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:
“The machine has had a pernicious effect upon virtue, pity, and love, and young men used to machines which induce inertia, and fear, are near impotents.”
—Edward Dahlberg (1900–1977)
“The notion that one will not survive a particular catastrophe is, in general terms, a comfort since it is equivalent to abolishing the catastrophe.”
—Iris Murdoch (b. 1919)