Hacker News new | ask | show | jobs
by User23 2894 days ago
It's been a while, since I studied this, but linear bounded automata are arguably a better model for the real computers we can actually build and the halting problem is computable for LBAs.
2 comments

Yeah, that seems true.

That said, in practice I'm not sure it is too useful (this is a slightly different question to the one originally asked, though). My understanding is the proof of decidability is essentially a pigeonhole principle argument based on LBA having a finite number of states: run the LBA for that many steps, if it hasn't halted, then it has looped. Even if a program is running on a system that only allows programs to use 1GB of memory, there's 2^(2^30*8) (approximately 10^(2.6e9)) states.

Essentially, the problem is not with computers, but with languages.

If your language lets you build a neverending loop/datastructure/etgc, then you cannot prove halting for all the programs that can be made by the language.

Since such languages exist, then by extension, it applies to computers.