The Halting Problem

Is it possible to write a program A that takes another program B as input and which determines if B will halt or loop forever?

Well it turns out that an assumption that the answer is “yes” leads to a paradox and hence there is a proof by contradiction that the correct answer must be “no”.

The proof goes like this:

Assume program A can determine if program B will halt or loop forever.

Now I write a program C that calls program A as follows:

B = input_program
if A says B will halt then
   loop forever
else
   stop
end if

And I now feed program C to itself as input.

The result is that if C will halt, then it will loop forever, but if it will loop forever, then it will halt.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s