[tomstuart]

Real-world computers are equivalent to linear bounded automata, not true Turing machines, because they have finite memory. This technicality is mostly ignored because a computer with a large finite memory is a decent enough approximation to a Turing machine for practical purposes. But, for example, the halting problem is decidable for linear bounded automata — because there are only finitely many states, every computation must either halt or eventually revisit an earlier state and get stuck in a loop — so in theory it’s an important distinction.

[DEADMINCE]

> because there are only finitely many states, every computation must either halt or eventually revisit an earlier state and get stuck in a loop

Yet we know this doesn't happen in practice.

[krallja]

You just didn’t wait long enough.

[cubefox]

It seems you didn't really read my comment though? I was arguing the relevant difference between Turing machines and FSMs was the memory system, not its infinite tape. It's interesting that the Wikipedia article on LBAs doesn't tell us whether they are considered equivalent to FSMs. It seems that by standard automata theory, they must be. Which is intuitively not the correct, since they are much more similar to Turing machines.

[tomstuart]

I did read your comment but I don’t really understand what you mean by “the memory system”. A linear bounded automaton is by definition a finite state machine for a given input (i.e. fixed tape size) because the number of possible configurations is finite. A Turing machine’s infinite tape is what stops it being a finite state machine.

[cubefox]

Well, I said I meant the tape of a Turing machine (irrespective of its size), or the RAM of a physical computer, and that I suspected that such memory is different from other states in that read/write operations have specific lower time complexity.

> A Turing machine’s infinite tape is what stops it being a finite state machine.

Well, that's if you accept the usual automata theory definition, which was what I was arguing against. Part of having an "infinite tape" memory is not just that it is infinite, but also that it is a tape. A pushdown automaton also has infinite "memory" (though a stack, not a tape memory with random access), but it is still not equivalent to a Turing machine. Nor is it equivalent to a finite state machine.

Basically, what I suspect is that the type of "memory" system that some automaton allows determines its computational power, not whether the memory or the maximum number of its states is infinite or not.