[DoomSlice]

A bit of computer science background: there is a theorem called the Church-Turing Thesis that states that everything that can be computed can be computed by a "machine" called a Turing Machine, look up in Wikipedia if you need to know exactly how a turing machine works.

Now for my proof.

Assume for the sake of contradiction that God exists with the usual Christian beliefs (omnipotence and omnipresence). There is a class of languages called "Non-turing recognizable languages" which cannot be computed using a Turing Machine (meaning they cannot be computed at all).

One such language is called EQ_TM, where EQ_TM = { <M , N> | L(M) = L(N)} where M and N are two turing machines and <M,N> is the string representation of those two machines. L(M) = L(N) means that the language that is accepted by turning machine M is the same as the language that N accepts (basically they are the same machine).

Since EQ_TM is a non-turing recognizable language, then there is no Turing Machine that can recognize it, and thus no way to compute it. However, if God existed with the aforementioned properties, he would be able to create a Turing Machine that would recognize EQ_TM.

Unfortunately, this would violate the Church-Turing thesis (which is the backbone of computation theory), so therefor no Turing Machine that God could make would do this, contradicting our initial assumption.

Therefor, a God does not exist (or at least is not omnipotent).