3 ms·
For 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
by Conlectus 6y ago
For 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.