Beeler, M., Gosper, R.W., and Schroeppel, R. HAKMEM. MIT AI
Memo 239, Feb. 29, 1972.
Retyped and converted to html ('Web browser format) by
Henry Baker,
April, 1995.
AUTOMATA THEORY
Previous
Up
Next
ITEM 64 (Schroeppel):
A 2-counter machine, given N in one of the counters, cannot generate
2^N. Proven Saturday, Sept. 26, 1970. (Independently rediscovered by
Frances Yao). But (Minsky, Liknaitzky), given 2^N, it can generate
2^2^N. (A 2-counter machine has a fixed, finite program containing
only the instructions "ADD 1", "SUBTRACT 1", "JUMP IF NOT ZERO", which
refer to either of two limited counters. Such machines are known
universal, but (due to the above) they must have specially encoded
inputs.)
ITEM 65 (Schroeppel):
What effort is required to compute pi(X), the number of primes < X?
Shanks and Brillhart claim about X^.7.
ITEM 66 (Gosper):
See space-filling curve machine
item in TOPOLOGY section.
Previous
Up
Next