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.

GROUP THEORY

Previous Up Next

ITEM 102 (Schroeppel):

As opposed to the usual formulation of a group, where you are given
  1. there exists an I such that A * I = I * A = A, and
  2. for all A, B and C, (A * B) * C = A * (B * C), and
  3. for each A there exists an A' such that A * A' = A' * A = I, and
  4. 4 sometimes you are given that I and A' are unique.
If instead you are given A * I = A and A * A' = I, then the above rules can be derived. But if you are given A * I = A and A' * A = I, then something very much like a group, but not necessarily a group, results. For example, every element is duplicated.

ITEM 103 (Gosper):

The Hamiltonian paths through the N! permutations of N objects using only SWAP (swap any specific pair) and ROTATE (1 position) are as follows: 
N       PATHS + DISTINCT REVERSES
2       2 + 0, namely, S, R
3       2 + 1, namely, SRRSR, RRSRR
4       3 + 3, namely:
        SRR RSR SRR RSR RRS RSR RSR RR
        RSR SRR RSR RRS RSR RRS RSR RR
        SRR RSR RRS RRS RSR RRS RRR SR
PROBLEM: A questionable program said there are none for N = 5; is this so?

ITEM 104 (Schroeppel):

Any permutation on 72 bits can be coded with a routine containing only the PDP-6/10 instructions "ROT" and "ROTC".

SET THEORY

ITEM 105 (Komolgoroff, maybe?):

Given a set of real numbers, how many sets can you get using only closure and complement? Answer: 14.

Previous Up Next