Recently I’ve been working on a theory of computation that’s based on set theory, rather than the type-theory that most modern languages are built on. (I think that such a theory would be highly homogeneous in a way that makes it particularly suitable for automated analysis.)
A pretty natural question for a theory of computation is: what is the computational power of this theory? The landmark result in this space is the halting problem which establishes a bound on what is computable by an algorithm. But a set-theoretic construction of computation lacks several of the features that the halting problem invokes, so it is not immediately obvious that the result applies to this new model — in particular there are “theories”, not “algorithms” that “halt”.
I currently have a tentative way to express any problem as a theory about sets, so in particular one can express the halting problem. Does this mean this new model is able to solve the halting problem? That would actually not be a good thing because I believe it means that the model of computation would not be physically realizable (I intuitively believe the physical Church-Turing thesis).
Set theory has its own set of impossibility results, and in particular for this case, Russell’s paradox. Which roughly states that there cannot be a set of all sets that do not contain themselves — which is strikingly similar in structure to the halting problem’s result that there cannot be an algorithm that halts on all programs that do not halt on themselves.
So the natural question is: does Russell’s paradox prevent the same type of set-theoretic computations that the halting problem prevents for other models?
Fortunately I’m not the first person to ask these kinds of questions, and there’s something called Lawvere’s fixed point theorem which I do not fully understand. But my lay understanding is that this is strong evidence that the answer to the above question is “yes”.
I’m not sure yet how this affects my model of computation; if it’s possible to represent an algorithm that solves the halting problem, does that mean the model is unsound? Or perhaps representation of impossible objects is fine, because we do some of that to prove that one can derive a contradiction from such an object and thus that the object can’t exist?
Stay tuned.
kmod's blog 
3 responses to “Halting problem ==? Russell’s paradox?”
I think the 2 problems are different.
Russell’s paradox only occurs because people believe in things that cannot be constructed, like sets of all sets and uncountable many irrational. I am a Constructivist also it seems 😉
Halting problem is actually computable for a given maximum memory of the Turing machine – even if unpractical to implement for some situations. I would not be surprised if program verification regarding halting is practical to implement for most real-life scenarios.
Why Kolmogorov complexity is not computable – root cause and an example
LikeLike
Could you say something analogous about Russell’s paradox? Maybe something like that for most sets it’s possible to determine if they contain themselves, so as a practical matter we could reason about most of a set/class of sets that don’t contain themselves?
LikeLike
There is another interesting paradox discussed by Bertrand Russell: “The smallest positive integer not definable in under sixty letters”, actually better known as Berry’s paradox. You can also prove that such number creates a contradiction, because you just defined it under sixty letters.
For me, the above paradox shows that it is not enough to create a condition for something to exist with that condition – or a set of such elements. Such paradoxes argue that such objects defined by a predicate cannot exist sometimes.
The same is for “the set of sets that do not contain themselves”. Let’s take it the other way around. Could you imagine a set that _contains_ itself? You take a set, you make it an element of itself, then you get a bigger set that needs to be included in the set.
Intuition: Such set that contains itself as element is like a dragon that managed to swallow itself. This cannot end. You can’t even define an algorithm for this set to grow, because it must grows from… everywhere – because each element is also recursively element of itself.
You can define such set that don’t contain itself only by complementing another set. However, you cannot always enumerate the elements of the complement of a simple set (even infinite) that you can enumerate.
For me, if you cannot imagine how to construct such set iteratively, it does not exist for all practical concerns. The same with the “set of all sets”, even without excluding such elusive objects that “contains themselves as elements”. You cannot iterate such set, so it does not exist for me.
The Berry paradox is a way more legitimate construct. You can imagine numbers that can be described by a number of letters. You can imagine that there should be a minimum description length of such number. Just that… Kolmogorov complexity proves that such minimum description is not always computable. You would be able to compute that if the halting problem would be decidable, but it is not in general.
LikeLike