Exactly when and why can a Turing-machine not solve the halting problem?












26














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?










share|cite|improve this question




















  • 3




    @MattSamuel The OP is aware of this, as they state in their question.
    – Noah Schweber
    2 days ago






  • 1




    @NoahSchweber Thanks Noah ... you are actually just the person I was hoping would see this post ... am I making sense? Do you see what I'm getting at?
    – Bram28
    2 days ago








  • 3




    The issue is that having more "power" will not solve the problem. No matter how powerful your machine is it cannot solve a busy beaver state even for low n. All the turing machine can do is continue running and running and even after 1000000000000 steps we cannot truely be sure it doesn't halt without a pattern, and many of these busy beaver states don't exhibit any obvious pattern. Only an infinitely powerful turing machine (infinite time turing machine) can solve the problem.
    – Matthew Liu
    2 days ago












  • Defining how a program $P$ halts is easy : there exists a finite integer $n$ such that running $P$ for $n$ steps yields the $0$ state. Defining what properties of $P$ guaranty that $n$ doesn't exist is exactly the purpose of our logic/mathematical theories (PA, ZFC...). That there exists two different integers such that $P$ is in the same state after $n$ and $m$ steps is one of those properties. But when looking at theories formalizing the arithmetic, we get much more, and we reach the incompleteness problem : we have no way to guaranty our theory is consistent.
    – reuns
    2 days ago








  • 2




    @Bram28 Still won't matter how much the machine is able to "reason". Fundamentally speaking reasoning is no different from calculation speed. Our human brains are no different from machines other than the fact that our brains are still much more powerful but we aren't made out of metal so we make more mistakes.
    – Matthew Liu
    2 days ago
















26














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?










share|cite|improve this question




















  • 3




    @MattSamuel The OP is aware of this, as they state in their question.
    – Noah Schweber
    2 days ago






  • 1




    @NoahSchweber Thanks Noah ... you are actually just the person I was hoping would see this post ... am I making sense? Do you see what I'm getting at?
    – Bram28
    2 days ago








  • 3




    The issue is that having more "power" will not solve the problem. No matter how powerful your machine is it cannot solve a busy beaver state even for low n. All the turing machine can do is continue running and running and even after 1000000000000 steps we cannot truely be sure it doesn't halt without a pattern, and many of these busy beaver states don't exhibit any obvious pattern. Only an infinitely powerful turing machine (infinite time turing machine) can solve the problem.
    – Matthew Liu
    2 days ago












  • Defining how a program $P$ halts is easy : there exists a finite integer $n$ such that running $P$ for $n$ steps yields the $0$ state. Defining what properties of $P$ guaranty that $n$ doesn't exist is exactly the purpose of our logic/mathematical theories (PA, ZFC...). That there exists two different integers such that $P$ is in the same state after $n$ and $m$ steps is one of those properties. But when looking at theories formalizing the arithmetic, we get much more, and we reach the incompleteness problem : we have no way to guaranty our theory is consistent.
    – reuns
    2 days ago








  • 2




    @Bram28 Still won't matter how much the machine is able to "reason". Fundamentally speaking reasoning is no different from calculation speed. Our human brains are no different from machines other than the fact that our brains are still much more powerful but we aren't made out of metal so we make more mistakes.
    – Matthew Liu
    2 days ago














26












26








26


10





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?










share|cite|improve this question















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?







turing-machines






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 2 days ago









amWhy

191k28224439




191k28224439










asked 2 days ago









Bram28

60.1k44489




60.1k44489








  • 3




    @MattSamuel The OP is aware of this, as they state in their question.
    – Noah Schweber
    2 days ago






  • 1




    @NoahSchweber Thanks Noah ... you are actually just the person I was hoping would see this post ... am I making sense? Do you see what I'm getting at?
    – Bram28
    2 days ago








  • 3




    The issue is that having more "power" will not solve the problem. No matter how powerful your machine is it cannot solve a busy beaver state even for low n. All the turing machine can do is continue running and running and even after 1000000000000 steps we cannot truely be sure it doesn't halt without a pattern, and many of these busy beaver states don't exhibit any obvious pattern. Only an infinitely powerful turing machine (infinite time turing machine) can solve the problem.
    – Matthew Liu
    2 days ago












  • Defining how a program $P$ halts is easy : there exists a finite integer $n$ such that running $P$ for $n$ steps yields the $0$ state. Defining what properties of $P$ guaranty that $n$ doesn't exist is exactly the purpose of our logic/mathematical theories (PA, ZFC...). That there exists two different integers such that $P$ is in the same state after $n$ and $m$ steps is one of those properties. But when looking at theories formalizing the arithmetic, we get much more, and we reach the incompleteness problem : we have no way to guaranty our theory is consistent.
    – reuns
    2 days ago








  • 2




    @Bram28 Still won't matter how much the machine is able to "reason". Fundamentally speaking reasoning is no different from calculation speed. Our human brains are no different from machines other than the fact that our brains are still much more powerful but we aren't made out of metal so we make more mistakes.
    – Matthew Liu
    2 days ago














  • 3




    @MattSamuel The OP is aware of this, as they state in their question.
    – Noah Schweber
    2 days ago






  • 1




    @NoahSchweber Thanks Noah ... you are actually just the person I was hoping would see this post ... am I making sense? Do you see what I'm getting at?
    – Bram28
    2 days ago








  • 3




    The issue is that having more "power" will not solve the problem. No matter how powerful your machine is it cannot solve a busy beaver state even for low n. All the turing machine can do is continue running and running and even after 1000000000000 steps we cannot truely be sure it doesn't halt without a pattern, and many of these busy beaver states don't exhibit any obvious pattern. Only an infinitely powerful turing machine (infinite time turing machine) can solve the problem.
    – Matthew Liu
    2 days ago












  • Defining how a program $P$ halts is easy : there exists a finite integer $n$ such that running $P$ for $n$ steps yields the $0$ state. Defining what properties of $P$ guaranty that $n$ doesn't exist is exactly the purpose of our logic/mathematical theories (PA, ZFC...). That there exists two different integers such that $P$ is in the same state after $n$ and $m$ steps is one of those properties. But when looking at theories formalizing the arithmetic, we get much more, and we reach the incompleteness problem : we have no way to guaranty our theory is consistent.
    – reuns
    2 days ago








  • 2




    @Bram28 Still won't matter how much the machine is able to "reason". Fundamentally speaking reasoning is no different from calculation speed. Our human brains are no different from machines other than the fact that our brains are still much more powerful but we aren't made out of metal so we make more mistakes.
    – Matthew Liu
    2 days ago








3




3




@MattSamuel The OP is aware of this, as they state in their question.
– Noah Schweber
2 days ago




@MattSamuel The OP is aware of this, as they state in their question.
– Noah Schweber
2 days ago




1




1




@NoahSchweber Thanks Noah ... you are actually just the person I was hoping would see this post ... am I making sense? Do you see what I'm getting at?
– Bram28
2 days ago






@NoahSchweber Thanks Noah ... you are actually just the person I was hoping would see this post ... am I making sense? Do you see what I'm getting at?
– Bram28
2 days ago






3




3




The issue is that having more "power" will not solve the problem. No matter how powerful your machine is it cannot solve a busy beaver state even for low n. All the turing machine can do is continue running and running and even after 1000000000000 steps we cannot truely be sure it doesn't halt without a pattern, and many of these busy beaver states don't exhibit any obvious pattern. Only an infinitely powerful turing machine (infinite time turing machine) can solve the problem.
– Matthew Liu
2 days ago






The issue is that having more "power" will not solve the problem. No matter how powerful your machine is it cannot solve a busy beaver state even for low n. All the turing machine can do is continue running and running and even after 1000000000000 steps we cannot truely be sure it doesn't halt without a pattern, and many of these busy beaver states don't exhibit any obvious pattern. Only an infinitely powerful turing machine (infinite time turing machine) can solve the problem.
– Matthew Liu
2 days ago














Defining how a program $P$ halts is easy : there exists a finite integer $n$ such that running $P$ for $n$ steps yields the $0$ state. Defining what properties of $P$ guaranty that $n$ doesn't exist is exactly the purpose of our logic/mathematical theories (PA, ZFC...). That there exists two different integers such that $P$ is in the same state after $n$ and $m$ steps is one of those properties. But when looking at theories formalizing the arithmetic, we get much more, and we reach the incompleteness problem : we have no way to guaranty our theory is consistent.
– reuns
2 days ago






Defining how a program $P$ halts is easy : there exists a finite integer $n$ such that running $P$ for $n$ steps yields the $0$ state. Defining what properties of $P$ guaranty that $n$ doesn't exist is exactly the purpose of our logic/mathematical theories (PA, ZFC...). That there exists two different integers such that $P$ is in the same state after $n$ and $m$ steps is one of those properties. But when looking at theories formalizing the arithmetic, we get much more, and we reach the incompleteness problem : we have no way to guaranty our theory is consistent.
– reuns
2 days ago






2




2




@Bram28 Still won't matter how much the machine is able to "reason". Fundamentally speaking reasoning is no different from calculation speed. Our human brains are no different from machines other than the fact that our brains are still much more powerful but we aren't made out of metal so we make more mistakes.
– Matthew Liu
2 days ago




@Bram28 Still won't matter how much the machine is able to "reason". Fundamentally speaking reasoning is no different from calculation speed. Our human brains are no different from machines other than the fact that our brains are still much more powerful but we aren't made out of metal so we make more mistakes.
– Matthew Liu
2 days ago










5 Answers
5






active

oldest

votes


















32














I think the following portion from your question is most important:




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?




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:




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?




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!






