4 ms·
Entirely an aside, and not meant as criticism but merely an interesting (hopefully) point noted in passing: If you are doing something that requires Turing-com
by dllthomas 13y ago
Entirely an aside, and not meant as criticism but merely an interesting (hopefully) point noted in passing:
If you are doing something that requires Turing-completeness, you're doing something that can't be done on real computers, because any collection of digital hardware can be represented as a (flippin' ginormous) finite state machine.
- eru 13y agoTuring machines are not infinite. There are merely big enough for everything you want to do. (I.e. actual infinity vs potential infinity.)
- dllthomas 13y agoTuring 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.