3 ms·
Counter Machine
- peter_d_sherman 3y ago>"A Turing machine can be simulated by two stacks. A Turing machine consists of an FSM and an infinite tape, initially filled with zeros, upon which the machine can write ones and zeros. At any time, the read/write head of the machine points to one cell on the tape. This tape can be conceptually cut in half at that point. Each half of the tape can be treated as a stack , where the top is the cell nearest the read/write head, and the bottom is some distance away from the head, with all zeros on the tape beyond the bottom. Accordingly, a Turing machine can be simulated by an FSM plus two stacks. Moving the head left or right is equivalent to popping a bit from one stack and pushing it onto the other. Writing is equivalent to changing the bit before pushing it." This is a truly fascinating Wikipedia article -- at least from the perspective of other mathematical identities (AKA, algorithmic identities) of Turing Machines...