News for hackers. Stuff that matters.
Re:Be Nice and Write Stable Code by User23 on Tuesday July 24, 2018 @01:13AM (#17598264)
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.
Re:Be Nice and Write Stable Code by dbaupp on Tuesday July 24, 2018 @01:45AM (#17598395)
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.

Re:Be Nice and Write Stable Code by pyrale on Tuesday July 24, 2018 @08:19AM (#17600313)
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.