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