Two-stack encoding of a Turing tape

ID: two-stack-encoding-of-a-turing-tape

Encode the cells immediately left of the head in a reversed positional stack , and the current and right cells in . Quotient and remainder by the alphabet base read and remove cells; multiplication by that base pushes a cell. The resulting local tape transitions are primitive recursive, which makes them directly implementable on Church numerals.

New to topics? Read the docs here!