3 ms·
The halting problem proof will work fine on finite sizes, I think. Failing due to an infinite loop will just be replaced by going out of memory. The main caveat
by Strilanc 6y ago
The halting problem proof will work fine on finite sizes, I think. Failing due to an infinite loop will just be replaced by going out of memory. The main caveat would be if the solver fills memory then the diagonalized solver (which is slightly larger) won't fit on the machine.
- Conlectus 6y agoFor finite sized memory, the problem can be solved by recording every system state (registers, memory values etc.) and seeing if the same state is ever reached twice. If so, the program will never terminate, and vice versa.
- Strilanc 6y agoFor clarification: I was imagining the the solver machine had the same number of resources as the problem machine (e.g. same length of tape, same number of states). I of course agree that there is a Turing machine that decides the computability of LBAs. When I said the problem still existed I meant you'd need e.g. larger and larger LBAs to solve the LBA problem up to a given size and that an LBA of tape size K with M states could not solve the halting problem for all LBAs of that size.
- light_hue_1 6y agoIt does not. A Turing machine with a finite tape is called a Linear Bounded Automaton. Halting is decidable for LBAs, but we don't know of any particularly fast algorithms for doing so.
- Strilanc 6y agoFor clarification: I was imagining the the solver machine had the same number of resources as the problem machine (e.g. same length of tape, same number of states). I of course agree that there is a Turing machine that decides the computability of LBAs.