halting problem

References

Summary

There is no algorithm H such that H satisfies the following:

given any algorithm A, and input I, H will return 1 if A stops when I is the input of A, and 0 if A doesn't stop when I is the input of A.

Proof:

Say there is such an H Define a new algorithm X:

Now use as input X: Say the output is X(X) If X(X) stops then H(X,X) = 1 But then X(X) loops forever, so X(X) doesn't stop.

Discussion

This is basically just a reformulation of Russel's paradox Basically all of these types of things are the same:

As Russel's Paradox

We can reformulate the halting problem as follows:

Associate to any algorithm A a set, as follows:

Now we'll think of the letters A,H,X as the above type of sets

Given a halting problem solution H, H(A,A) = 0 iff AI ∉ AI.

So the set corresponding to the algorithm X is XI  ≡ A|H(A,A) = 0  ≅ AI|AI ∉ AI This is Russel's class, which isn't a set

Full Comprehension

The (potential) underlying problem in Russel's Paradox is that you assume you can construct any set you want

The axiom of full comprehension says that given any property P, the set { x | P(x) } exists

There are lots of ways around this

  1. Restricted comprehension You can only say Given a set X and property P of the elements of X { X | P } exists

  2. (there are a bunch of weaker forms of comprehension)

Discussion

One interesting thing about this, is that the usual way of resolving Russel's paradox — of just saying that X is a class rather than a set, and therefore since X is defined to be { sets | … }, X ∉ X is fine and doesn't cause a contradiction — seems a bit odd, because it corresponds to the idea that X isn't an algorithm

But what does that mean? What is it then?

Resolutions

Russel's Paradox has a number of different possible resolutions

  1. Restrict the axiom of comprehension, so you can't actually define the set X
  2. Distinguish between sets and classes
  3. Structural set theories don't allow you to define a set inherently

-It's basically just category theory; there are no elements truly internal to a set -Instead you have morphisms/relations between sets

  1. Use paraconsistent logic! So you say it's actually fine that there's a contradiction

Lawvere's Fixed Point Theorem