patternMajor
Algorithm to solve Turing's "Halting problem"
Viewed 0 times
problemhaltingalgorithmsolveturing
Problem
"Alan Turing proved in 1936 that a general algorithm to solve the
halting problem for all possible program-input pairs cannot exist"
Can I find a general algorithm to solve the halting problem for some possible program input pairs?
Can I find a programming language (or languages), where I for every kind of program in this language, it can decide if the program terminates or run forever?
halting problem for all possible program-input pairs cannot exist"
Can I find a general algorithm to solve the halting problem for some possible program input pairs?
Can I find a programming language (or languages), where I for every kind of program in this language, it can decide if the program terminates or run forever?
Solution
Can I find a general algorithm to solve the halting problem for some possible program input pairs?
Yes, sure. For example you could write an algorithm that returns "Yes, it terminates" for any program which contains neither loops nor recursion and "No, it does not terminate" for any program that contains a
Can I find a programming language (or languages), where I for every kind of program in this language, it can decide if the program terminates or run forever?
Not if that language is Turing-complete, no.
However there are non-Turing complete languages like for example Coq, Agda or Microsoft Dafny for which the Halting Problem is decidable (and in fact is decided by their respective type systems, making them total languages (i.e. a program that might not terminate will not compile)).
Yes, sure. For example you could write an algorithm that returns "Yes, it terminates" for any program which contains neither loops nor recursion and "No, it does not terminate" for any program that contains a
while(true) loop that will definitely be reached and doesn't contain a break statement, and "Dunno" for everything else.Can I find a programming language (or languages), where I for every kind of program in this language, it can decide if the program terminates or run forever?
Not if that language is Turing-complete, no.
However there are non-Turing complete languages like for example Coq, Agda or Microsoft Dafny for which the Halting Problem is decidable (and in fact is decided by their respective type systems, making them total languages (i.e. a program that might not terminate will not compile)).
Context
StackExchange Computer Science Q#4856, answer score: 27
Revisions (0)
No revisions yet.