Hacker News new | past | comments | ask | show | jobs | submit login

Turing defined the machines with reference to an infinite tape. Obviously any given machine (that halts) isn't going to use all of it. If you give any specific hard bound, you have a system which can be implemented on a sufficiently large FSM. There is, therefore, a sense in which you can never "need" a Turing complete system to solve any given problem that you can solve with finite resources.



To hold to your definition of Turing completeness would make the term effectively pointless. If you relax the definition only so slightly, suddenly it has meaning again to say that something can be Turing complete.


No, to hold to my definition of Turing completeness would make the term an important theoretical construct, with a lot of ramifications. It would make the statement "X needs Turing completeness" meaningless in a particular, strict sense. I understood what the parent was talking about, speaking loosely, and I originally stated that my post was not meant as criticism.


No hard bound, but the tape is only potential infinite. (Compare https://en.wikipedia.org/wiki/Actual_infinity)


I don't see that that actually has any bearing on what I said, though. Reality will always give some hard bound, on any practical problem.


Not if you are prepared to buy more RAM (or disk space for swapping) as the program is running.


There's only so much RAM in the universe.


And, more importantly, there's only so much RAM one could reasonably acquire. When someone says something in the browser requires Turing completeness, they don't mean they expect users to acquire arbitrary amounts of RAM even at amounts far, far below any theoretical limits.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

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

Search: