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.
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.
This is basically just a reformulation of Russel's paradox Basically all of these types of things are the same:
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
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
Restricted comprehension You can only say Given a set X and property P of the elements of X { X | P } exists
(there are a bunch of weaker forms of comprehension)
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?
Russel's Paradox has a number of different possible resolutions
-It's basically just category theory; there are no elements truly internal to a set -Instead you have morphisms/relations between sets