4 ms·
More complex how? Both are abstract and can simulate each other. The difference in complexity would wend into practicality arguments that don't apply in Turing
by lupire 2y ago
More complex how? Both are abstract and can simulate each other. The difference in complexity would wend into practicality arguments that don't apply in Turing world.
Turing machine uses a tape, which is equivalent to two stacks, and also equivalent to a 2-dimensional tape (Farey Sequence), and (I guess, per previous comment) equivalent to Rule 110.
The word "Equivalent" always carries some load, though. For example, the Langton Ant tape and Rule 110 use a more interesting version of "blank" initial state, similar to the "send a message by flipping a coin on a chess board with an arbitrarily flipped coin on each square" puzzle.