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)
“Perhaps basketball and poetry have just a few things in common, but the most important is the possibility of transcendence. The opposite is labor. In writing, every writer knows when he or she is laboring to achieve an effect. You want to get from here to there, but find yourself willing it, forcing it. The equivalent in basketball is aiming your shot, a kind of strained and usually ineffective purposefulness. What you want is to be in some kind of flow, each next moment a discovery.”
—Stephen Dunn (b. 1939)