This is a note of undecidablility in computing based on two books:

  • Chapter 11 of “Once Upon an Algorithm: How Stories Explain Computing”.
  • Chapter 10 of “The Little Schemer”

1 Halting Algorithm

The only source of nonterminating behavior is loops. Checking the termination of an algorithm is called a halting problem. We need an algorith, say halts, to analyze all loops in the algorithm.

Suppose that the halts algorihtm exists, then we can create another algorithm selfie that determines whether an algorithm terminates when executed given its own description as input.

1
2
3
4
5
6
7
8
def selfie(algorithm):
  is_decidable = halts(algorithm)

  while is_decidable:
    is_decidable = halts(algorithm)

# ooops
selfie(selfie)

In the above code, if selfie is decidable, it enters an infinite loop that is indecidable. If selfie is undidable, it terminates. Therefore there is a logical contradiction.

2 The Schemer Version

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
; will-stop? return #t or #f
; depending on whether the arugment stops or not.

(define eternity
  (lambda (x)
    eternity(x)))

(define will-stop?
  (lambda (f) ...))

(define last-try
  (lambda (x)
    (and (will-stop? last-try) (eternity x))))

3 The Common Idea

The common idea of the two examples is to enter an infinite loop when an algorithm is decidable and exit when it is undecidable – therefore we create a logic paradox similar to the simple contradition of “I am lying”.

From the article:

In 1901 Russell discovered the paradox that the set of all sets that are not members of themselves cannot exist. Such a set would be a member of itself if and only if it were not a member of itself. This paradox is based on the fact that some sets are members of themselves and some are not. These paradoxes are self-referential because they conflate the definition with what is being defined. They confound the properties that define a set with the members of the set. They result from their implicit confusion between the “object language,” which talks about the individual members of sets, and the “metalanguage,” which talks about the sets themselves. Russell’s discovery led immediately to much research in set theory and logic to define the nature of sets, classes, and membership more accurately.