The Caveat: *If* Its Counters Are Initialised To N and 0, Then A 2CM Cannot Calculate 2N
This result, together with a list of other functions of N that are not calculable by a two-counter machine — when initialised with N in one counter and 0 in the other — such as N2, sqrt(N), log2(N), etc., appears in a paper by Schroeppel (1972). The result is not surprising, because the two-counter machine model was proved (by Minsky) to be universal only when the argument N is appropriately encoded (by Gödelization) to simulate a Turing machine whose initial tape contains N encoded in unary; moreover, the output of the two-counter machine will be similarly encoded. This phenomenon is typical of very small bases of computation whose universality is proved only by simulation (e.g., many Turing tarpits, the smallest-known universal Turing machines, etc.).
The proof is preceded by some interesting theorems:
- "Theorem: A three-counter machine can simulate a Turing machine" (p. 2, also cf Minsky 1967:170-174)
- "Theorem: A 3CM can compute any partial recursive function of one variable. It starts with the argument in a counter, and (if it halts) leaves the answer in a counter." (p. 3)
- "Theorem: A counter machine can be simulated by a 2CM, provided an obscure coding is accepted for the input and output"
- "Theorem: Any counter machine can be simulated by a 2CM, provided an obscure coding is accepted for the input and output." (p. 3)
-
- "Corollary: the Halting Problem for 2CM's is unsolvable.
- "Corollary: A 2CM can compute any partial recursive function of one argument, provided the input is coded as 2N and the output (if the machine halts) is coded as 2answer." (p. 3)
- "Theorem: There is no two counter machine that calculates 2N ." (p. 11)
With regard to the second theorem that "A 3CM can compute any partial recursive function" the author challenges the reader with a "Hard Problem: Multiply two numbers using ony three counters" (p. 2); he's not kidding, it is a hard problem, and he asks for a better solution. The main proof is clever and difficult and involves the notion that two-counter machines cannot compute arithmetic sequences with non-linear growth rates (p. 15) i.e. "the function 2X grows more rapidly than any arithmetic progression." (p. 11).
Read more about this topic: Counter Machine, Two-counter Machines Are Turing Equivalent (with A Caveat)
Famous quotes containing the word calculate:
“However others calculate the cost,
To us the final aggregate is one,
One with a name, one transferred to the blest;
And though another stoops and takes the gun,
We cannot add the second to the first.”
—Karl Shapiro (b. 1913)