|
I'm not sure there's "a" distinction, but there's a couple I tend to think about. This isn't necessarily anything formal or official. One is just, could this be Turing complete if we gave it infinite resources in the obvious manner? e.g., in Life, an infinite grid, for a modern computer, hypothetically infinite RAM and disk and time, etc. I think this is the one most people are using. Another one I tend to think about is, since the system is theoretically modeled by a finite state automaton, you can ask the question "how large would the manifested finite state automaton be?" For these toy models such as Cities, or the CSS Turing machine [1], or some small chunk of a Rule 110 encoding, often the answer is still something that might fit in a real computer as a table. There's a sense in which that's so small that using Turing Machine tools to understand the system may still not be the best way to look at it. By contrast, the FSM for something like the computer you're using to read this would be so staggeringly large that it could never fit into our universe by any encoding that doesn't somehow "cheat" and cease to be an FSM model. (That is, we can "compress" the FSM model right back down by encoding it as a Turing machine, but that defeats the purpose, no?) Even though it is theoretically a correct model of your computer, it's not useful for us humans to understand the behavior of the system. The tools of computer science for Turing-complete systems are far more applicable to understanding what it does than the FSM-based tools, even if, technically, they don't fully apply. Often they still do de facto; while theoretically it is possible to create a program that can examine the real state of any real computer and determine whether it's going to halt [2], the result would (without proof) again be so large that it couldn't possibly be manifested in the real universe, so in reality the results of the Halting Problem and similar TM-based analyses are still generally "correct" for us in practice, even if they aren't in principle. Symantec isn't going to be selling a 10^100^100^100-byte-sized anti-virus program to us any time soon. So there's also a sort of line you can draw based on the size difference between the TM-based model and the FSM-based model. It's fuzzy, although, since the FSM-based model grows exponentially (super-exponentially?), it's less fuzzy than you may think since it doesn't take much for the FSM model to go to plaid. [1]: https://notlaura.com/is-css-turing-complete/ [2]: I'm not 100% sure this is true, but I'm pretty sure it is; I suspect we can prove that the only way this machine can run is to simply execute the computer internally and record every single state it passes through; eventually it'll either repeat a previous state or halt. You can't even assume you can compress the past history very well since for any compression scheme there are programs that will pass through the states in an order that will pessimize your compression (I'm pretty sure), so we rapidly exceed the universe's storage capacity trying to store all the previous states even with such cleverness as we might still be able to muster. |