2 ms·
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 specifi
by dllthomas 13y ago
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.
- eru 13y agoNo hard bound, but the tape is only potential infinite. (Compare https://en.wikipedia.org/wiki/Actual_infinity https://en.wikipedia.org/wiki/Actual_infinity)
- dllthomas 13y agoI 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.
- eru 13y agoNot if you are prepared to buy more RAM (or disk space for swapping) as the program is running.
- cgag 13y agoThere's only so much RAM in the universe.
- dllthomas 13y agoAnd, 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.
- jessedhillon 13y agoTo 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.
- dllthomas 13y agoNo, 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.