share|cite|improve this answer



















  • 1




    Someone can find a theory T that is "obviously consistent" and does prove an explicit upper bound for $Sigma(1919)$ ? If T,ZFC both are consistent then T is stronger than ZFC since it will prove ZFC is consistent.
    – reuns
    2 days ago








  • 3




    @Bram28 Yes, if there is a contradiction in ZFC, this Turing machine will find it and halt. On the other hand, if the Turing machine halts, then it has found a contradiction in ZFC and ZFC is inconsistent. Therefore, this is a biconditional statement.
    – Noble Mushtak
    2 days ago






  • 1




    @Bram28 And continuing Noble's comment, this equivalence - appropriately phrased in the language of arithmetic - is provable in PA, and indeed much less.
    – Noah Schweber
    2 days ago






  • 4




    @NobleMushtak: NBG is known to be equiconsistent with ZFC, so looking for an inconsistency of either of them is basically the same task. (I don't know for sure, but I could imagine the optimizations necessary for cramming it into 1919 states involve much more drastic reformulations of the system anyway). NF versus ZFC would be a different matter ...
    – Henning Makholm
    yesterday








  • 2




    @Bram28 : Currently 1919 is special. But, in 2016, this special number was 7918. (I know the paper I cite had led to work condensing the machine to fewer states and that there was success. I do not know if the 1919 result follows from that chain of work or possibly a different chain of work.) So, tomorrow, someone could show that the TM can be condensed to a 500 state machine, or to a 5 state machine? This is currently unknown. It may be unknowable how small a machine does this computation -- what is the intrinsic entropy of a computation?
    – Eric Towers
    yesterday



















10














Since, as you observe, any finite amount of the halting problem - that is, any set of the form $Hupharpoonright s:={x<s:Phi_x(x)downarrow}$ - is computable, there isn't any particular sharp impossibility point. There are some interesting "phase transitions" which appear relevant - e.g. at a certain point we hit our first universal machine - but I don't know of any which have any claim to be the point where the halting problem becomes noncomputable.



On the other hand, as you also observe the way in which the $Hupharpoonright s$s are computable is non-uniform (otherwise, the whole halting problem would be computable). So we can try to measure this "ongoing complexity." There are two, to my mind, natural approaches:




  • Given $n$, how up up the "hierarchy of theories" - from fragments of PA, to fragments of $Z_2$, to fragments of ZFC, to ZFC + large cardinals - do we have to go to get a theory which can decide whether each of the first $n$ Turing machines halts on input $0$?


  • Given $n$, how complicated is the finite string consisting of the first $n$ bits of the characteristic function of the halting problem (call this string "$eta_n$")?



Of these two approaches, the first has some draw which the second lacks, but it's also far more vague and limited. The second winds up leading to a very rich theory, namely the theory of Kolmogorov complexity (and its attendant notions, like algorithmic randomness), and also partially subsumes the former question. So I think that's my answer to your question: ultimately you won't find a sharp transition point, but the study of the dynamic behavior of the complexity of the halting problem is quite rewarding.






share|cite|improve this answer





















  • Thanks Noah! ... a little over my head .. though I like your "phase transitions" notion .... from one of the other answers I gather that indeed for some number of states we "transit" into the consistency of ZFC ... which is certainly 'special' real-life-practicing-mathematics in some sense ... but maybe not 'special' in the sense I had in mind?
    – Bram28
    2 days ago










  • So thinking about this a little more .... "transitioning" into the consistency-of-ZFC space is pretty 'special' for sure ... and yet it doesn't feel 'special' enough to me: The proof of the unsolvability of the Halting problem seems so deeply logical that I was looking for a likewise more deeply logical barrier that we'd run into as we contemplate more and more complicated TMs ... the fact that ZFC plays such a prominent role in mathematics makes it 'special' ... but I feel not 'special' enough. So, maybe it's back to the thought that there is no deeply logical 'special' point.
    – Bram28
    2 days ago












  • I think your first sentence is a bit misleading. Any set $Hrestriction s$ is finite and hence computable, but that doesn't mean that we can actually compute it, because we don't know what program computes this particular finite set because we don't know what set it is. There are indeed concrete finite values of $s$ like 1919 for which we definitely cannot prove that it is equal to anything in particular. This is an "impossibility point" by any reasonable measure. (If you are working in a different system than ZFC the point may be elsewhere, but it will be there regardless.)
    – Mario Carneiro
    19 hours ago










  • @MarioCarneiro I disagree - we can compute it, we just don't know what program will do the job. More substantively, each specific theory hits a wall somewhere, but I don't see any reason to argue that any one theory perfectly captures the "right" situation (re: "any reasonable measure"); so the right picture is still a "sliding scale."
    – Noah Schweber
    8 hours ago



















5














For example, you can construct a Turing machine (I don't know how many states you need, but it is a finite number) that searches for a counterexample to Goldbach's conjecture, i.e. an even number $> 2$ that is not the sum of two primes, going through the even numbers one by one; for even number $n > 2$ it checks each $k$ from $2$ to $n/2$; if $k$ is prime and $n-k$ is prime it goes to the next $n$, but if it gets through all the $k$ it halts. Thus this Turing machine will halt if and only if Goldbach's conjecture is false. In order to decide whether it will halt, your analysis will need to decide Goldbach's conjecture.



And when you're done with that one, there are lots of other conjectures you could check with a Turing machine.






share|cite|improve this answer





















  • Thanks! I am guessing we can program something like this with a Turing-machines with close to 100 states ... so that gives us some measure (or at least a kind of minimum) of 'how difficult' it is to figure out the halting behavior of machines with that number of states. One of the other answers does something similar with the consistency of ZFC, which has been shown to take 1919 states at the most. Interesting!
    – Bram28
    2 days ago



















3














A potential Busy Beaver has three possibilities:




  1. It is easy to show it stops

  2. It is easy to show it never stops

  3. It is difficult to show either case


Number 1 either stops quickly, or it has a repeating pattern with an eventual flaw that causes it to stop.



Number 2 has a repeating pattern and never has a flaw, causing it to continue forever.



Number 3 is the interesting case. Its behaviour is chaotic. It might have short-term patterns, but it has no long-term patterns. Its future states can be predicted a short way without actually running the machine. There comes a certain point where its behaviour can no longer be predicted without running it. At this point you need a machine capable of emulating a Turning machine but faster. However, you will reach the same problem with this hypothetical new machine too, as long as it has finite power, which all real-world machines have.



If you improve your analysis of Busy Beavers, you can decide whether certain candidates are actually case 1 or case 2. We can think of it as a spectrum of behaviour with stopping at 0, running forever at 2, and undecidability at 1. To start with we know that 0 to 0.5 will stop (case 1) and 1.5 to 2 will run forever (case 2), with 0.5 to 1.5 being undecidable without running it (case 3). We improve our understanding of Busy Beavers. Now we know that 0 to 0.95 will stop and 1.05 to 2 will run forever, with 0.95 to 1.05 being undecidable.



At some point, there's no way to predict without running the machine whether it will halt or not. The only way to determine its behaviour is to run it, and if it stops, it usually gives you no insight you can use for other potential Busy Beavers. If it doesn't stop after $10^6$ cycles, you can try $10^7$, then $10^8$, and so on. At some point you give up without knowing whether it will stop if given enough time.



The problem is similar to drawing a Mandelbrot set. Certain points "escape" to infinity quickly, others settle into a repeating pattern quickly. The points on the boundary of the Mandelbrot set are difficult to predict either way without calculating them. There are methods to make the decision easier, but there will always be chaotic behaviour between the two easily detectable outcomes that can't be predicted.



Hopefully I've answered "why". Then "when" will be determined by your understanding of the specific problem you're trying to solve and the power of the machine you're using. Over time we can eat into the chaos and make it decidable, but it grows much faster than we can ever solve.






share|cite|improve this answer





















  • So basically a universal computer is a kind of "useful discrete chaos", then? Interesting, but seems to make sense on a certain level.
    – The_Sympathizer
    yesterday



















-4














Part of the confusion is that it's not that there isn't a turing machine or a process to solve each case and determine whether it halts or not. After all, the information exists in theory. A machine either halts or doesn't so in theory for any case $n$ there does in fact exist a theoretical lookup table for each of those $n$-state machines. However, there is nothing special there. It's a simple statement of fact. Since such a table exists a machine can be made by doing simple graph recognition.



The problem arises when we consider that the machine needs to be able to handle all $n$ and that the number is unbounded. The general reasoning is that more and more memory is needed to process these turing machines and to determine whether or not they halt. That and that depending on the method the halting problem solver is effectively solving the same thing that turing machine is solving.



Building on the previous paragraph the intuitive reason why the halting problem cannot be solved with a turing machine is straight-forward. We have a finite amount of memory and time. If we could solve the halting problem we could solve any problem that involves determining whether or not the computation will end. In fact, it would mean we can solve all semi-decidable problems including the hailstone problem among others. But then for those times we know infinite loops will always occur, we deem them undecidable. I do not know for sure but I believe a proof exists that if all semi-decidable problems were decidable then all undecidable problems would be decidable.



Since we would also have a magic algorithm to say whether or not some machine terminates we could also validate any theorem on the integers by having it terminate if false for some case.



In other words if a turing machine could solve the halting problem it could compute anything and solve any mathematical problem.



In particular, Legendre's conjecture, the Riemann Hypothesis (through some equivalences), and the Collatz Conjecture would all be solved pretty much overnight.



The fact that we haven't done this already shows it isn't possible.



However, I will point out that a computer has a finite amount of memory (in particular a $2^{64}$ byte memory array) and therefore does automatically qualify as a finite state machine in most cases. Therefore there does in fact exist an algorithm to determine whether or not a computer program halts with a known finite input on a 64-bit system. Do I know what it is? Definitely not off the top of my head, but it does technically exist.






share|cite|improve this answer

















  • 4




    This doesn't answer the OP's question - they already know that the halting problem is unsolvable. Also, "Since we would also have a magic algorithm to say whether or not some machine terminates we could also validate any theorem on the integers by having it terminate if false for some case. In other words if a turing machine could solve the halting problem it could compute anything and solve any mathematical problem." is extremely false, and for example the Collatz conjecture cannot (so far as we know) be reduced to a "halting question."
    – Noah Schweber
    2 days ago










  • @NoahSchweber They ask for an intuitive reason why it is true and also why the busy beaver problem isn't a valid way to solve that case. And yes the Collatz conjecture would be solvable in that case as one would iterate over the integers and test whether the repeated iteration of the Collatz Copnjecture would terminate. Since that is turing-solvable under the assumption that the halting problem is solved then one could check whether the iteration through all the integers would ever halt at a counter example.
    – The Great Duck
    2 days ago










  • @NoahSchweber however, you may be correct in that nested halting problems cannot be rephrased as one halting problem, but it isn't relevant to my point here.
    – The Great Duck
    2 days ago










  • @NoahSchweber No, you are wrong. The statement was that "if a turing machine could solve the halting problem" then "it could solve the collatz conjecture". Such a machine can in fact solve the collatz conjecture. It simply doesn't exist.
    – The Great Duck
    2 days ago






  • 2




    @TheGreatDuck It's silly in the sense that if you assume a contradiction is true, then you can trivially prove that any statement is both true and false at the same time!
    – alephzero
    yesterday











Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3053345%2fexactly-when-and-why-can-a-turing-machine-not-solve-the-halting-problem%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























5 Answers
5






active

oldest

votes








5 Answers
5






active

oldest

votes









active

oldest

votes






active

oldest

votes









32














I think the following portion from your question is most important:




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?




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:




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?




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!






share|cite|improve this answer



















  • 1




    Someone can find a theory T that is "obviously consistent" and does prove an explicit upper bound for $Sigma(1919)$ ? If T,ZFC both are consistent then T is stronger than ZFC since it will prove ZFC is consistent.
    – reuns
    2 days ago








  • 3




    @Bram28 Yes, if there is a contradiction in ZFC, this Turing machine will find it and halt. On the other hand, if the Turing machine halts, then it has found a contradiction in ZFC and ZFC is inconsistent. Therefore, this is a biconditional statement.
    – Noble Mushtak
    2 days ago






  • 1




    @Bram28 And continuing Noble's comment, this equivalence - appropriately phrased in the language of arithmetic - is provable in PA, and indeed much less.
    – Noah Schweber
    2 days ago






  • 4




    @NobleMushtak: NBG is known to be equiconsistent with ZFC, so looking for an inconsistency of either of them is basically the same task. (I don't know for sure, but I could imagine the optimizations necessary for cramming it into 1919 states involve much more drastic reformulations of the system anyway). NF versus ZFC would be a different matter ...
    – Henning Makholm
    yesterday








  • 2




    @Bram28 : Currently 1919 is special. But, in 2016, this special number was 7918. (I know the paper I cite had led to work condensing the machine to fewer states and that there was success. I do not know if the 1919 result follows from that chain of work or possibly a different chain of work.) So, tomorrow, someone could show that the TM can be condensed to a 500 state machine, or to a 5 state machine? This is currently unknown. It may be unknowable how small a machine does this computation -- what is the intrinsic entropy of a computation?
    – Eric Towers
    yesterday
















32














I think the following portion from your question is most important:




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?




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:




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?




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!






share|cite|improve this answer



















  • 1




    Someone can find a theory T that is "obviously consistent" and does prove an explicit upper bound for $Sigma(1919)$ ? If T,ZFC both are consistent then T is stronger than ZFC since it will prove ZFC is consistent.
    – reuns
    2 days ago








  • 3




    @Bram28 Yes, if there is a contradiction in ZFC, this Turing machine will find it and halt. On the other hand, if the Turing machine halts, then it has found a contradiction in ZFC and ZFC is inconsistent. Therefore, this is a biconditional statement.
    – Noble Mushtak
    2 days ago






  • 1




    @Bram28 And continuing Noble's comment, this equivalence - appropriately phrased in the language of arithmetic - is provable in PA, and indeed much less.
    – Noah Schweber
    2 days ago






  • 4




    @NobleMushtak: NBG is known to be equiconsistent with ZFC, so looking for an inconsistency of either of them is basically the same task. (I don't know for sure, but I could imagine the optimizations necessary for cramming it into 1919 states involve much more drastic reformulations of the system anyway). NF versus ZFC would be a different matter ...
    – Henning Makholm
    yesterday








  • 2




    @Bram28 : Currently 1919 is special. But, in 2016, this special number was 7918. (I know the paper I cite had led to work condensing the machine to fewer states and that there was success. I do not know if the 1919 result follows from that chain of work or possibly a different chain of work.) So, tomorrow, someone could show that the TM can be condensed to a 500 state machine, or to a 5 state machine? This is currently unknown. It may be unknowable how small a machine does this computation -- what is the intrinsic entropy of a computation?
    – Eric Towers
    yesterday














32












32








32






I think the following portion from your question is most important:




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?




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:




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?




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!






share|cite|improve this answer














I think the following portion from your question is most important:




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?




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:




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?




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!







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited 2 days ago

























answered 2 days ago









Noble Mushtak

13.9k1734




13.9k1734








  • 1




    Someone can find a theory T that is "obviously consistent" and does prove an explicit upper bound for $Sigma(1919)$ ? If T,ZFC both are consistent then T is stronger than ZFC since it will prove ZFC is consistent.
    – reuns
    2 days ago








  • 3




    @Bram28 Yes, if there is a contradiction in ZFC, this Turing machine will find it and halt. On the other hand, if the Turing machine halts, then it has found a contradiction in ZFC and ZFC is inconsistent. Therefore, this is a biconditional statement.
    – Noble Mushtak
    2 days ago






  • 1




    @Bram28 And continuing Noble's comment, this equivalence - appropriately phrased in the language of arithmetic - is provable in PA, and indeed much less.
    – Noah Schweber
    2 days ago






  • 4




    @NobleMushtak: NBG is known to be equiconsistent with ZFC, so looking for an inconsistency of either of them is basically the same task. (I don't know for sure, but I could imagine the optimizations necessary for cramming it into 1919 states involve much more drastic reformulations of the system anyway). NF versus ZFC would be a different matter ...
    – Henning Makholm
    yesterday








  • 2




    @Bram28 : Currently 1919 is special. But, in 2016, this special number was 7918. (I know the paper I cite had led to work condensing the machine to fewer states and that there was success. I do not know if the 1919 result follows from that chain of work or possibly a different chain of work.) So, tomorrow, someone could show that the TM can be condensed to a 500 state machine, or to a 5 state machine? This is currently unknown. It may be unknowable how small a machine does this computation -- what is the intrinsic entropy of a computation?
    – Eric Towers
    yesterday














  • 1




    Someone can find a theory T that is "obviously consistent" and does prove an explicit upper bound for $Sigma(1919)$ ? If T,ZFC both are consistent then T is stronger than ZFC since it will prove ZFC is consistent.
    – reuns
    2 days ago








  • 3




    @Bram28 Yes, if there is a contradiction in ZFC, this Turing machine will find it and halt. On the other hand, if the Turing machine halts, then it has found a contradiction in ZFC and ZFC is inconsistent. Therefore, this is a biconditional statement.
    – Noble Mushtak
    2 days ago






  • 1




    @Bram28 And continuing Noble's comment, this equivalence - appropriately phrased in the language of arithmetic - is provable in PA, and indeed much less.
    – Noah Schweber
    2 days ago






  • 4




    @NobleMushtak: NBG is known to be equiconsistent with ZFC, so looking for an inconsistency of either of them is basically the same task. (I don't know for sure, but I could imagine the optimizations necessary for cramming it into 1919 states involve much more drastic reformulations of the system anyway). NF versus ZFC would be a different matter ...
    – Henning Makholm
    yesterday








  • 2




    @Bram28 : Currently 1919 is special. But, in 2016, this special number was 7918. (I know the paper I cite had led to work condensing the machine to fewer states and that there was success. I do not know if the 1919 result follows from that chain of work or possibly a different chain of work.) So, tomorrow, someone could show that the TM can be condensed to a 500 state machine, or to a 5 state machine? This is currently unknown. It may be unknowable how small a machine does this computation -- what is the intrinsic entropy of a computation?
    – Eric Towers
    yesterday








1




1




Someone can find a theory T that is "obviously consistent" and does prove an explicit upper bound for $Sigma(1919)$ ? If T,ZFC both are consistent then T is stronger than ZFC since it will prove ZFC is consistent.
– reuns
2 days ago






Someone can find a theory T that is "obviously consistent" and does prove an explicit upper bound for $Sigma(1919)$ ? If T,ZFC both are consistent then T is stronger than ZFC since it will prove ZFC is consistent.
– reuns
2 days ago






3




3




@Bram28 Yes, if there is a contradiction in ZFC, this Turing machine will find it and halt. On the other hand, if the Turing machine halts, then it has found a contradiction in ZFC and ZFC is inconsistent. Therefore, this is a biconditional statement.
– Noble Mushtak
2 days ago




@Bram28 Yes, if there is a contradiction in ZFC, this Turing machine will find it and halt. On the other hand, if the Turing machine halts, then it has found a contradiction in ZFC and ZFC is inconsistent. Therefore, this is a biconditional statement.
– Noble Mushtak
2 days ago




1




1




@Bram28 And continuing Noble's comment, this equivalence - appropriately phrased in the language of arithmetic - is provable in PA, and indeed much less.
– Noah Schweber
2 days ago




@Bram28 And continuing Noble's comment, this equivalence - appropriately phrased in the language of arithmetic - is provable in PA, and indeed much less.
– Noah Schweber
2 days ago




4




4




@NobleMushtak: NBG is known to be equiconsistent with ZFC, so looking for an inconsistency of either of them is basically the same task. (I don't know for sure, but I could imagine the optimizations necessary for cramming it into 1919 states involve much more drastic reformulations of the system anyway). NF versus ZFC would be a different matter ...
– Henning Makholm
yesterday






@NobleMushtak: NBG is known to be equiconsistent with ZFC, so looking for an inconsistency of either of them is basically the same task. (I don't know for sure, but I could imagine the optimizations necessary for cramming it into 1919 states involve much more drastic reformulations of the system anyway). NF versus ZFC would be a different matter ...
– Henning Makholm
yesterday






2




2




@Bram28 : Currently 1919 is special. But, in 2016, this special number was 7918. (I know the paper I cite had led to work condensing the machine to fewer states and that there was success. I do not know if the 1919 result follows from that chain of work or possibly a different chain of work.) So, tomorrow, someone could show that the TM can be condensed to a 500 state machine, or to a 5 state machine? This is currently unknown. It may be unknowable how small a machine does this computation -- what is the intrinsic entropy of a computation?
– Eric Towers
yesterday




@Bram28 : Currently 1919 is special. But, in 2016, this special number was 7918. (I know the paper I cite had led to work condensing the machine to fewer states and that there was success. I do not know if the 1919 result follows from that chain of work or possibly a different chain of work.) So, tomorrow, someone could show that the TM can be condensed to a 500 state machine, or to a 5 state machine? This is currently unknown. It may be unknowable how small a machine does this computation -- what is the intrinsic entropy of a computation?
– Eric Towers
yesterday











10














Since, as you observe, any finite amount of the halting problem - that is, any set of the form $Hupharpoonright s:={x<s:Phi_x(x)downarrow}$ - is computable, there isn't any particular sharp impossibility point. There are some interesting "phase transitions" which appear relevant - e.g. at a certain point we hit our first universal machine - but I don't know of any which have any claim to be the point where the halting problem becomes noncomputable.



On the other hand, as you also observe the way in which the $Hupharpoonright s$s are computable is non-uniform (otherwise, the whole halting problem would be computable). So we can try to measure this "ongoing complexity." There are two, to my mind, natural approaches:




  • Given $n$, how up up the "hierarchy of theories" - from fragments of PA, to fragments of $Z_2$, to fragments of ZFC, to ZFC + large cardinals - do we have to go to get a theory which can decide whether each of the first $n$ Turing machines halts on input $0$?


  • Given $n$, how complicated is the finite string consisting of the first $n$ bits of the characteristic function of the halting problem (call this string "$eta_n$")?



Of these two approaches, the first has some draw which the second lacks, but it's also far more vague and limited. The second winds up leading to a very rich theory, namely the theory of Kolmogorov complexity (and its attendant notions, like algorithmic randomness), and also partially subsumes the former question. So I think that's my answer to your question: ultimately you won't find a sharp transition point, but the study of the dynamic behavior of the complexity of the halting problem is quite rewarding.






share|cite|improve this answer





















  • Thanks Noah! ... a little over my head .. though I like your "phase transitions" notion .... from one of the other answers I gather that indeed for some number of states we "transit" into the consistency of ZFC ... which is certainly 'special' real-life-practicing-mathematics in some sense ... but maybe not 'special' in the sense I had in mind?
    – Bram28
    2 days ago










  • So thinking about this a little more .... "transitioning" into the consistency-of-ZFC space is pretty 'special' for sure ... and yet it doesn't feel 'special' enough to me: The proof of the unsolvability of the Halting problem seems so deeply logical that I was looking for a likewise more deeply logical barrier that we'd run into as we contemplate more and more complicated TMs ... the fact that ZFC plays such a prominent role in mathematics makes it 'special' ... but I feel not 'special' enough. So, maybe it's back to the thought that there is no deeply logical 'special' point.
    – Bram28
    2 days ago












  • I think your first sentence is a bit misleading. Any set $Hrestriction s$ is finite and hence computable, but that doesn't mean that we can actually compute it, because we don't know what program computes this particular finite set because we don't know what set it is. There are indeed concrete finite values of $s$ like 1919 for which we definitely cannot prove that it is equal to anything in particular. This is an "impossibility point" by any reasonable measure. (If you are working in a different system than ZFC the point may be elsewhere, but it will be there regardless.)
    – Mario Carneiro
    19 hours ago










  • @MarioCarneiro I disagree - we can compute it, we just don't know what program will do the job. More substantively, each specific theory hits a wall somewhere, but I don't see any reason to argue that any one theory perfectly captures the "right" situation (re: "any reasonable measure"); so the right picture is still a "sliding scale."
    – Noah Schweber
    8 hours ago
















10














Since, as you observe, any finite amount of the halting problem - that is, any set of the form $Hupharpoonright s:={x<s:Phi_x(x)downarrow}$ - is computable, there isn't any particular sharp impossibility point. There are some interesting "phase transitions" which appear relevant - e.g. at a certain point we hit our first universal machine - but I don't know of any which have any claim to be the point where the halting problem becomes noncomputable.



On the other hand, as you also observe the way in which the $Hupharpoonright s$s are computable is non-uniform (otherwise, the whole halting problem would be computable). So we can try to measure this "ongoing complexity." There are two, to my mind, natural approaches:




  • Given $n$, how up up the "hierarchy of theories" - from fragments of PA, to fragments of $Z_2$, to fragments of ZFC, to ZFC + large cardinals - do we have to go to get a theory which can decide whether each of the first $n$ Turing machines halts on input $0$?


  • Given $n$, how complicated is the finite string consisting of the first $n$ bits of the characteristic function of the halting problem (call this string "$eta_n$")?



Of these two approaches, the first has some draw which the second lacks, but it's also far more vague and limited. The second winds up leading to a very rich theory, namely the theory of Kolmogorov complexity (and its attendant notions, like algorithmic randomness), and also partially subsumes the former question. So I think that's my answer to your question: ultimately you won't find a sharp transition point, but the study of the dynamic behavior of the complexity of the halting problem is quite rewarding.






share|cite|improve this answer





















  • Thanks Noah! ... a little over my head .. though I like your "phase transitions" notion .... from one of the other answers I gather that indeed for some number of states we "transit" into the consistency of ZFC ... which is certainly 'special' real-life-practicing-mathematics in some sense ... but maybe not 'special' in the sense I had in mind?
    – Bram28
    2 days ago










  • So thinking about this a little more .... "transitioning" into the consistency-of-ZFC space is pretty 'special' for sure ... and yet it doesn't feel 'special' enough to me: The proof of the unsolvability of the Halting problem seems so deeply logical that I was looking for a likewise more deeply logical barrier that we'd run into as we contemplate more and more complicated TMs ... the fact that ZFC plays such a prominent role in mathematics makes it 'special' ... but I feel not 'special' enough. So, maybe it's back to the thought that there is no deeply logical 'special' point.
    – Bram28
    2 days ago












  • I think your first sentence is a bit misleading. Any set $Hrestriction s$ is finite and hence computable, but that doesn't mean that we can actually compute it, because we don't know what program computes this particular finite set because we don't know what set it is. There are indeed concrete finite values of $s$ like 1919 for which we definitely cannot prove that it is equal to anything in particular. This is an "impossibility point" by any reasonable measure. (If you are working in a different system than ZFC the point may be elsewhere, but it will be there regardless.)
    – Mario Carneiro
    19 hours ago










  • @MarioCarneiro I disagree - we can compute it, we just don't know what program will do the job. More substantively, each specific theory hits a wall somewhere, but I don't see any reason to argue that any one theory perfectly captures the "right" situation (re: "any reasonable measure"); so the right picture is still a "sliding scale."
    – Noah Schweber
    8 hours ago














10












10








10






Since, as you observe, any finite amount of the halting problem - that is, any set of the form $Hupharpoonright s:={x<s:Phi_x(x)downarrow}$ - is computable, there isn't any particular sharp impossibility point. There are some interesting "phase transitions" which appear relevant - e.g. at a certain point we hit our first universal machine - but I don't know of any which have any claim to be the point where the halting problem becomes noncomputable.



On the other hand, as you also observe the way in which the $Hupharpoonright s$s are computable is non-uniform (otherwise, the whole halting problem would be computable). So we can try to measure this "ongoing complexity." There are two, to my mind, natural approaches:




  • Given $n$, how up up the "hierarchy of theories" - from fragments of PA, to fragments of $Z_2$, to fragments of ZFC, to ZFC + large cardinals - do we have to go to get a theory which can decide whether each of the first $n$ Turing machines halts on input $0$?


  • Given $n$, how complicated is the finite string consisting of the first $n$ bits of the characteristic function of the halting problem (call this string "$eta_n$")?



Of these two approaches, the first has some draw which the second lacks, but it's also far more vague and limited. The second winds up leading to a very rich theory, namely the theory of Kolmogorov complexity (and its attendant notions, like algorithmic randomness), and also partially subsumes the former question. So I think that's my answer to your question: ultimately you won't find a sharp transition point, but the study of the dynamic behavior of the complexity of the halting problem is quite rewarding.






share|cite|improve this answer












Since, as you observe, any finite amount of the halting problem - that is, any set of the form $Hupharpoonright s:={x<s:Phi_x(x)downarrow}$ - is computable, there isn't any particular sharp impossibility point. There are some interesting "phase transitions" which appear relevant - e.g. at a certain point we hit our first universal machine - but I don't know of any which have any claim to be the point where the halting problem becomes noncomputable.



On the other hand, as you also observe the way in which the $Hupharpoonright s$s are computable is non-uniform (otherwise, the whole halting problem would be computable). So we can try to measure this "ongoing complexity." There are two, to my mind, natural approaches:




  • Given $n$, how up up the "hierarchy of theories" - from fragments of PA, to fragments of $Z_2$, to fragments of ZFC, to ZFC + large cardinals - do we have to go to get a theory which can decide whether each of the first $n$ Turing machines halts on input $0$?


  • Given $n$, how complicated is the finite string consisting of the first $n$ bits of the characteristic function of the halting problem (call this string "$eta_n$")?



Of these two approaches, the first has some draw which the second lacks, but it's also far more vague and limited. The second winds up leading to a very rich theory, namely the theory of Kolmogorov complexity (and its attendant notions, like algorithmic randomness), and also partially subsumes the former question. So I think that's my answer to your question: ultimately you won't find a sharp transition point, but the study of the dynamic behavior of the complexity of the halting problem is quite rewarding.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered 2 days ago









Noah Schweber

121k10147283




121k10147283












  • Thanks Noah! ... a little over my head .. though I like your "phase transitions" notion .... from one of the other answers I gather that indeed for some number of states we "transit" into the consistency of ZFC ... which is certainly 'special' real-life-practicing-mathematics in some sense ... but maybe not 'special' in the sense I had in mind?
    – Bram28
    2 days ago










  • So thinking about this a little more .... "transitioning" into the consistency-of-ZFC space is pretty 'special' for sure ... and yet it doesn't feel 'special' enough to me: The proof of the unsolvability of the Halting problem seems so deeply logical that I was looking for a likewise more deeply logical barrier that we'd run into as we contemplate more and more complicated TMs ... the fact that ZFC plays such a prominent role in mathematics makes it 'special' ... but I feel not 'special' enough. So, maybe it's back to the thought that there is no deeply logical 'special' point.
    – Bram28
    2 days ago












  • I think your first sentence is a bit misleading. Any set $Hrestriction s$ is finite and hence computable, but that doesn't mean that we can actually compute it, because we don't know what program computes this particular finite set because we don't know what set it is. There are indeed concrete finite values of $s$ like 1919 for which we definitely cannot prove that it is equal to anything in particular. This is an "impossibility point" by any reasonable measure. (If you are working in a different system than ZFC the point may be elsewhere, but it will be there regardless.)
    – Mario Carneiro
    19 hours ago










  • @MarioCarneiro I disagree - we can compute it, we just don't know what program will do the job. More substantively, each specific theory hits a wall somewhere, but I don't see any reason to argue that any one theory perfectly captures the "right" situation (re: "any reasonable measure"); so the right picture is still a "sliding scale."
    – Noah Schweber
    8 hours ago


















  • Thanks Noah! ... a little over my head .. though I like your "phase transitions" notion .... from one of the other answers I gather that indeed for some number of states we "transit" into the consistency of ZFC ... which is certainly 'special' real-life-practicing-mathematics in some sense ... but maybe not 'special' in the sense I had in mind?
    – Bram28
    2 days ago










  • So thinking about this a little more .... "transitioning" into the consistency-of-ZFC space is pretty 'special' for sure ... and yet it doesn't feel 'special' enough to me: The proof of the unsolvability of the Halting problem seems so deeply logical that I was looking for a likewise more deeply logical barrier that we'd run into as we contemplate more and more complicated TMs ... the fact that ZFC plays such a prominent role in mathematics makes it 'special' ... but I feel not 'special' enough. So, maybe it's back to the thought that there is no deeply logical 'special' point.
    – Bram28
    2 days ago












  • I think your first sentence is a bit misleading. Any set $Hrestriction s$ is finite and hence computable, but that doesn't mean that we can actually compute it, because we don't know what program computes this particular finite set because we don't know what set it is. There are indeed concrete finite values of $s$ like 1919 for which we definitely cannot prove that it is equal to anything in particular. This is an "impossibility point" by any reasonable measure. (If you are working in a different system than ZFC the point may be elsewhere, but it will be there regardless.)
    – Mario Carneiro
    19 hours ago










  • @MarioCarneiro I disagree - we can compute it, we just don't know what program will do the job. More substantively, each specific theory hits a wall somewhere, but I don't see any reason to argue that any one theory perfectly captures the "right" situation (re: "any reasonable measure"); so the right picture is still a "sliding scale."
    – Noah Schweber
    8 hours ago
















Thanks Noah! ... a little over my head .. though I like your "phase transitions" notion .... from one of the other answers I gather that indeed for some number of states we "transit" into the consistency of ZFC ... which is certainly 'special' real-life-practicing-mathematics in some sense ... but maybe not 'special' in the sense I had in mind?
– Bram28
2 days ago




Thanks Noah! ... a little over my head .. though I like your "phase transitions" notion .... from one of the other answers I gather that indeed for some number of states we "transit" into the consistency of ZFC ... which is certainly 'special' real-life-practicing-mathematics in some sense ... but maybe not 'special' in the sense I had in mind?
– Bram28
2 days ago












So thinking about this a little more .... "transitioning" into the consistency-of-ZFC space is pretty 'special' for sure ... and yet it doesn't feel 'special' enough to me: The proof of the unsolvability of the Halting problem seems so deeply logical that I was looking for a likewise more deeply logical barrier that we'd run into as we contemplate more and more complicated TMs ... the fact that ZFC plays such a prominent role in mathematics makes it 'special' ... but I feel not 'special' enough. So, maybe it's back to the thought that there is no deeply logical 'special' point.
– Bram28
2 days ago






So thinking about this a little more .... "transitioning" into the consistency-of-ZFC space is pretty 'special' for sure ... and yet it doesn't feel 'special' enough to me: The proof of the unsolvability of the Halting problem seems so deeply logical that I was looking for a likewise more deeply logical barrier that we'd run into as we contemplate more and more complicated TMs ... the fact that ZFC plays such a prominent role in mathematics makes it 'special' ... but I feel not 'special' enough. So, maybe it's back to the thought that there is no deeply logical 'special' point.
– Bram28
2 days ago














I think your first sentence is a bit misleading. Any set $Hrestriction s$ is finite and hence computable, but that doesn't mean that we can actually compute it, because we don't know what program computes this particular finite set because we don't know what set it is. There are indeed concrete finite values of $s$ like 1919 for which we definitely cannot prove that it is equal to anything in particular. This is an "impossibility point" by any reasonable measure. (If you are working in a different system than ZFC the point may be elsewhere, but it will be there regardless.)
– Mario Carneiro
19 hours ago




I think your first sentence is a bit misleading. Any set $Hrestriction s$ is finite and hence computable, but that doesn't mean that we can actually compute it, because we don't know what program computes this particular finite set because we don't know what set it is. There are indeed concrete finite values of $s$ like 1919 for which we definitely cannot prove that it is equal to anything in particular. This is an "impossibility point" by any reasonable measure. (If you are working in a different system than ZFC the point may be elsewhere, but it will be there regardless.)
– Mario Carneiro
19 hours ago












@MarioCarneiro I disagree - we can compute it, we just don't know what program will do the job. More substantively, each specific theory hits a wall somewhere, but I don't see any reason to argue that any one theory perfectly captures the "right" situation (re: "any reasonable measure"); so the right picture is still a "sliding scale."
– Noah Schweber
8 hours ago




@MarioCarneiro I disagree - we can compute it, we just don't know what program will do the job. More substantively, each specific theory hits a wall somewhere, but I don't see any reason to argue that any one theory perfectly captures the "right" situation (re: "any reasonable measure"); so the right picture is still a "sliding scale."
– Noah Schweber
8 hours ago











5














For example, you can construct a Turing machine (I don't know how many states you need, but it is a finite number) that searches for a counterexample to Goldbach's conjecture, i.e. an even number $> 2$ that is not the sum of two primes, going through the even numbers one by one; for even number $n > 2$ it checks each $k$ from $2$ to $n/2$; if $k$ is prime and $n-k$ is prime it goes to the next $n$, but if it gets through all the $k$ it halts. Thus this Turing machine will halt if and only if Goldbach's conjecture is false. In order to decide whether it will halt, your analysis will need to decide Goldbach's conjecture.



And when you're done with that one, there are lots of other conjectures you could check with a Turing machine.






share|cite|improve this answer





















  • Thanks! I am guessing we can program something like this with a Turing-machines with close to 100 states ... so that gives us some measure (or at least a kind of minimum) of 'how difficult' it is to figure out the halting behavior of machines with that number of states. One of the other answers does something similar with the consistency of ZFC, which has been shown to take 1919 states at the most. Interesting!
    – Bram28
    2 days ago
















5














For example, you can construct a Turing machine (I don't know how many states you need, but it is a finite number) that searches for a counterexample to Goldbach's conjecture, i.e. an even number $> 2$ that is not the sum of two primes, going through the even numbers one by one; for even number $n > 2$ it checks each $k$ from $2$ to $n/2$; if $k$ is prime and $n-k$ is prime it goes to the next $n$, but if it gets through all the $k$ it halts. Thus this Turing machine will halt if and only if Goldbach's conjecture is false. In order to decide whether it will halt, your analysis will need to decide Goldbach's conjecture.



And when you're done with that one, there are lots of other conjectures you could check with a Turing machine.






share|cite|improve this answer





















  • Thanks! I am guessing we can program something like this with a Turing-machines with close to 100 states ... so that gives us some measure (or at least a kind of minimum) of 'how difficult' it is to figure out the halting behavior of machines with that number of states. One of the other answers does something similar with the consistency of ZFC, which has been shown to take 1919 states at the most. Interesting!
    – Bram28
    2 days ago














5












5








5






For example, you can construct a Turing machine (I don't know how many states you need, but it is a finite number) that searches for a counterexample to Goldbach's conjecture, i.e. an even number $> 2$ that is not the sum of two primes, going through the even numbers one by one; for even number $n > 2$ it checks each $k$ from $2$ to $n/2$; if $k$ is prime and $n-k$ is prime it goes to the next $n$, but if it gets through all the $k$ it halts. Thus this Turing machine will halt if and only if Goldbach's conjecture is false. In order to decide whether it will halt, your analysis will need to decide Goldbach's conjecture.



And when you're done with that one, there are lots of other conjectures you could check with a Turing machine.






share|cite|improve this answer












For example, you can construct a Turing machine (I don't know how many states you need, but it is a finite number) that searches for a counterexample to Goldbach's conjecture, i.e. an even number $> 2$ that is not the sum of two primes, going through the even numbers one by one; for even number $n > 2$ it checks each $k$ from $2$ to $n/2$; if $k$ is prime and $n-k$ is prime it goes to the next $n$, but if it gets through all the $k$ it halts. Thus this Turing machine will halt if and only if Goldbach's conjecture is false. In order to decide whether it will halt, your analysis will need to decide Goldbach's conjecture.



And when you're done with that one, there are lots of other conjectures you could check with a Turing machine.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered 2 days ago









Robert Israel

318k23207458




318k23207458












  • Thanks! I am guessing we can program something like this with a Turing-machines with close to 100 states ... so that gives us some measure (or at least a kind of minimum) of 'how difficult' it is to figure out the halting behavior of machines with that number of states. One of the other answers does something similar with the consistency of ZFC, which has been shown to take 1919 states at the most. Interesting!
    – Bram28
    2 days ago


















  • Thanks! I am guessing we can program something like this with a Turing-machines with close to 100 states ... so that gives us some measure (or at least a kind of minimum) of 'how difficult' it is to figure out the halting behavior of machines with that number of states. One of the other answers does something similar with the consistency of ZFC, which has been shown to take 1919 states at the most. Interesting!
    – Bram28
    2 days ago
















Thanks! I am guessing we can program something like this with a Turing-machines with close to 100 states ... so that gives us some measure (or at least a kind of minimum) of 'how difficult' it is to figure out the halting behavior of machines with that number of states. One of the other answers does something similar with the consistency of ZFC, which has been shown to take 1919 states at the most. Interesting!
– Bram28
2 days ago




Thanks! I am guessing we can program something like this with a Turing-machines with close to 100 states ... so that gives us some measure (or at least a kind of minimum) of 'how difficult' it is to figure out the halting behavior of machines with that number of states. One of the other answers does something similar with the consistency of ZFC, which has been shown to take 1919 states at the most. Interesting!
– Bram28
2 days ago











3














A potential Busy Beaver has three possibilities:




  1. It is easy to show it stops

  2. It is easy to show it never stops

  3. It is difficult to show either case


Number 1 either stops quickly, or it has a repeating pattern with an eventual flaw that causes it to stop.



Number 2 has a repeating pattern and never has a flaw, causing it to continue forever.



Number 3 is the interesting case. Its behaviour is chaotic. It might have short-term patterns, but it has no long-term patterns. Its future states can be predicted a short way without actually running the machine. There comes a certain point where its behaviour can no longer be predicted without running it. At this point you need a machine capable of emulating a Turning machine but faster. However, you will reach the same problem with this hypothetical new machine too, as long as it has finite power, which all real-world machines have.



If you improve your analysis of Busy Beavers, you can decide whether certain candidates are actually case 1 or case 2. We can think of it as a spectrum of behaviour with stopping at 0, running forever at 2, and undecidability at 1. To start with we know that 0 to 0.5 will stop (case 1) and 1.5 to 2 will run forever (case 2), with 0.5 to 1.5 being undecidable without running it (case 3). We improve our understanding of Busy Beavers. Now we know that 0 to 0.95 will stop and 1.05 to 2 will run forever, with 0.95 to 1.05 being undecidable.



At some point, there's no way to predict without running the machine whether it will halt or not. The only way to determine its behaviour is to run it, and if it stops, it usually gives you no insight you can use for other potential Busy Beavers. If it doesn't stop after $10^6$ cycles, you can try $10^7$, then $10^8$, and so on. At some point you give up without knowing whether it will stop if given enough time.



The problem is similar to drawing a Mandelbrot set. Certain points "escape" to infinity quickly, others settle into a repeating pattern quickly. The points on the boundary of the Mandelbrot set are difficult to predict either way without calculating them. There are methods to make the decision easier, but there will always be chaotic behaviour between the two easily detectable outcomes that can't be predicted.



Hopefully I've answered "why". Then "when" will be determined by your understanding of the specific problem you're trying to solve and the power of the machine you're using. Over time we can eat into the chaos and make it decidable, but it grows much faster than we can ever solve.






share|cite|improve this answer





















  • So basically a universal computer is a kind of "useful discrete chaos", then? Interesting, but seems to make sense on a certain level.
    – The_Sympathizer
    yesterday
















3














A potential Busy Beaver has three possibilities:




  1. It is easy to show it stops

  2. It is easy to show it never stops

  3. It is difficult to show either case


Number 1 either stops quickly, or it has a repeating pattern with an eventual flaw that causes it to stop.



Number 2 has a repeating pattern and never has a flaw, causing it to continue forever.



Number 3 is the interesting case. Its behaviour is chaotic. It might have short-term patterns, but it has no long-term patterns. Its future states can be predicted a short way without actually running the machine. There comes a certain point where its behaviour can no longer be predicted without running it. At this point you need a machine capable of emulating a Turning machine but faster. However, you will reach the same problem with this hypothetical new machine too, as long as it has finite power, which all real-world machines have.



If you improve your analysis of Busy Beavers, you can decide whether certain candidates are actually case 1 or case 2. We can think of it as a spectrum of behaviour with stopping at 0, running forever at 2, and undecidability at 1. To start with we know that 0 to 0.5 will stop (case 1) and 1.5 to 2 will run forever (case 2), with 0.5 to 1.5 being undecidable without running it (case 3). We improve our understanding of Busy Beavers. Now we know that 0 to 0.95 will stop and 1.05 to 2 will run forever, with 0.95 to 1.05 being undecidable.



At some point, there's no way to predict without running the machine whether it will halt or not. The only way to determine its behaviour is to run it, and if it stops, it usually gives you no insight you can use for other potential Busy Beavers. If it doesn't stop after $10^6$ cycles, you can try $10^7$, then $10^8$, and so on. At some point you give up without knowing whether it will stop if given enough time.



The problem is similar to drawing a Mandelbrot set. Certain points "escape" to infinity quickly, others settle into a repeating pattern quickly. The points on the boundary of the Mandelbrot set are difficult to predict either way without calculating them. There are methods to make the decision easier, but there will always be chaotic behaviour between the two easily detectable outcomes that can't be predicted.



Hopefully I've answered "why". Then "when" will be determined by your understanding of the specific problem you're trying to solve and the power of the machine you're using. Over time we can eat into the chaos and make it decidable, but it grows much faster than we can ever solve.






share|cite|improve this answer





















  • So basically a universal computer is a kind of "useful discrete chaos", then? Interesting, but seems to make sense on a certain level.
    – The_Sympathizer
    yesterday














3












3








3






A potential Busy Beaver has three possibilities:




  1. It is easy to show it stops

  2. It is easy to show it never stops

  3. It is difficult to show either case


Number 1 either stops quickly, or it has a repeating pattern with an eventual flaw that causes it to stop.



Number 2 has a repeating pattern and never has a flaw, causing it to continue forever.



Number 3 is the interesting case. Its behaviour is chaotic. It might have short-term patterns, but it has no long-term patterns. Its future states can be predicted a short way without actually running the machine. There comes a certain point where its behaviour can no longer be predicted without running it. At this point you need a machine capable of emulating a Turning machine but faster. However, you will reach the same problem with this hypothetical new machine too, as long as it has finite power, which all real-world machines have.



If you improve your analysis of Busy Beavers, you can decide whether certain candidates are actually case 1 or case 2. We can think of it as a spectrum of behaviour with stopping at 0, running forever at 2, and undecidability at 1. To start with we know that 0 to 0.5 will stop (case 1) and 1.5 to 2 will run forever (case 2), with 0.5 to 1.5 being undecidable without running it (case 3). We improve our understanding of Busy Beavers. Now we know that 0 to 0.95 will stop and 1.05 to 2 will run forever, with 0.95 to 1.05 being undecidable.



At some point, there's no way to predict without running the machine whether it will halt or not. The only way to determine its behaviour is to run it, and if it stops, it usually gives you no insight you can use for other potential Busy Beavers. If it doesn't stop after $10^6$ cycles, you can try $10^7$, then $10^8$, and so on. At some point you give up without knowing whether it will stop if given enough time.



The problem is similar to drawing a Mandelbrot set. Certain points "escape" to infinity quickly, others settle into a repeating pattern quickly. The points on the boundary of the Mandelbrot set are difficult to predict either way without calculating them. There are methods to make the decision easier, but there will always be chaotic behaviour between the two easily detectable outcomes that can't be predicted.



Hopefully I've answered "why". Then "when" will be determined by your understanding of the specific problem you're trying to solve and the power of the machine you're using. Over time we can eat into the chaos and make it decidable, but it grows much faster than we can ever solve.






share|cite|improve this answer












A potential Busy Beaver has three possibilities:




  1. It is easy to show it stops

  2. It is easy to show it never stops

  3. It is difficult to show either case


Number 1 either stops quickly, or it has a repeating pattern with an eventual flaw that causes it to stop.



Number 2 has a repeating pattern and never has a flaw, causing it to continue forever.



Number 3 is the interesting case. Its behaviour is chaotic. It might have short-term patterns, but it has no long-term patterns. Its future states can be predicted a short way without actually running the machine. There comes a certain point where its behaviour can no longer be predicted without running it. At this point you need a machine capable of emulating a Turning machine but faster. However, you will reach the same problem with this hypothetical new machine too, as long as it has finite power, which all real-world machines have.



If you improve your analysis of Busy Beavers, you can decide whether certain candidates are actually case 1 or case 2. We can think of it as a spectrum of behaviour with stopping at 0, running forever at 2, and undecidability at 1. To start with we know that 0 to 0.5 will stop (case 1) and 1.5 to 2 will run forever (case 2), with 0.5 to 1.5 being undecidable without running it (case 3). We improve our understanding of Busy Beavers. Now we know that 0 to 0.95 will stop and 1.05 to 2 will run forever, with 0.95 to 1.05 being undecidable.



At some point, there's no way to predict without running the machine whether it will halt or not. The only way to determine its behaviour is to run it, and if it stops, it usually gives you no insight you can use for other potential Busy Beavers. If it doesn't stop after $10^6$ cycles, you can try $10^7$, then $10^8$, and so on. At some point you give up without knowing whether it will stop if given enough time.



The problem is similar to drawing a Mandelbrot set. Certain points "escape" to infinity quickly, others settle into a repeating pattern quickly. The points on the boundary of the Mandelbrot set are difficult to predict either way without calculating them. There are methods to make the decision easier, but there will always be chaotic behaviour between the two easily detectable outcomes that can't be predicted.



Hopefully I've answered "why". Then "when" will be determined by your understanding of the specific problem you're trying to solve and the power of the machine you're using. Over time we can eat into the chaos and make it decidable, but it grows much faster than we can ever solve.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered yesterday









CJ Dennis

467211




467211












  • So basically a universal computer is a kind of "useful discrete chaos", then? Interesting, but seems to make sense on a certain level.
    – The_Sympathizer
    yesterday


















  • So basically a universal computer is a kind of "useful discrete chaos", then? Interesting, but seems to make sense on a certain level.
    – The_Sympathizer
    yesterday
















So basically a universal computer is a kind of "useful discrete chaos", then? Interesting, but seems to make sense on a certain level.
– The_Sympathizer
yesterday




So basically a universal computer is a kind of "useful discrete chaos", then? Interesting, but seems to make sense on a certain level.
– The_Sympathizer
yesterday











-4














Part of the confusion is that it's not that there isn't a turing machine or a process to solve each case and determine whether it halts or not. After all, the information exists in theory. A machine either halts or doesn't so in theory for any case $n$ there does in fact exist a theoretical lookup table for each of those $n$-state machines. However, there is nothing special there. It's a simple statement of fact. Since such a table exists a machine can be made by doing simple graph recognition.



The problem arises when we consider that the machine needs to be able to handle all $n$ and that the number is unbounded. The general reasoning is that more and more memory is needed to process these turing machines and to determine whether or not they halt. That and that depending on the method the halting problem solver is effectively solving the same thing that turing machine is solving.



Building on the previous paragraph the intuitive reason why the halting problem cannot be solved with a turing machine is straight-forward. We have a finite amount of memory and time. If we could solve the halting problem we could solve any problem that involves determining whether or not the computation will end. In fact, it would mean we can solve all semi-decidable problems including the hailstone problem among others. But then for those times we know infinite loops will always occur, we deem them undecidable. I do not know for sure but I believe a proof exists that if all semi-decidable problems were decidable then all undecidable problems would be decidable.



Since we would also have a magic algorithm to say whether or not some machine terminates we could also validate any theorem on the integers by having it terminate if false for some case.



In other words if a turing machine could solve the halting problem it could compute anything and solve any mathematical problem.



In particular, Legendre's conjecture, the Riemann Hypothesis (through some equivalences), and the Collatz Conjecture would all be solved pretty much overnight.



The fact that we haven't done this already shows it isn't possible.



However, I will point out that a computer has a finite amount of memory (in particular a $2^{64}$ byte memory array) and therefore does automatically qualify as a finite state machine in most cases. Therefore there does in fact exist an algorithm to determine whether or not a computer program halts with a known finite input on a 64-bit system. Do I know what it is? Definitely not off the top of my head, but it does technically exist.






share|cite|improve this answer

















  • 4




    This doesn't answer the OP's question - they already know that the halting problem is unsolvable. Also, "Since we would also have a magic algorithm to say whether or not some machine terminates we could also validate any theorem on the integers by having it terminate if false for some case. In other words if a turing machine could solve the halting problem it could compute anything and solve any mathematical problem." is extremely false, and for example the Collatz conjecture cannot (so far as we know) be reduced to a "halting question."
    – Noah Schweber
    2 days ago










  • @NoahSchweber They ask for an intuitive reason why it is true and also why the busy beaver problem isn't a valid way to solve that case. And yes the Collatz conjecture would be solvable in that case as one would iterate over the integers and test whether the repeated iteration of the Collatz Copnjecture would terminate. Since that is turing-solvable under the assumption that the halting problem is solved then one could check whether the iteration through all the integers would ever halt at a counter example.
    – The Great Duck
    2 days ago










  • @NoahSchweber however, you may be correct in that nested halting problems cannot be rephrased as one halting problem, but it isn't relevant to my point here.
    – The Great Duck
    2 days ago










  • @NoahSchweber No, you are wrong. The statement was that "if a turing machine could solve the halting problem" then "it could solve the collatz conjecture". Such a machine can in fact solve the collatz conjecture. It simply doesn't exist.
    – The Great Duck
    2 days ago






  • 2




    @TheGreatDuck It's silly in the sense that if you assume a contradiction is true, then you can trivially prove that any statement is both true and false at the same time!
    – alephzero
    yesterday
















-4














Part of the confusion is that it's not that there isn't a turing machine or a process to solve each case and determine whether it halts or not. After all, the information exists in theory. A machine either halts or doesn't so in theory for any case $n$ there does in fact exist a theoretical lookup table for each of those $n$-state machines. However, there is nothing special there. It's a simple statement of fact. Since such a table exists a machine can be made by doing simple graph recognition.



The problem arises when we consider that the machine needs to be able to handle all $n$ and that the number is unbounded. The general reasoning is that more and more memory is needed to process these turing machines and to determine whether or not they halt. That and that depending on the method the halting problem solver is effectively solving the same thing that turing machine is solving.



Building on the previous paragraph the intuitive reason why the halting problem cannot be solved with a turing machine is straight-forward. We have a finite amount of memory and time. If we could solve the halting problem we could solve any problem that involves determining whether or not the computation will end. In fact, it would mean we can solve all semi-decidable problems including the hailstone problem among others. But then for those times we know infinite loops will always occur, we deem them undecidable. I do not know for sure but I believe a proof exists that if all semi-decidable problems were decidable then all undecidable problems would be decidable.



Since we would also have a magic algorithm to say whether or not some machine terminates we could also validate any theorem on the integers by having it terminate if false for some case.



In other words if a turing machine could solve the halting problem it could compute anything and solve any mathematical problem.



In particular, Legendre's conjecture, the Riemann Hypothesis (through some equivalences), and the Collatz Conjecture would all be solved pretty much overnight.



The fact that we haven't done this already shows it isn't possible.



However, I will point out that a computer has a finite amount of memory (in particular a $2^{64}$ byte memory array) and therefore does automatically qualify as a finite state machine in most cases. Therefore there does in fact exist an algorithm to determine whether or not a computer program halts with a known finite input on a 64-bit system. Do I know what it is? Definitely not off the top of my head, but it does technically exist.






share|cite|improve this answer

















  • 4




    This doesn't answer the OP's question - they already know that the halting problem is unsolvable. Also, "Since we would also have a magic algorithm to say whether or not some machine terminates we could also validate any theorem on the integers by having it terminate if false for some case. In other words if a turing machine could solve the halting problem it could compute anything and solve any mathematical problem." is extremely false, and for example the Collatz conjecture cannot (so far as we know) be reduced to a "halting question."
    – Noah Schweber
    2 days ago










  • @NoahSchweber They ask for an intuitive reason why it is true and also why the busy beaver problem isn't a valid way to solve that case. And yes the Collatz conjecture would be solvable in that case as one would iterate over the integers and test whether the repeated iteration of the Collatz Copnjecture would terminate. Since that is turing-solvable under the assumption that the halting problem is solved then one could check whether the iteration through all the integers would ever halt at a counter example.
    – The Great Duck
    2 days ago










  • @NoahSchweber however, you may be correct in that nested halting problems cannot be rephrased as one halting problem, but it isn't relevant to my point here.
    – The Great Duck
    2 days ago










  • @NoahSchweber No, you are wrong. The statement was that "if a turing machine could solve the halting problem" then "it could solve the collatz conjecture". Such a machine can in fact solve the collatz conjecture. It simply doesn't exist.
    – The Great Duck
    2 days ago






  • 2




    @TheGreatDuck It's silly in the sense that if you assume a contradiction is true, then you can trivially prove that any statement is both true and false at the same time!
    – alephzero
    yesterday














-4












-4








-4






Part of the confusion is that it's not that there isn't a turing machine or a process to solve each case and determine whether it halts or not. After all, the information exists in theory. A machine either halts or doesn't so in theory for any case $n$ there does in fact exist a theoretical lookup table for each of those $n$-state machines. However, there is nothing special there. It's a simple statement of fact. Since such a table exists a machine can be made by doing simple graph recognition.



The problem arises when we consider that the machine needs to be able to handle all $n$ and that the number is unbounded. The general reasoning is that more and more memory is needed to process these turing machines and to determine whether or not they halt. That and that depending on the method the halting problem solver is effectively solving the same thing that turing machine is solving.



Building on the previous paragraph the intuitive reason why the halting problem cannot be solved with a turing machine is straight-forward. We have a finite amount of memory and time. If we could solve the halting problem we could solve any problem that involves determining whether or not the computation will end. In fact, it would mean we can solve all semi-decidable problems including the hailstone problem among others. But then for those times we know infinite loops will always occur, we deem them undecidable. I do not know for sure but I believe a proof exists that if all semi-decidable problems were decidable then all undecidable problems would be decidable.



Since we would also have a magic algorithm to say whether or not some machine terminates we could also validate any theorem on the integers by having it terminate if false for some case.



In other words if a turing machine could solve the halting problem it could compute anything and solve any mathematical problem.



In particular, Legendre's conjecture, the Riemann Hypothesis (through some equivalences), and the Collatz Conjecture would all be solved pretty much overnight.



The fact that we haven't done this already shows it isn't possible.



However, I will point out that a computer has a finite amount of memory (in particular a $2^{64}$ byte memory array) and therefore does automatically qualify as a finite state machine in most cases. Therefore there does in fact exist an algorithm to determine whether or not a computer program halts with a known finite input on a 64-bit system. Do I know what it is? Definitely not off the top of my head, but it does technically exist.






share|cite|improve this answer












Part of the confusion is that it's not that there isn't a turing machine or a process to solve each case and determine whether it halts or not. After all, the information exists in theory. A machine either halts or doesn't so in theory for any case $n$ there does in fact exist a theoretical lookup table for each of those $n$-state machines. However, there is nothing special there. It's a simple statement of fact. Since such a table exists a machine can be made by doing simple graph recognition.



The problem arises when we consider that the machine needs to be able to handle all $n$ and that the number is unbounded. The general reasoning is that more and more memory is needed to process these turing machines and to determine whether or not they halt. That and that depending on the method the halting problem solver is effectively solving the same thing that turing machine is solving.



Building on the previous paragraph the intuitive reason why the halting problem cannot be solved with a turing machine is straight-forward. We have a finite amount of memory and time. If we could solve the halting problem we could solve any problem that involves determining whether or not the computation will end. In fact, it would mean we can solve all semi-decidable problems including the hailstone problem among others. But then for those times we know infinite loops will always occur, we deem them undecidable. I do not know for sure but I believe a proof exists that if all semi-decidable problems were decidable then all undecidable problems would be decidable.



Since we would also have a magic algorithm to say whether or not some machine terminates we could also validate any theorem on the integers by having it terminate if false for some case.



In other words if a turing machine could solve the halting problem it could compute anything and solve any mathematical problem.



In particular, Legendre's conjecture, the Riemann Hypothesis (through some equivalences), and the Collatz Conjecture would all be solved pretty much overnight.



The fact that we haven't done this already shows it isn't possible.



However, I will point out that a computer has a finite amount of memory (in particular a $2^{64}$ byte memory array) and therefore does automatically qualify as a finite state machine in most cases. Therefore there does in fact exist an algorithm to determine whether or not a computer program halts with a known finite input on a 64-bit system. Do I know what it is? Definitely not off the top of my head, but it does technically exist.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered 2 days ago









The Great Duck

11732047




11732047








  • 4




    This doesn't answer the OP's question - they already know that the halting problem is unsolvable. Also, "Since we would also have a magic algorithm to say whether or not some machine terminates we could also validate any theorem on the integers by having it terminate if false for some case. In other words if a turing machine could solve the halting problem it could compute anything and solve any mathematical problem." is extremely false, and for example the Collatz conjecture cannot (so far as we know) be reduced to a "halting question."
    – Noah Schweber
    2 days ago










  • @NoahSchweber They ask for an intuitive reason why it is true and also why the busy beaver problem isn't a valid way to solve that case. And yes the Collatz conjecture would be solvable in that case as one would iterate over the integers and test whether the repeated iteration of the Collatz Copnjecture would terminate. Since that is turing-solvable under the assumption that the halting problem is solved then one could check whether the iteration through all the integers would ever halt at a counter example.
    – The Great Duck
    2 days ago










  • @NoahSchweber however, you may be correct in that nested halting problems cannot be rephrased as one halting problem, but it isn't relevant to my point here.
    – The Great Duck
    2 days ago










  • @NoahSchweber No, you are wrong. The statement was that "if a turing machine could solve the halting problem" then "it could solve the collatz conjecture". Such a machine can in fact solve the collatz conjecture. It simply doesn't exist.
    – The Great Duck
    2 days ago






  • 2




    @TheGreatDuck It's silly in the sense that if you assume a contradiction is true, then you can trivially prove that any statement is both true and false at the same time!
    – alephzero
    yesterday














  • 4




    This doesn't answer the OP's question - they already know that the halting problem is unsolvable. Also, "Since we would also have a magic algorithm to say whether or not some machine terminates we could also validate any theorem on the integers by having it terminate if false for some case. In other words if a turing machine could solve the halting problem it could compute anything and solve any mathematical problem." is extremely false, and for example the Collatz conjecture cannot (so far as we know) be reduced to a "halting question."
    – Noah Schweber
    2 days ago










  • @NoahSchweber They ask for an intuitive reason why it is true and also why the busy beaver problem isn't a valid way to solve that case. And yes the Collatz conjecture would be solvable in that case as one would iterate over the integers and test whether the repeated iteration of the Collatz Copnjecture would terminate. Since that is turing-solvable under the assumption that the halting problem is solved then one could check whether the iteration through all the integers would ever halt at a counter example.
    – The Great Duck
    2 days ago










  • @NoahSchweber however, you may be correct in that nested halting problems cannot be rephrased as one halting problem, but it isn't relevant to my point here.
    – The Great Duck
    2 days ago










  • @NoahSchweber No, you are wrong. The statement was that "if a turing machine could solve the halting problem" then "it could solve the collatz conjecture". Such a machine can in fact solve the collatz conjecture. It simply doesn't exist.
    – The Great Duck
    2 days ago






  • 2




    @TheGreatDuck It's silly in the sense that if you assume a contradiction is true, then you can trivially prove that any statement is both true and false at the same time!
    – alephzero
    yesterday








4




4




This doesn't answer the OP's question - they already know that the halting problem is unsolvable. Also, "Since we would also have a magic algorithm to say whether or not some machine terminates we could also validate any theorem on the integers by having it terminate if false for some case. In other words if a turing machine could solve the halting problem it could compute anything and solve any mathematical problem." is extremely false, and for example the Collatz conjecture cannot (so far as we know) be reduced to a "halting question."
– Noah Schweber
2 days ago




This doesn't answer the OP's question - they already know that the halting problem is unsolvable. Also, "Since we would also have a magic algorithm to say whether or not some machine terminates we could also validate any theorem on the integers by having it terminate if false for some case. In other words if a turing machine could solve the halting problem it could compute anything and solve any mathematical problem." is extremely false, and for example the Collatz conjecture cannot (so far as we know) be reduced to a "halting question."
– Noah Schweber
2 days ago












@NoahSchweber They ask for an intuitive reason why it is true and also why the busy beaver problem isn't a valid way to solve that case. And yes the Collatz conjecture would be solvable in that case as one would iterate over the integers and test whether the repeated iteration of the Collatz Copnjecture would terminate. Since that is turing-solvable under the assumption that the halting problem is solved then one could check whether the iteration through all the integers would ever halt at a counter example.
– The Great Duck
2 days ago




@NoahSchweber They ask for an intuitive reason why it is true and also why the busy beaver problem isn't a valid way to solve that case. And yes the Collatz conjecture would be solvable in that case as one would iterate over the integers and test whether the repeated iteration of the Collatz Copnjecture would terminate. Since that is turing-solvable under the assumption that the halting problem is solved then one could check whether the iteration through all the integers would ever halt at a counter example.
– The Great Duck
2 days ago












@NoahSchweber however, you may be correct in that nested halting problems cannot be rephrased as one halting problem, but it isn't relevant to my point here.
– The Great Duck
2 days ago




@NoahSchweber however, you may be correct in that nested halting problems cannot be rephrased as one halting problem, but it isn't relevant to my point here.
– The Great Duck
2 days ago












@NoahSchweber No, you are wrong. The statement was that "if a turing machine could solve the halting problem" then "it could solve the collatz conjecture". Such a machine can in fact solve the collatz conjecture. It simply doesn't exist.
– The Great Duck
2 days ago




@NoahSchweber No, you are wrong. The statement was that "if a turing machine could solve the halting problem" then "it could solve the collatz conjecture". Such a machine can in fact solve the collatz conjecture. It simply doesn't exist.
– The Great Duck
2 days ago




2




2




@TheGreatDuck It's silly in the sense that if you assume a contradiction is true, then you can trivially prove that any statement is both true and false at the same time!
– alephzero
yesterday




@TheGreatDuck It's silly in the sense that if you assume a contradiction is true, then you can trivially prove that any statement is both true and false at the same time!
– alephzero
yesterday


















draft saved

draft discarded




















































Thanks for contributing an answer to Mathematics Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3053345%2fexactly-when-and-why-can-a-turing-machine-not-solve-the-halting-problem%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

Human spaceflight

Can not write log (Is /dev/pts mounted?) - openpty in Ubuntu-on-Windows?

張江高科駅