[derefr]

Is there some distinction to be made between Turing machines with tapes of fixed capacity, and ones whose capacities are limited by their execution substrate, such that they’ll support as much memory as they are “given” by the environment?

I’m picturing here the difference between Turing machines in the Game of Life that take place on a fixed area of the grid, vs. ones that attempt to just index out to whatever grid position they need, whether that causes wraparound or not.

[mdxn]

There is definitely a difference. The problem with the vast majority of "Turing-completeness in X" claims on HN is that they are just logically complete Boolean circuits that are overgeneralized (infinitely tessellated or scaled) for free and cannot handle arbitrarily large inputs. They can only handle constant sized input lengths. To handle an arbitrary input, the circuit has to be resynthesized and created to handle that particular case length. This ends up being a massive leap in computational complexity from constant-time to decidable.

Some of these claims are even wrong since the posters don't bother analyzing whether their suggested generalization technique (e.g. infinite tiling) actually do let you topologically embed every gate and batch of wires into any Boolean circuit you want. This is quite common in 2D side scrollers where you have constant y-height and infinite x length. It just is not possible to communicate all the information you need for a computation from one side of the map to the other. This was the case with Minecraft prior to bidirectional flying machines. You could actually prove that any finite sized "machine" could not communicate an arbitrary distance away (think arbitrarily long Turing tapes) without losing some part of it going off in the distance forever. Hence it was not "Turing-equivalent" unless you used command blocks or gave some overly general infinite tiling capabilities.

Actual descriptions of Turing machines are finite in size/length. These "Turing-equivalent" candidates that keep popping up are not when laid out. This makes it pretty easy to run into uncomputability situations when you try to feed the machines a description of itself and compute some property (like a number = 2x its length). A typical Turing machine would have no problem handling this, though a Boolean circuit would.

[mys_721tx]

Turing machine has unbounded memory. There is a difference between unbounded and unlimited memory: You can extend the tape as needed, but at any given step of computation, the used space is finite.

A Turing machine with bounded memory is called linear bounded automaton. Although LBA is less powerful than a Turing machine in the absolute sense, it is not trivial to form a problem that a Turing machine could decide but a LBA could not.

[ignaloidas]

The difference is that with LBA you can determine if the program will end or not, as you can check all of the finite states it can have.

[jerf]

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.