[cubefox]

Cool project. It reminds me of a theoretical issue. As the project page says, this system is clearly Turing equivalent. Since it runs software, it even implements a _universal_ Turing machine. But the design uses only (synchronic) sequential logic [1] and Wikipedia seems to suggest that automata theory considers sequential logic only equivalent to finite state machines. Not Turing machines. Isn't that clearly a major bug in automata theory?

My guess is that automata theory consideres it critically important that a "Turing machine" has an infinite tape, while intuitively it instead seems relevant that it has something like a tape at all, some sort of random access memory, even if it is finite. I think such a memory system can't be implemented with classical finite state machines, at least not with comparable time complexity for read and write, but can be realized with sequential logic.

[1] https://en.wikipedia.org/wiki/Sequential_logic

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