Two-counter Machines Are Turing Equivalent (with A Caveat)
For every Turing machine, there is a 2CM that simulates it, given that the 2CM's input and output are properly encoded. This is proved in Minsky's book (Computation, 1967, p.255-258), and an alternative proof is sketched below in three steps. First, a Turing machine can be simulated by a finite-state machine (FSM) equipped with two stacks. Then, two stacks can be simulated by four counters. Finally, four counters can be simulated by two counters.
Read more about this topic: Counter Machine
Famous quotes containing the words machines and/or equivalent:
“There are bills to be paid, machines to keep in repair,
Irregular verbs to learn, the Time Being to redeem
From insignificance.”
—W.H. (Wystan Hugh)
“To place oneself in the position of God is painful: being God is equivalent to being tortured. For being God means that one is in harmony with all that is, including the worst. The existence of the worst evils is unimaginable unless God willed them.”
—Georges Bataille (1897–1962)