I perfectly understand and accept the proof that a Turing-machine cannot solve the halting problem.
Indeed, this is not one of those questions that challenges the proof or result.
However, I feel that there is still something left to be explained … I am still left wondering exactly why the Halting problem is not solvable. Of course, in the sense that there is a proof, there is a why here … and yet … I feel that some important other part of the why is missing.
Let me explain:
First, let's assume we just try to solve the 'empty-tape halting problem' and let's assume that the machines we are interested in only have two symbols: 1 and 0. Now, given some machine, will it halt, when stated on the empty tape (meaning: all 0) or not?
Now, we know that this problem is not Turing-solvable. If it were, we get a logical contradiction. OK, I get it. I have no problem with that at all, and like I said, I can follow the proof and I completely agree with it. I perfectly accept that this halting problem is not solvable.
But suppose I would actually try and give it a go: suppose I would try and solve this halting problem. We know the set of all turing-machines is enumerable, so let's just go through them one by one. Now, presumably this enumeration is such that it starts with relatively 'simple' machines. Indeed, I could first list all the ones with 1 internal state, then all the ones with 2, etc. since for any $n$, and with only $2$ symbols, there are only finitely many possible machines
Now, for all the machines with $1$ state, I can easily predict their behavior. Some halt. Some don't. OK, moving on to the machines with $2$ states. With some effort, I can predict the behavior for all of them as well. Cool. On to $3$ … ok, now it becomes more difficult .. but even here I can do it. I know, because people working on the Busy Beaver problem have figured this out. And I believe they figured it out for $n=4$ as well …
Interestingly, these researchers are using computers to help them figure out the halting or non-halting behavior for these relatively 'simple' machines. These computer programs are, in a way, trying to solve the halting problem, at least for very small values of $n$. Presumably, these machines 'analyze' and 'break down' the behavior of a machine with $4$ states into something that can be demonstrated to halt or not halt. But of course, we know they can't solve it for all $n$ … they can't be perfect. And indeed, for $n=5$ the behavior of Turing-machines gets so complicated that human nor machine is able to figure out (yet) whether the machine halts or not.
So … here is my question: what is it that we're running into that prevents us from figuring out the halting behavior?
The proof of the Halting problem uses self-reference. That is, if a machine could solve the halting, then we can show that thee must be a machine that halts on its own input (i.e. when given its own program, or its own number in some enumeration, or..) if and only if it does not .. a contradiction.
OK, but this is when we have a machine with certain powers … in a way, a machine that can solve the halting problem is a machine with 'too much' power, which leads to a contradiction.
But, the halting-detection machines used by the Busy Beaver researchers don't have too much power. They have too little power. Currently they can't solve $n=5$. OK, so we give them some more power. Maybe at some point they can solve $n=5$ … but they still can't solve $n=6$. Maybe we can give them enough power to solve $n=6$, or $n=7$ or ….
… so my question is: is there some 'special' value of $n$, say $n=m$ where this has to stop. Where, somehow, the only way to solve $n=m$, is by a machine that has 'too much' power? But why would that be? Is it because of some kind of self-reference? Because the only way to solve $n=m$ is by a machine that, as it tries to analyze and predict the behavior of some machine with $m$ states, cannot break it down to anything 'smaller' than something that requires solving $n=m$ itself? Some kind of 'minimal' value not unlike some set of minimum requirements that formal systems need to have in order to apply the Godel construction to them?
One thought I have is that this cannot be: like I said, for any $n$, there are only finitely many machines to consider. As such, it is computable; there is some machine that correctly classifies all machines with $n$ states as empty-tape halters or non-halters: it takes a machine on the input, goes through its finite list with pre-stored answers, and outputs that answer. There is a machine that does this for $n=5$, there is one for $n=6$, etc. And, none of those machines have too much power: no contradictions here. They all have too little.
Then again, these machine don't do any explicit analysis of the machines involved … they just happen to give the right value. So, maybe there is still some value of $n$ where the approach of actually trying to analyze and predict the behavior of machine starts to break down for some fundamental, again possibly self-referential, reason?
Or: is it that the analytical approach merely gets harder and harder … but that there is no 'special' point where it becomes, for some theoretical, fundamental reason, too hard? As such, the contradiction only comes from a machine that can do it for all infinitely many values of $n$? Indeed, maybe the problem is that in order to analyze the behavior of all machines with $n$ states, we need a machine that has to have more than $n$ states … and so while for every $n$, there is a machine $M$ that can perform the analysis, the complexity of $M$ is greater than any of the machines with $n$ states, and hence you'd need another, even more complicated machine $M'$ in order to analyze machines with the kind of complexity that $M$ has … thus setting up an infinite regress that you can never complete, i.e. there is no one machine that can 'do it all'?
Can someone help me how to think about this?
Best Answer
I think the following portion from your question is most important:
The solution to solving $\Sigma(5)$ isn't simply giving Turing machines "more power." The reason we don't know $\Sigma(5)$ right now is because there are 5-state Turing machines which mathematicians believe will never halt, but have not been able to prove will never halt. The problem is not as simple as just enumerating through all of the 5-state Turing machines since once you've done that, you still need to figure out if the Turing machine halts or not, which, as you know, is not a trivial problem. We've been able to do this for 4-state Turing machines, but we don't know yet if we can do this for 5-state Turing machines because there may very well be 5-state Turing machines which we can never prove to be halting/non-halting within the system of classical mathematics (that is, ZFC).
Now, you've asked what is the magic number is: What is the magic number $n=m$ such that we will never be able to solve for $\Sigma(n)$? As I've said above, that magic number could very well be $n=5$, but that hasn't been proven yet. However, mathematicians have proven that $\Sigma(1919)$ is indeed un-knowable within ZFC. Before explaining this, I think it might be helpful to quote your question again:
My answer to this question is yes, there is a 1919-state Turing machine such that trying to predict if the machine halts would be fundamentally unsolvable within our system of mathematics. See, the way mathematicians proved $\Sigma(1919)$ is unsolvable is by constructing a 1919-state Turing machine $M$ which halts if there is a contradiction within ZFC and never halts if ZFC is consistent. However, there's no way to prove ZFC is consistent using the axioms of ZFC because of Godel's Second Incompleteness Theorems. This means we can never use the ZFC axioms of mathematics to prove machine $M$ ever halts or not because doing so would constitute a proof that ZFC is consistent. Thus, mathematicians can't predict if machine $M$ halts or not because of Godel's Incompleteness Theorem, which means that the busy-beaver problem for 1919-state Turing machines is unsolvable.
I hope this gives you some more insight into why $\Sigma(n)$ is solvable for small values of $n$ but unsolvable for larger values of $n$. Anyway, I am certainly not an expert in theory of computation, so if someone would like to add an alternate explanation/clarifying comments to my answer, feel free. Thanks!