Gödel, Escher, Bach An Eternal Golden Braid by Douglas R. Hofstadter

(Dana P.) #1
FIBO [N] = the Nth Fibonacci number
(e.g., FIBO [9] = 34)
PRIME-BEYOND [N] = the lowest prime beyond N
(e.g., PRIME-BEYOND [33] = 37)
PERFECT [N] = the Nth "perfect" number (a number such as 28 whose
divisors sum up to itself: 28 = 1 + 2 + 4 + 7 + 14)
(e.g., PERFECT [2] = 28)
PRIME? [N] = YES if N is prime, otherwise NO.
PERFECT? [N] = YES if N is perfect, otherwise NO.
TRIVIAL? [A,B.C,N] = YES if AN+ BN = CN is correct; otherwise NO.
(e.g., TRIVIAL? [3,4,5.2] = YES,
TRIVIAL? [3,4,5,3] = NO)
PIERRE? [A,B,C] = YES if AN+BN =, CN IS satisfiable for some value
of N greater than 1, otherwise NO.
(e.g., PIERRE? [3,4,5] = YES,
PIERRE? [1,2,3] = NO)
FERMAT? [N] = YES if AN + BN = CN IS satisfied by some positive
values of A, B, C; otherwise NO.
(e.g., FERMAT? [2] = YES)
TORTOISE-PAIR? [M,N] = YES if both M and M + N are prime, otherwise
NO.
(e.g., TORTOISE-PAIR [5,1742] = YES,
TORTOISE-PAIR [5,100] = NO)
TORTOISE? [N] = YES if N is the difference of two primes, otherwise NO.
(e.g., TORTOISE [1742] = YES,
TORTOISE [7] = NO)
MIU-WELL-FORMED? [N] = YES if N, when seen as a string of the MIU-
system, is well-formed; otherwise NO.
(e.g., MIU-WELL-FORMED? [310] = YES.
MIU-WELL-FORMED? [415] = NO)
MIU-PROOF-PAIR? [M,N] = YES if M, as seen as a sequence of strings of
the MIU-system, is a derivation of N, as seen as a string of the MIU-system;
otherwise NO.
(e.g., MIU-PROOF-PAIR? [3131131111301.301] = YES,
MIU-PROOF-PAIR? [31 1 130,30] = NO)
MIU-THEOREM? [N] = YES if N, seen as a MIU-system string, is a theorem;
otherwise NO.
(e.g., MIU-THEOREM? [311] = YES,
MIU-THEOREM? [30] = NO,
MIU-THEOREM? [701] = NO)
TNT-THEOREM? [N] = YES if N, seen as a TNT-string, is a theorem.
(e.g., TNT-THEOREM? [666111666] = YES,
TNT-THEOREM? [123666111666] = NO,
TNT-THEOREM? [7014] = NO)

(^416) BlooP and FlooP and GlooP

Free download pdf