Why Can't a Program Tell Whether Another Program Stops?

This page looks at a classic argument for why you cannot write a program that examines another program and tells you whether that other program stops. But before doing that, let's think about an obvious way to answer the question, and see why it does not work.

A naive algorithm

To tell whether a program stops, let's just run it. When it stops, say yes. Won't that work? Why not? Answer

A thought experiment: The premise

Let's do a thought experiment. Imagine that a wizard manages to write a program that can examine another program and tell whether that other program stops. A program can have many function definitions in it; let's make the wizard's job even simpler and ask for a definition of a function called terminates with the following contract.

Function terminates(fundef, arg) takes two strings fundef and arg. String fundef should be the definition of a function that takes a string as an argument and produces a string as an answer. Suppose that the function defined by string fundef is named f. (It could have any name.)

Terminates(fundef, arg) returns true if f(arg) will eventually stop without encountering an error, and returns false if f(arg) runs forever or encounters an error.

For example, terminates("Define f(x) = x.", "zzz") yields true, since if you run function f define by

  Define f(x) = x.