Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: