lpetrich
Contributor
I finally was able to understand a proof of this theorem.
The Halting Problem - An Impossible Problem to Solve - YouTube
Turing & The Halting Problem - Computerphile - YouTube
Halting Problem -- Simple Proof
Halting problem
Let us say that we have a function that can test whether or not some function will halt when it is given some input. In pseudocode form:
function halt(function f, input data i) -> boolean
Its action:
if evaluation of f(i) will halt
. return true
else // it will run forever
. return false
end if
In 1936, Alan Turing showed that that program is undecidable. He did that by constructing a program that includes the halting tester and constructs a negation of its results:
function turing(function f)
. if halt(f,f)
. . . while true
. . . . // infinite loop
. . . end while
. else
. . return // it halts
. end if
end function
Now try to run that function called on itself: turing(turing)
If it will halt, it will run forever, while if it will run forever, it will halt. A contradiction. Thus, the halting problem is undecidable.
The Halting Problem - An Impossible Problem to Solve - YouTube
Turing & The Halting Problem - Computerphile - YouTube
Halting Problem -- Simple Proof
Halting problem
Let us say that we have a function that can test whether or not some function will halt when it is given some input. In pseudocode form:
function halt(function f, input data i) -> boolean
Its action:
if evaluation of f(i) will halt
. return true
else // it will run forever
. return false
end if
In 1936, Alan Turing showed that that program is undecidable. He did that by constructing a program that includes the halting tester and constructs a negation of its results:
function turing(function f)
. if halt(f,f)
. . . while true
. . . . // infinite loop
. . . end while
. else
. . return // it halts
. end if
end function
Now try to run that function called on itself: turing(turing)
If it will halt, it will run forever, while if it will run forever, it will halt. A contradiction. Thus, the halting problem is undecidable.