Chaitin. Algorithmic information theory
.pdf5.4. OMEGA IN LISP |
149 |
5.4Omega in LISP
LISP Interpreter Run
[
Make a list of strings into a prefix-free set
by removing duplicates. Last occurrence is kept.
]
& (Rx)
[ P-equiv: are two bit strings prefixes of each other ? ] : (Pxy) /.x1 /.y1 /=+x+y (P-x-y) 0
[ is x P-equivalent to a member of l ? ] : (Mxl) /.l0 /(Px+l) 1 (Mx-l)
[ body of R follows: ]
/.xx : r (R-x) /(M+xr) r *+xr
R:(&(x)(('(&(P)(('(&(M)(/(.x)x(('(&(r)(/(M(+x)r)r(*( +x)r))))(R(-x))))))('(&(xl)(/(.l)0(/(Px(+l))1(Mx(- l)))))))))('(&(xy)(/(.x)1(/(.y)1(/(=(+x)(+y))(P(-x )(-y))0)))))))
[ |
|
|
|
K |
th approximation to Omega for given U. |
||
] |
|
|
|
& (WK) |
|
|
|
: (Cxy) /.xy *+x(C-xy) |
[ concatenation (set union) ] |
||
: (B) |
|
|
|
: k |
,(*"&*()*,'k()) |
|
[ write k & its value ] |
: s |
(R(C(Hk)s)) [ add to s programs not P-equiv which halt ] |
||
: s |
,(*"&*()*,'s()) |
|
[ write s & its value ] |
/=kK (Ms) |
|
[ if k = K, return measure of set s ] |
|
: k |
*1k |
|
[ add 1 to k ] |
(B) |
|
|
|
: k |
() |
|
[ initialize k to zero ] |
: s |
() |
[ initialize s to empty set of programs ] |
|
(B) |
|
|
|
W:(&(K)(('(&(C)(('(&(B)(('(&(k)(('(&(s)(B)))())))())
150 |
CHAPTER 5. CONCEPTUAL DEVELOPMENT |
))('(&()(('(&(k)(('(&(s)(('(&(s)(/(=kK)(Ms)(('(&(k
)(B)))(*1k)))))(,((*&(*()(*(,('s))()))))))))(R(C(H
k)s)))))(,((*&(*()(*(,('k))())))))))))))('(&(xy)(/ (.x)y(*(+x)(C(-x)y)))))))
[
Subset of computer programs of size up to k which halt within time k when run on U.
]
& (Hk)
[ quote all elements of list ] : (Qx) /.xx **"'*+x()(Q-x)
[ select elements of x which have property P ]
:(Sx) /.xx /(P+x) *+x(S-x) (S-x) [ property P
is that program halts within time k when run on U ]
:(Px) =0.?k(Q*U*x())
[ body of H follows:
select subset of programs of length up to k ]
(S(Xk))
H:(&(k)(('(&(Q)(('(&(S)(('(&(P)(S(Xk))))('(&(x)(=0(.
(?k(Q(*U(*x())))))))))))('(&(x)(/(.x)x(/(P(+x))(*( +x)(S(-x)))(S(-x)))))))))('(&(x)(/(.x)x(*(*'(*(+x) ()))(Q(-x))))))))
[
Produce all bit strings of length less than or equal to k. Bigger strings come first.
]
& (Xk) /.k '(())
: (Zy) /.y '(()) **0+y **1+y (Z-y) (Z(X-k))
X:(&(k)(/(.k)('(()))(('(&(Z)(Z(X(-k)))))('(&(y)(/(.y )('(()))(*(*0(+y))(*(*1(+y))(Z(-y))))))))))
5.4. OMEGA IN LISP |
151 |
& (Mx) [ M calculates measure of set of programs ]
[ S = sum of three bits ] : (Sxyz) =x=yz
[ C = carry of three bits ] : (Cxyz) /x/y1z/yz0
[A = addition (left-aligned base-two fractions) returns carry followed by sum ]
:(Axy) /.x*0y /.y*0x : z (A-x-y) *(C+x+y+z) *(S+x+y+z) -z [ M = change bit string to 2**-length of string
example: (111) has length 3, becomes 2**-3 = (001) ]
:(Mx) /.x'(1) *0(M-x)
[P = given list of strings,
form sum of 2**-length of strings ]
: (Px) /.x'(0)
:y (A(M+x)(P-x))
:z /+y ,'(overflow) 0 [ if carry out, overflow ! ]
-y [ remove carry ]
[ body of definition of measure of a set of programs follows:]
: s |
(Px) |
|
*+s |
*". -s |
[ insert binary point ] |
M:(&(x)(('(&(S)(('(&(C)(('(&(A)(('(&(M)(('(&(P)(('(& (s)(*(+s)(*.(-s)))))(Px))))('(&(x)(/(.x)('(0))(('( &(y)(('(&(z)(-y)))(/(+y)(,('(overflow)))0))))(A(M( +x))(P(-x))))))))))('(&(x)(/(.x)('(1))(*0(M(-x))))
)))))('(&(xy)(/(.x)(*0y)(/(.y)(*0x)(('(&(z)(*(C(+x
)(+y)(+z))(*(S(+x)(+y)(+z))(-z)))))(A(-x)(-y))))))
))))('(&(xyz)(/x(/y1z)(/yz0)))))))('(&(xyz)(=x(=yz
))))))
[
If k th bit of string x is 1 then halt, else loop forever. Value, if has one, is always 0.
] |
|
& (Oxk) /=0.,k (O-x-k) |
[ else ] |
152 CHAPTER 5. CONCEPTUAL DEVELOPMENT
/.x |
(Oxk) [ string too short implies bit = 0, else ] |
/+x |
0 (Oxk) |
O:(&(xk)(/(=0(.(,k)))(O(-x)(-k))(/(.x)(Oxk)(/(+x)0(O xk)))))
[[[ Universal Computer ]]]
& (Us)
[
Alphabet:
]
:A '"
((((((((leftparen)(rightparen))(AB))((CD)(EF)))(((GH)(IJ))((KL
)(MN))))((((OP)(QR))((ST)(UV)))(((WX)(YZ))((ab)(cd)))))(((((ef
)(gh))((ij)(kl)))(((mn)(op))((qr)(st))))((((uv)(wx))((yz)(01)) )(((23)(45))((67)(89))))))((((((_+)(-.))((',)(!=)))(((*&)(?/)) ((:")($%))))((((%%)(%%))((%%)(%%)))(((%%)(%%))((%%)(%%)))))((( ((%%)(%%))((%%)(%%)))(((%%)(%%))((%%)(%%))))((((%%)(%%))((%%)( %%)))(((%%)(%%))((%%)(%%)))))))
[
Read 7-bit character from bit string. Returns character followed by rest of string. Typical result is (A 1111 000).
]
:(Cs)
/.--- ---s (Cs) |
[ undefined if less than 7 bits left ] |
: (Rx) +-x |
[ 1 bit: take right half ] |
: (Lx) +x |
[ 0 bit: take left half ] |
* |
|
(/+s R L |
|
(/+-s R L |
|
(/+--s R L |
|
(/+---s R L |
|
(/+----s R L |
|
(/+-----s R L |
|
(/+------s R L |
|
5.4. OMEGA IN LISP |
153 |
A)))) )))
---- ---s
[
Read zero or more s-exp's until get to a right parenthesis. Returns list of s-exp's followed by rest of string.
Typical result is ((AB) 1111 000).
] |
|
: (Ls) |
|
: c (Cs) |
[ c = read char from input s ] |
/=+c'(right paren) *()-c |
[ end of list ] |
: d (Es) |
[ d = read s-exp from input s ] |
: e (L-d) |
[ e = read list from rest of input ] |
**+d+e-e |
[ add s-exp to list ] |
[ |
|
Read single s-exp.
Returns s-exp followed by rest of string.
Typical result is ((AB) 1111 000).
] |
|
|
|
: (Es) |
|
|
|
: c (Cs) |
|
|
[ c = read char from input s ] |
/=+c'(right paren) *()-c |
[ invalid right paren becomes () ] |
||
/=+c'(left |
paren) (L-c) |
[ read list from rest of input ] |
|
c |
|
[ otherwise atom followed by rest of input ] |
|
|
|
[ end of definitions; body of U follows: ] |
|
: x (Es) |
[ split bit string into function followed by data ] |
||
! *+x**"'*-x()() |
[ apply unquoted function to quoted data ] |
||
U:(&(s)(('(&(A)(('(&(C)(('(&(L)(('(&(E)(('(&(x)(!(*( +x)(*(*'(*(-x)()))())))))(Es))))('(&(s)(('(&(c)(/( =(+c)('(rightparen)))(*()(-c))(/(=(+c)('(leftparen
)))(L(-c))c))))(Cs)))))))('(&(s)(('(&(c)(/(=(+c)(' (rightparen)))(*()(-c))(('(&(d)(('(&(e)(*(*(+d)(+e ))(-e))))(L(-d)))))(Es)))))(Cs)))))))('(&(s)(/(.(- (-(-(-(-(-s)))))))(Cs)(('(&(R)(('(&(L)(*((/(+s)RL) ((/(+(-s))RL)((/(+(-(-s)))RL)((/(+(-(-(-s))))RL)(( /(+(-(-(-(-s)))))RL)((/(+(-(-(-(-(-s))))))RL)((/(+ (-(-(-(-(-(-s)))))))RL)A)))))))(-(-(-(-(-(-(-s))))
154 |
CHAPTER 5. CONCEPTUAL DEVELOPMENT |
))))))('(&(x)(+x))))))('(&(x)(+(-x)))))))))))('(((
(((((leftparen)(rightparen))(AB))((CD)(EF)))(((GH)
(IJ))((KL)(MN))))((((OP)(QR))((ST)(UV)))(((WX)(YZ)
)((ab)(cd)))))(((((ef)(gh))((ij)(kl)))(((mn)(op))(
(qr)(st))))((((uv)(wx))((yz)(01)))(((23)(45))((67) (89))))))((((((_+)(-.))((',)(!=)))(((*&)(?/))((:") ($%))))((((%%)(%%))((%%)(%%)))(((%%)(%%))((%%)(%%)
))))(((((%%)(%%))((%%)(%%)))(((%%)(%%))((%%)(%%)))
)((((%%)(%%))((%%)(%%)))(((%%)(%%))((%%)(%%)))))))
)))
[ Omega ! ] (W'(1111 111 111))
expression |
(W('(1111111111))) |
display |
k |
display |
() |
display |
s |
display |
() |
display |
k |
display |
(1) |
display |
s |
display |
() |
display |
k |
display |
(11) |
display |
s |
display |
() |
display |
k |
display |
(111) |
display |
s |
display |
() |
display |
k |
display |
(1111) |
display |
s |
display |
() |
display |
k |
display |
(11111) |
display |
s |
5.4. OMEGA IN LISP |
155 |
|
display |
() |
|
display |
k |
|
display |
(111111) |
|
display |
s |
|
display |
() |
|
display |
k |
|
display |
(1111111) |
|
display |
s |
|
display |
() |
|
display |
k |
|
display |
(11111111) |
|
display |
s |
|
display |
() |
|
display |
k |
|
display |
(111111111) |
|
display |
s |
|
display |
() |
|
display |
k |
|
display |
(1111111111) |
|
display |
(000) |
|
display |
(100) |
|
display |
(010) |
|
display |
(110) |
|
display |
(001) |
|
display |
(101) |
|
display |
(011) |
|
display |
(111) |
|
display |
(00) |
|
display |
(10) |
|
display |
(01) |
|
display |
(11) |
|
display |
(0) |
|
display |
(1) |
|
display |
() |
|
display |
s |
|
display |
((1000000)(0100000)(1100000)(0010000)(1010000)(011 |
|
|
0000)(1110000)(0001000)(1001000)(0101000)(1101000) |
|
(0011000)(1011000)(0111000)(1111000)(0000100)(1000
100)(0100100)(1100100)(0010100)(1010100)(0110100)(
156 |
CHAPTER 5. CONCEPTUAL DEVELOPMENT |
|
1110100)(0001100)(1001100)(0101100)(1101100)(00111 |
|
00)(1011100)(0111100)(1111100)(0000010)(1000010)(0 |
|
100010)(1100010)(0010010)(1010010)(0110010)(111001 |
|
0)(0001010)(1001010)(0101010)(1101010)(0011010)(10 |
|
11010)(0111010)(1111010)(0000110)(1000110)(0100110 |
|
)(1100110)(0010110)(1010110)(0110110)(1110110)(000 |
|
1110)(1001110)(0101110)(1101110)(0011110)(1011110) |
|
(0111110)(1111110)(0000001)(1000001)(0100001)(1100 |
|
001)(0010001)(1010001)(0110001)(1110001)(0001001)( |
|
1001001)(0101001)(1101001)(0011001)(1011001)(01110 |
|
01)(1111001)(0000101)(1000101)(0100101)(1100101)(0 |
|
010101)(1010101)(0110101)(1110101)(0001101)(100110 |
|
1)(0101101)(1101101)(0011101)(1011101)(0111101)(11 |
|
11101)(0000011)(1000011)(0100011)(1100011)(0010011 |
|
)(1010011)(0110011)(1110011)(0001011)(1001011)(010 |
|
1011)(1101011)(0011011)(1011011)(0111011)(1111011) |
|
(0000111)(1000111)(0100111)(1100111)(0010111)(1010 |
|
111)(0110111)(1110111)(0001111)(1001111)(0101111)( |
|
1101111)(0011111)(1011111)(0111111)(1111111)) |
value |
(0.1111111) |
End of LISP Run
Elapsed time is 127.585399 seconds.
Chapter 6
Program Size
6.1Introduction
In this chapter we present a new de nition of program-size complexity. H(A; B=C; D) is de ned to be the size in bits of the shortest self-delimiting program for calculating strings A and B if one is given a minimal-size self-delimiting program for calculating strings C and D. As is the case in LISP, programs are required to be self-delimiting, but instead of achieving this with balanced parentheses, we merely stipulate that no meaningful program be a pre x of another. Moreover, instead of being given C and D directly, one is given a program for calculating them that is minimal in size. Unlike previous de nitions, this one has precisely the formal properties of the entropy concept of information theory.
What train of thought led us to this de nition? Following [Chaitin (1970a)], think of a computer as decoding equipment at the receiving end of a noiseless binary communications channel. Think of its programs as code words, and of the result of the computation as the decoded message. Then it is natural to require that the programs/code words form what is called a \pre x-free set," so that successive messages sent across the channel (e.g. subroutines) can be separated. Pre x-free sets are well understood; they are governed by the Kraft inequality, which therefore plays an important role in this chapter.
One is thus led to de ne the relative complexity H(A; B=C; D) of
157
158 |
CHAPTER 6. PROGRAM SIZE |
A and B with respect to C and D to be the size of the shortest selfdelimiting program for producing A and B from C and D. However, this is still not quite right. Guided by the analogy with information theory, one would like
H(A; B) = H(A) + H(B=A) +
to hold with an error term bounded in absolute value. But, as is shown in the Appendix of Chaitin (1975b), j j is unbounded. So we stipulate instead that H(A; B=C; D) is the size of the smallest selfdelimiting program that produces A and B when it is given a minimalsize self-delimiting program for C and D. We shall show that j j is then bounded.
For related concepts that are useful in statistics, see Rissanen (1986).
6.2De nitions
In this chapter, = LISP () is the empty string. f ; 0, 1, 00, 01, 10, 11, 000, : : :g is the set of nite binary strings, ordered as indicated. Henceforth we say \string" instead of \binary string;" a string is understood to be nite unless the contrary is explicitly stated. As before, jsj is the length of the string s. The variables p, q, s, and t denote strings. The variables c, i, k, m, and n denote non-negative integers. #(S) is the cardinality of the set S.
De nition of a Pre x-Free Set
A pre x-free set is a set of strings S with the property that no string in S is a pre x of another.
De nition of a Computer
A computer C is a computable partial function that carries a program string p and a free data string q into an output string C(p; q) with the property that for each q the domain of C(:; q) is a pre x-free set; i.e., if C(p; q) is de ned and p is a proper pre x of p0, then C(p0; q) is not de ned. In other words, programs must be self-delimiting.
De nition of a Universal Computer
U is a universal computer i for each computer C there is a constant sim(C) with the following property: if C(p; q) is de ned, then there is