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.
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.
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.
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.
There's a bug in your reasoning.
The Turing completeness theorem says that no *Turing* *Machine* can analyze a program and its input, for all programs and inputs, and decide whether the program will halt or not.
If there exists a god that can answer the Turing problem for all programs, then the theorem says that this god thing is more computationally powerful than a Turing machine, and therefore not a Turing machine.
Going further, the diagonalization argument used to prove both Turing and Goedel applies to any non-trivial logic system. You could apply diagonalization to a hypothetical god; can god decide whether god will halt or not?
But this is not new at all; a very old philosopher's conundrum is "can god make a rock so heavy that god cannot lift it?" The root of this is "is god subject to consistency?"
While that's an interesting question, it does not prove the existence of god either way. One could argue that god is a fantasy, and therefore not subject to consistency. One could also argue that god is outside of our universe, and therefore not subject to our petty little human notions of consistency (insert lots of wild arm waving) and postulate a magic god being that can resolve inconsistency.
Personally i'm going with "god is a fantasy, and diagonalization is hardly the only consistency bug in this fantasy."
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)!
What a great interesting answer! Your not trying to be smart, you are smart!
Follow us on:
From the officers:
The ACA Lecture Series continues Sunday, October 11th at 12:15pm in the Austin History Center, 9th and Guadalupe. The building opens at noon. Texas Freedom Network's Dan Quinn will give us an update on their activities. The lecture is free and open to the public.