GB: Sorry, it was late and my reply was not very transparent. First off, the only reason i introduced this question: "Can God (as in creator of our universe) know he is not controlled by a greater God?" was to avoid "the matrix" since, well, its another rather fuzzy concept :-). I believe we are both asking the same question, and the answer should be pretty clear: he cant.
As for the rest of my post, i think making "formal" claims on God, and treating him like some "formal" philosophical object is a bad idea; the idea that God could somehow be summoned out of a sufficiently complicated discussion on first causes, eternity/infinite, etc. does not appeal to me at all. Thats why i brought up the Higgs bosone - it make very little sence to proove the neccesary existence of the Higgs bosone (A much more humble project than prooving the existence of God!).
As for the other examples, well, i wanted to hint at the difficulty of a "formal" discussion on God. Halting oracles and sets of all sets seem to make a lot of sence; they are easy to think of and define in ordinary language. but that does not mean the begin to exist in a puff of logic. In fact, it turns out a much more carefull analysis of halting oracles and "sets of all sets" reveal they have very subtle difficulties which mean they cant exist; at least not the way we think of them.
http://scientopia.org/blogs/goodmath/2010/09/12/the-halting-problem/
http://en.wikipedia.org/wiki/Russell's_paradox
As an example for why this is important, a few years back there was a group of french mathematicians who was working on a special type of mathematical object, and was prooving one interesting theorem after another. The only problem was that a few years later, it was proven that the type of object they was working with could not be constructed; they had been prooving one really important theorem after another which was only valid for the members of the empty set!
So is "the set of all Gods" empty?
