- #36
AlephZero
Science Advisor
Homework Helper
- 6,982
- 299
stevendaryl said:To give an illustration from computer science, the halting problem: Some computer programs get into an infinite loop and never halt. That's completely predetermined by the program. But you can show (this was shown by Turing) that there is no way to predict which computer programs halt and which ones don't.
That is slightly wrong, but the "slightly" seems important to this discussion.
Of course you can (almost always) predict whether any particular computer program will halt or not, by applying the ordinary rules of logic.
What Turing showed was this: you can't produce just one algorithm (which you could implement as a computer program) that will predict whether all possible computer programs will halt or not.
The proof is very simple: suppose such a "magic debugger" exists. Now write a program that says "If the magic debugger says this program will loop for ever, then halt, otherwise loop for ever".
But how this relates to determinism is not so simple IMO. The proof says nothing about you can prove by some method or other whether all possible programs halt or loop. All it says is that one particular string of symbols in a programming language (i.e. the one in quotes in the previous paragraph) is not actually a computer program, it is only a meaningless string of symbols that looks similar to a program.
Last edited: