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

A Turing machine can either go left or right on its tape (some versions have a stay step as well, doesn’t matter). If all your program does is step right forever, than it will use the maximum amount of memory, but only ever a finite amount, that is equal to the number of steps taken.

So if you don’t have infinite time (you don’t have), and you have big enough memory for the particular use case so that you don’t get OOMKiller involved, then you have a Turing machine for all complexity theoretical and practical purposes, especially that RAM is not analogous to the Turing machine tape - your computer has much more state than only its memory, if it has network access, you can basically make use of a cloud vendors whole army of servers as storage, just as an example.



The reason for undecidability of halting is that a program's state may grow without bound. If a program's memory usage is bounded, its halting can be determined. So the computer is not like a Turing machine since its programs don't use Turing machine's key feature - infinite tape.

Although the naive way of deciding halting requires exponential time in program's memory bound, AGIs will speed that up for many programs by using clever math.




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

Search: