Hacker News Reader

Comment by Strilanc | Hacker News Reader

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.

View on HN

It 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.

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.

For 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.

Reply on news.ycombinator.com