4 ms·

> There are so many bits of state in a modern CPU, you are never going to solve the halting problem in practice even for a computer with a CPU only but no RAM o

> There are so many bits of state in a modern CPU, you are never going to solve the halting problem in practice even for a computer with a CPU only but no RAM or disk. And once you add some RAM, or haven forbid, a disk with a couple of terabyte of capacity, you are in never never never never never ever territory. Is that actually proven? Or is it possible that in fact, there might be an efficient algorithm for solving the halting problem in practice for computers, but it's just that we haven't discovered it yet? Just because the state space is big doesn't mean that there aren't shortcuts to figure out in a much more efficient way whether a program loops forever.

rocqua 4y ago
It seems like we are effectively asking about the complexity of the halting problem of Turing machines with state space of N bits. It seems incredibly likely that this question has a complexity of O(exp(N)) which very quickly makes the halting problem infeasible to solve for modern computers.
- wizeman 4y ago
  > the halting problem of Turing machines with state space of N bits That's an oxymoron, because Turing machines have a state space of infinite bits by definition. I understand you mean "deterministic finite-state machines" rather than "Turing machines". > It seems incredibly likely that this question has a complexity of O(exp(N)) which very quickly makes the halting problem infeasible to solve for modern computers. I mean, I agree that it's likely, but again, is this proven? I'm not aware that it is and therefore I think this is actually missing many of the points I mentioned. It could be false for all we know.
  - rocqua 4y ago
    I understand you mean "deterministic finite-state machines" rather than "Turing machines". I meant "Turing machines with X states and a type limited to Y bits, with X + Y = N". You can, of course, cast those as Deterministic Finite State Machines, but that will require incredibly many states.
swid 4y ago
The busy beaver problem show how many states a program can have given a certain number of Turing instructions. We don’t actually know the value of that number past five I think, but it already shows us brute force is out of the question. Could we solve it without brute force? Well, there are plenty of math problems we can’t prove; we can write a program that only halts if counter example is found, and we would be unable to prove if the program halts. We can also write program that will halt if it can prove ZF set theory is false, but we already know it’s impossible to prove that (it only possible to prove it is false). So symbolically deciding if a program halts is also impossible in the general case.
- wizeman 4y ago
  > we can write a program that only halts if counter example is found, and we would be unable to prove if the program halts. Yes, but again, you're missing my point: you would be able to prove if the program halts. It's just that in this particular case it would not necessarily be useful, because it just might happen that to solve the mathematical problem it would require more memory than you have available. So if the halting detector says: "the program halted due to running out of memory", the results would be inconclusive for answering a difficult mathematical problem. But that's not what most programs do, in fact, the vast majority of programs would benefit immensely from knowing whether they will exceed some finite memory limit. > We can also write program that will halt if it can prove ZF set theory is false, but we already know it’s impossible to prove that (it only possible to prove it is false). The same point above applies. > So symbolically deciding if a program halts is also impossible in the general case. No, it's not. You completely missed my point. It is 100% decidable. It's only undecidable if you're imagining running this program on an imaginary machine which cannot physically be constructed.
  - swid 4y ago
    You asked if we could solve if it overflows a computer efficiently (without overflowing it), so I am showing that is not possible generally due to limitations of math; both our current understanding but also because math also has limits. (Gödel’s incompleteness theorem.) Attempting to overflow it is impractical using cpu cache memory sizes, no hard drive needed. No matter how fast you go through states, there are too many possible states in the cpu, and too many states even a small program can iterate through while still eventually terminating.

rocqua 4y ago

It seems like we are effectively asking about the complexity of the halting problem of Turing machines with state space of N bits. It seems incredibly likely that this question has a complexity of O(exp(N)) which very quickly makes the halting problem infeasible to solve for modern computers.

wizeman 4y ago
> the halting problem of Turing machines with state space of N bits That's an oxymoron, because Turing machines have a state space of infinite bits by definition. I understand you mean "deterministic finite-state machines" rather than "Turing machines". > It seems incredibly likely that this question has a complexity of O(exp(N)) which very quickly makes the halting problem infeasible to solve for modern computers. I mean, I agree that it's likely, but again, is this proven? I'm not aware that it is and therefore I think this is actually missing many of the points I mentioned. It could be false for all we know.
- rocqua 4y ago
  I understand you mean "deterministic finite-state machines" rather than "Turing machines". I meant "Turing machines with X states and a type limited to Y bits, with X + Y = N". You can, of course, cast those as Deterministic Finite State Machines, but that will require incredibly many states.

swid 4y ago

The busy beaver problem show how many states a program can have given a certain number of Turing instructions. We don’t actually know the value of that number past five I think, but it already shows us brute force is out of the question. Could we solve it without brute force? Well, there are plenty of math problems we can’t prove; we can write a program that only halts if counter example is found, and we would be unable to prove if the program halts. We can also write program that will halt if it can prove ZF set theory is false, but we already know it’s impossible to prove that (it only possible to prove it is false). So symbolically deciding if a program halts is also impossible in the general case.

wizeman 4y ago
> we can write a program that only halts if counter example is found, and we would be unable to prove if the program halts. Yes, but again, you're missing my point: you would be able to prove if the program halts. It's just that in this particular case it would not necessarily be useful, because it just might happen that to solve the mathematical problem it would require more memory than you have available. So if the halting detector says: "the program halted due to running out of memory", the results would be inconclusive for answering a difficult mathematical problem. But that's not what most programs do, in fact, the vast majority of programs would benefit immensely from knowing whether they will exceed some finite memory limit. > We can also write program that will halt if it can prove ZF set theory is false, but we already know it’s impossible to prove that (it only possible to prove it is false). The same point above applies. > So symbolically deciding if a program halts is also impossible in the general case. No, it's not. You completely missed my point. It is 100% decidable. It's only undecidable if you're imagining running this program on an imaginary machine which cannot physically be constructed.
- swid 4y ago
  You asked if we could solve if it overflows a computer efficiently (without overflowing it), so I am showing that is not possible generally due to limitations of math; both our current understanding but also because math also has limits. (Gödel’s incompleteness theorem.) Attempting to overflow it is impractical using cpu cache memory sizes, no hard drive needed. No matter how fast you go through states, there are too many possible states in the cpu, and too many states even a small program can iterate through while still eventually terminating.