---

This is the first in a series of articles building up to an explanation the Church-Turing Thesis.

Consider the following yes-or-no question.

Will the following program terminate?

We can contrive simple examples for a "yes" case of the question:

def a():
    print("Hello")
a()

And for the "no" case.

def a():
    return a()
a()

Someone fluent in Python will tell you of the above: No, it will accumulate to infinite. Its stack will grow as such.

   .
   .
   .
|-----|
| a() | <-- third call to a()
|-----|
| a() | <-- second call to a()
|-----|
| a() | <-- first call to a()

This toy question invites us to consider a concept called decidability. A yes-or-no question is decidable if there exists an effective means of computing its answer.

An example of a very decidable question is:

Is the following number prime?

42

No.

41

Yes.

We, as thinkers, can surmise computing machines that can automatically and reliably answer the above question with a yes or a no. The device that you are reading this post on is a machine that can reliably answer yes or no to Is this number prime?

Undecidability

Returning to our first example. Why is it considered undecidable?

The device you are using can not reliably answer Will the following program terminate?. This is there's no simple tool for Bill Gates or Steve Jobs to include in their computers that would simply choose not to run a program with an infinite loop.

From a different angle, we are unable to determine whether a program will run without actually running the program. Well, if we want to know if a program will terminate, and our tool for determining so must run that program to completion... then we're hosed. The tool will sit and churn forever on the input.

Thus, "Does this program terminate?" is an undecidable question. We'll build on this concept (and return to it) in follow-up posts about the Church-Turing Thesis and its broader implications.

Back to posts