[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.