Hello folks,

Can the Halting problem be used as a proof that god doesn't exist?

http://en.wikipedia.org/wiki/Halting_problem

The halting problem is about what things can be computed. Godels's incompleteness theorem is about the limits of a mathematical system to prove things which are true. This line of thinking has even been used to show that there are facts about the universe that cannot be determined (either measured or computed). This last result was published in a recent Scientific American.

If anything, these things add up the fact that our knowledge is and forever will be limited. This plays into the bogus "god of the gaps" arguments of theists where they will forever claim that god knows these things that we do not know. As always, they will make these claims without evidence. They will be convincing to those who cannot think critically.

I don't see these limits on our knowledge to ever be turned in to an argument for the non-existence of god, but I would be happy to be proved wrong.

Hello Don,

Thanks for the answer. I just thought about that line from Wikipedia:

"[..]a general algorithm to solve the halting problem for all possible program-input pairs cannot exist[..]". So if god is almighty and especially all-knowing, god can solve the halting problem for all possible program-input pairs. Therefore god must have a way or in other words an algorithm to do so. However such a general algorithm cannot exist. Therefore god is not all-knowing, however since being all-knowing is one attribute of god, god doesn't exist.

Got it. It's a dig against the claim of omniscience. I think what you found has some validity, but I think there are bigger problems with omniscience, such as whether or not a god can know the future. If so, that would seem to invalidate any claim of free will.

Well, if i were you i would try to speak with a theoretical computer science specialist about this (some dr. from a state university). And of course don't tell him/her the real reason why you want to understand this halting problem and the proof so badly. ;-) Although I study computer science myself I'm still a beginner regarding theoretical computer science so I can't help here. (Maybe I should listen to my own piece of advice. ;-D ). I vaguely remember that an Oracle machine can solve the Halting Problem for Turing machines. However the Halting Problem also exists for Oracle Machines if I remember it correctly. So maybe the Theists' claims that we don't have a proof for god's nonexistence are wrong after all ... Hurray!! :)

[ If it can be used as a real proof, I would try to "spread the word" for instance in this "Atheist Experience" Show. However the problem ist known for 74 years but Religion still exists on this planet... . So either it can't be used as a real proof or people are not listening.

I have to laugh. I'm a PhD in computer science and I've taught the theory of computation for several years.

Och :) Sorry, I didn't know. Then I should apologize to you.

Don, do you know if a video regarding the Halting Problem or Turing was ever produced for the "Atheist Experience" Show? If the answer is 'yes', could you please give me the link? What would be nice.

If not:

I have one final suggestion/or "plea" to make. Since you are a PhD maybe you could indeed make a "special" "Atheist Experience" Show, there you could talk about and explain Turing machines and Oracle machines and then the Halting Problem, so that the general public can understand it and then conclude from that about the question for god's existence.

I think such a show would be awesome, because

(a) many computer science students would be grateful to you! :)

(b) You would have a powerful argument in your hand against religious dogma. Although the Halting Problem is known for so long it seems to me that it is just not known well enough in public. (People tend to think: "Ahhh, Computer & Science how boring/complicated! Just stay away from me! :) " ) I can't image that religious people can have a counterargument for this even after 70 years.

Well, I just wanted to make this suggestion. :)

No need to apologize. The irony was just amusing.

I'm not convinced that the halting problem has a connection with god claims. The halting problem, Godel's incompleteness theorem, the Church-Turing thesis, etc., have to do with the limits of specific formalisms such as the Turing machine, computer algorithms, or mathematical systems. They aren't about reality as a whole.

It's too easy for a theist to claim (without justification) that their god transcends any formalism and whatever proof you would construct does not apply to their god. I don't see this as a path to convince anyone.

It wouldn't invalidate free will if God changes the past, each time making a parallel timeline. We would be stuck in a time where God fixed some errors but at some point he left this timeline and began another without a mistake, leaving us to do whatever we please.

I have no idea what they are talking about. I hope I'm not making a fool of myself. Ah, yes, god is in a parallel timeline, I thought time was in a dimension, and there were parallel Universes … I'm making up science…there is no god. Does this prove I'm smart?

nineteeneightyfour said, "Hello folks, Can the Halting problem be used as a proof that god doesn't exist?"

I could not prove the existence or none existence of God with the halting problem?

The halting problem is unsolvable? If you prove that the statement is true then it is false.

The Turing Halting Problem's basic theory is based on the Turing machine (a very simple computer) which given certain inputs would halt.

Existence or non-existence:

Combinations of inputs detected and that combination written down. Don't use that set of inputs to keep the computer from crashing. Then run it again and find the next set of inputs halt the machine write it down and so on. That shows what not to do, but another set of inputs could cause the same problem. The halting problem is to determine, given a particular input to a particular computer program, whether the program will terminate after a finite number of steps.

This is like (define God first) to solve problem - God is infinite - there is nothing that is not God - then there is nothing that is God.

Algorithms may contain loops, which may be infinite or finite in length. The amount of work done in an algorithm usually depends on the data input. Algorithms may consist of various numbers of loops, nested or in sequence. The Halting problem is to determine if the program will eventually stop when it is given that input.

There is no existence - there is existence.

The (problem) in the halting problem is to determine what procedure works for all programs and inputs. Every particular program either halts on a given input or does not halt. Example (one algorithm that always answers halt and another that always answers doesn't halt. For any specific program and input, one of these two algorithms answers correctly, although nobody may know which one. Halt or doesn't halt.

The answer there is no existence - would fall as the program continues to run - there is existence would rise as the program goes on.

Nobody knows which answer is correct - no proof that there is or is no existence.

An interpreter will not halt if its input program does not halt, so this cannot solve the halting problem. It does not answer (doesn't halt) for programs that do not halt.

It really comes down to common sense to make an accurate decision.

How does the programmer provide accurate information for a problem that cannot be defined? Is God (infinite) (everything) (nothing)!