> In colloquial usage, the terms "Turing-complete" and "Turing-equivalent" are used to mean that any real-world general-purpose computer or computer language can approximately simulate the computational aspects of any other real-world general-purpose computer or computer language. In real life this leads to the practical concepts of computing virtualization and emulation.[citation needed]

> Real computers constructed so far can be functionally analyzed like a single-tape Turing machine (the "tape" corresponding to their memory); thus the associated mathematics can apply by abstracting their operation far enough. However, real computers have limited physical resources, so they are only linear bounded automaton complete. In contrast, a universal computer is defined as a device with a Turing-complete instruction set, infinite memory, and infinite available time.

https://en.m.wikipedia.org/wiki/Turing_completeness#Non-math...

A caveat which covers a whole category is illustrating an elision, not a mistake. We know that we mean finite memory, because of, er. Reality.

of course, hence "technically", or "I'm being a smartass, but"

Turing completeness is about simulating a Turing machine, not being one.

Touring completeness is about accurately simulating any Turing machine. Not approximately simulating one (what would that even mean?), or simulating just some of them.

When we say something is Turing complete, there’s always an implicit “if it ran on a computer with unlimited memory” assumption that comes with it, because no computer with limited memory can ever simulate all Turing machines. You can always construct a Touring machine that makes a given computer run out of memory.

So technically, no real computer or computer program is Turing complete, or able to accurately simulate any Turing machine. The whole thing is an irrelevant technicality though, as A) we have so much memory available that we might as well treat it as unlimited and B) touring completeness is a theoretical property - if you prove it for something like python type hints, that proof won’t assume any memory limitations, ie. it’ll assume the computer the thing runs on has infinite memory. The proof is valid even though no such infinite computer actually exists.

Nah they're technically correct. You can't simulate a Turing machine with finite memory.

To simulate something is not to be something. Simulations are approximations of the thing. What you're implying is that we can't simulate anything, as the simulation can never be the thing. Can we not simulate the weather or the solar system because we can't take into account every possible detail? If your position is that nothing can be Turing complete, than why should anyone care about Turing completeness?

We can simulate a model of the weather. We can simulate (as in completely replicate the software behavior of) a gameboy advanced.

Not going to keep replying as this is not really a point I am going to get convinced of - to be technically turing complete is to show that every thing computable by a turing machine is computable by your construct. This is not possible in a memory constrained system.

Appreciate you've bowed out of this discussion, but what you're saying makes no sense to me, because then we would just say things are or are not Turing machines. The reason we have the term "Turing complete" and not just "Turing machine" is precisely the fact that nothing can literally be a Turing machine, and we need a useful term in discussions of computability nonetheless. The analysis as to whether or not a system is Turing complete or not is done with respect to the operations it can perform, not its memory capacity, or even the time over which is performs the operations, both of which are always assumed to be "enough" rather than infinite.

>The reason we have the term "Turing complete" and not just "Turing machine" is precisely the fact that nothing can literally be a Turing machine, and we need a useful term in discussions of computability nonetheless.

a turing machine is something way more specific than just "something that can execute algorithms" though, it's a machine that executes them using a specific system and constraints (namely advancing and modifying a strip of tape). So calling anything that can compute what a turing machine can compute a turing machine would be inaccurate just by merit of that.

of course ultimately you're right though, words mean what they're used to mean, so turing completeness excludes the infinite memory constraint, my initial comment wasn't really meant fully seriously, just being a smartass for a joke.

A Turing machine has unbounded tape, not infinite tape.

which effectively means it has infinite memory, does it not?

I don't see a distinction myself between unbounded and infinite, but the Typing system might be unbounded but it's being run on a computer with bounded memory so it becomes bounded. But that isn't a property of the Typing system, it's a property of the environment it's being executed in.

Unless you allow unbounded input there is technically a limit to the amount of memory an N-state Turing machine could possibly allocate (and still halt).

Although we don't know what that limit is, and I believe it's uncomputable.

yes, but for any given real machine with a memory limit, i can come up with a turing machine it can't simulate

When you look at the space complexity of an algorithm, it's never ‘infinity’.

Nonsense, here's an implementation (in shell, so you can easily paste and run it in your terminal) of such an algorithm:

:(){ :|:& };:

It's a ... uh ... a recursive parallel processing algorithm. Yeah.

Infinite memory available, but never used.