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
Other related articles:
... This result,together with a list of other functions of N that are not calculable by a two-countermachine € when initialised with N in one counter and 0 in the other € such ... appears in a paper by Schroeppel 1972) ... The result is not surprising,because the two-countermachine model was proved by Minsky)to be universal only when the argument N is appropriately encoded by GĂdeli ...
Famous quotes containing the words equivalent and/or machines:
“I started off rapping for people just like myself, people who were in awe of wealth and flash. It was a conversation between me and them. But now most of those who buy my records are listening in on others conversation. They are the aural equivalent of voyeurs, thrilled at this crazy world that has nothing to do with their experience.”
—Ice-T [Tracy Marrow], U.S. rap musician. Observer (London, Oct. 27, 1991)
“As machines become more and more efficient and perfect, so it will become clear that imperfection is the greatness of man.”
—Ernst Fischer (18991972)