Some Results on Kolmogorov-Chaitin Complexity Citation Schweizer, David Lawrence (1986) Some Results on Kolmogorov-Chaitin Complexity. Master's thesis, California Institute of Technology. doi:10.7907/50qm-c858. https://resolver.caltech.edu/CaltechTHESIS:04132012-090947715 Abstract No abstract. Item Type: Thesis (Master's thesis) Subject Keywords: Computer Science Degree Grantor: California Institute of Technology Division: Engineering and Applied Science Major Option: Computer Science Thesis Availability: Public (worldwide access) Research Advisor(s): Abu-Mostafa, Yaser S. Thesis Committee: Unknown, Unknown Defense Date: 1 January 1986 Other Numbering System: Other Numbering System Name Other Numbering System ID CaltechCSTR 5233:TR:86 Record Number: CaltechTHESIS:04132012-090947715 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:04132012-090947715 DOI: 10.7907/50qm-c858 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 6930 Collection: CaltechTHESIS Deposited By: Benjamin Perez Deposited On: 13 Apr 2012 16:16 Last Modified: 09 Nov 2022 19:20 Thesis Files Preview PDF - Final Version See Usage Policy. 1MB Repository Staff Only: item control page

Some Results on Kolmogorov-Chaitin Complexity David Lawrence Schweizer Computer Science Department California Institute of Technology 5233:TR :86 Some Results on Kolmogorov—Chaitin Complexity David Lawrence Schweizer In Partial Fulfillment of the Requirements for the Degree of Master of Science Department of Computer Science California Institute of Technology Pasadena, California 1986 5233:TR:86 This work was supported by Caltech’s Program in Advanced Techuclogies, sponsored by Aerojet General, General Motors, GTE, and TRW. ©David Lawrence Schweizer 1986 Acknowledgements My advisor, Yaser Abu-Mostafa, guided me toward and through the work which makes up this thesis. Young-il Choo listened patiently to early versions of proofs, and provided invaluable assistance in convincing the TEX program to cooperate. Al Barr helped me over various obstacles in the earlier parts of my Caltech career. My parents have always encouraged and supported my academic endeavors, sometimes with greater faith in my eventual success than I had myself. To these, and to many others who have helped me realize just how much there is to learn, I am deeply grateful. i Coutents Acknowledgements ......... Introduction. . ........0.. Chapter 1 On Time Bounded Kolmogorov—Chaitin Complexity . . 1. Notation and Definitions ........ 2. On the Existence of Apparently Random Strings . 3. On the Significance of Apparently Random Strings . Chapter 2 On the Algorithmic Information of Halting Oracles Notation and Definitions .......2.~. On Discussing the Complexity of Infinite Binary Strings. . . Remarks on Relativized Kolmogorov—Chaitin Complexity oP WN On the Algorithmic Information of Halting Oracles, Big Jumps . Chapter 3 On the Time Complexity of Extracting Bits from a Compressed Halting Oracle. . Conclusions and Directions for Future Research Appendix ............. References . iii On the Algorithmic Information of Halting Oracles, Small Jumps . . . i . 10 -1l . 12 .13 . 18 . 16 17 . 20 .2l . 22 Introduction This thesis describes results in algorithmic information theory, a field of research also known as Kolmogorov—Chaitin complexity. The thesis is divided into three chapters. In the first chapter, the Kolmogorov—Chaitin definition of complexity is extended to include time complexity. This allows the absolute randomness of a binary string, as defined by its Kolmogorov—Chaitin complexity, to be distinguished from its apparent randomness, as measured by some bounded amount of computation. We show that under any computable bound on the amount of calculation allowed, there are binary strings of arbitrarily low complexity that appear totally chaotic. Further, we show that apparently random binary strings are a non-vanishing fractivu of all binary strings of sufficient length. In the second chapter, we study the Kolmogorov—Chaitin complexity of a class of infinite binary strings that arise naturally in computability theory. We begin with the halting oracle for Turing machines, and define a hierarchy of halting oracles for relativized computations. We show that the higher order oracles are of much greater Kolmogorov—Chaitin complexity than the first order oracle. In the third chapter, we combine the results and techniques of the first two chapters to prove a strong result about the time complexity of extracting information from a compressed version of the halting oracle. We show that although the halting oracle is of low randomness, all significantly compressed versions are of high apparent randomness under all computable time bounds. Chapter 1 On Time Bounded Kolimogorov—Chaitin Complexity The average computer user is unwilling to wait 10'° years for a computation to yield a result. This impatience puts limitations on the algorithms such a person will use. In this chapter, we investigate the price the user must pay (in extra program length) to get results quickly. We show that the price can be very steep, and that it must be paid quite often. 1. Notation and Definitions We will be working over the input alphabet © = {0,1}, and we write # for the blank symbol. We writc s to denote a string in 4* (the set of all finite binary strings), and A to denote the empty string. Binary strings can be put in lexicographic order thus: A,0,1,00,01,10,11,000,.... If s € 5” (that is, s is a binary string of length n) we write |s| =n. Note that the binary strings of length & can be interpreted as the binary represen- tations of the integers from 0 to 2" — 1 if we simply ignore leading zeros: Formally, a Turing Machine is a triple (Q, 2,5), where: (1) Q is a finite set of states, including two distinguished states go (the start state) and q (the halt state). (2) & is a finite alphabet, including the blank symbol #. (3) 6 is a function from Q x B to @ x (UU {L, R}), where L and R denote move left and move right, respectively. Further, once the machine enters the halt state, it never leaves it. That is, for any o € D, 6(q1,0) = (q1,¢). The machine is equipped with a single two-way infinite tape. Throughout this thesis, the tape alphabet is taken to be {#, 0, 1}. Informally, a Turing machine is a finite control that reads and writes symbols of a finite alphabet to and from a finite collection of infinite tapes. Changing the number of symbols or tapes allowed does nothing to enhance the computational power of the Turing machine, except to make it run faster or slower. It will be convenient to describe Turing machines in an informal manner throughout this thesis; everything presented can be made excruciatingly formal. Excellent expositions of the formal mechanics of Turing machines may be found in Turing’s original paper [16], or in introductory texts such as Davis and Weyuker [5], Lewis and Papadimitriou [13], or Hopcroft and Ullman [9]. All functions are taken to have domain aud range in the natural numbers. A function f is computable if there is a fixed Turing machine which will print the binary representation of f(n) when started on the binary representation of n, for any valuc of n. Since there are only countably many Turing machines, but uncountably many functions from the natural numbers to the natural numbers, many functions are uncomputable. There exists a class of Turing machines of paramount importance: the universal Turing machines. These machines are able to compute any function that can be computed by any Turing machine M by simulating the actions of M step by step. We take U to be a particular implementation of a universal Turing machine with input alphabet & and states {9o,91,...,¢K}. We write p(M) to denote the encoding of the Turing machine M and p(M)w to denote the binary string w concatenated onto the encoding of M. (The encoding p(M) is defined to be self-delimiting.) We call a string of the form p(M)w a program. The string w is called the data. For fixed p(M), we refer to the various programs obtained by adding different data as instances of the encoding. (Note that p(M) = p(M), = the instance of p(M) with the empty string as input.) If it is necessary to supply multiple strings as data, we can perform a syntactic transformation that makes the component parts of the data self-delimiting. We denote such a transformation by [w, v]. A very simple trausformation that allows |[w, v]| = 2({w] + [v|) + 2 is simply to write each bit of each string twice, and separate the strings with “01.” This method generalizes to three or more strings. Given p(M)w as input, U halts if and only if M would halt on the input w, and leaves as output precisely what M would leave. U is further defined nat to halt if its input is not a syntactically correct encoding of a Turing machine with input. It is convenient to think of 3 U as having an input tape, several work tapes, and an output tape. This convention allows a Turing machine M to have easy access to its own encoding, the binary string p(M). We use the term simulation to describe the situation of one Turing machine calculating the action of another Turing machine on a particular string. Note that since U itself is a Turing machine, it has an encoding which can be incorporated into other machines. Simulations of the action of U are of great importance. We denote by E (for Everhalting) the machine which copies the contents of its input tape to its output tape and then halts. (Or, under the convention of Turing machines having only a single tape, justs halts.) The existence of this machine guarantees that every finite binary string is the output of some program. (The string v is generated by U when presented with p(E)v.) The status of a Turing machine computation at any moment can be represented by a quadruple called a snapshot. The quadruple (¢,v,0,w) indicates that the machine is in state q with the string v to the left of its head, the string w to the right of its head, the symbol o currently being scanned, and the rest. of the tape blank. We define the relation ——*m on snapshots thus: if the machine M goes from the snapshot (g,v,0,w) to the snapshot (q',v',o’,w’) in exactly one transition (i.e. by exactly one application of the transition function 6) then (9,V,0,w)——>,(7',v',0", w'), and we define +” to be the reflexive, transitive closure of ——>+,,. Note that (q1,v,0,w)——,, (m1, V, 0, w). The Kolmogorov-Chaitin complexity of a string s is defined as: That is, K(s) = min{ |p|: U given p halts leaving s as output }. Note that p is a binary string; we have not specified how it is divided into encoding and data. A string s is random in the sense of Kolmogorov if K(s) + |s|. These definitions were first presented by Kolmogorov [11], and were extended by Chaitin [4,3]. We now define the relation —", recursively as follows: (t) (a,u, o3,v)—>,, (4,4, 05,¥), (#2) (951,11, 0%, V1) ——}, (G52, Oj, V2) if and only if there exists a snapshot (9;,u,0;,v) such that (91,115 03,, V1), (4i,0,03,V) and (q:,u,0;,v)—>,, (Gin, 02, 0},V2). Intuitively, wo snapshots satisfy this relation if the machine M transforms one snapshot into the other in ¢ steps of computation. When we simulate, the machine doing the simulation can count the number of state transitions the simulated machine goes through during the course of the simulation. This allows a Turing machine to decide whether or not some other Turing machine produces a specified output within some time bound. Finally, given a function r, we define the time bounded Kolmogorov—Chaitin complexity by: K,(s) = min{ |p| : (g0,,#,P)— 0" (1, 0, #48) - Or, K,(s) = min{ |p| : U given p halts within 7(|s|) steps leaving s as output }. We assume that 7 is always chosen large enough for U to reduce p(E)s to s within r(|s|) steps. We could eliminate this assumption by adding a clause defining K,(s) to be infinite if there is no program satisfying the requirement, but this makes the definition unnecessarily cumbersome given the weakness of the assumption above. These definitions and conventions will be used throughout the thesis. Further, more specialized, definitions will be introduced at the beginning of chapter IL. 2. On the Existence of Apparently Random Strings We show that given a computable bound on the amount of time allowed for the produc- tion of a string from the program that generates it, there exist strings of arbitrarily low Kolmogorov-Chaitin complexity that appear maximally random. That is, given a notion of quick, we show that there are strings that can be compressed to extremely short rep- resentations, but that cannot be recovered quickly from any specification shorter than the original string. Reasons to be interested in the amount of time required to generate a binary string are most intuitively to be found in the realm of data compaction. Computer users often want to store large amounts of data, but are not concerned with the details of how the information is stored. It is important, however, that the stored data be readily accessible. The problem of data compression should really be called the problem of data re-expansion. Typically, we are concerned with the size of the compressed version and the difficulty of retrieval of the original information, not the difficulty of the compression process. Other areas of Computer Science are also well characterized as the study of culupach representations. Computer Graphics seeks to model the real world in ways that permit generation of realistic images without having previously stored digitized versions of those images. Suppose we limit the amount of computation that may be done to retrieve a binary string from its compressed version. Clearly, under some bounds some strings will require longer programs than they do under larger bounds. One might hope that a trade-off of space against time exists; that is, that restricting the amount of time allowed would cost some (but not all) of the space saved. Unfortunately, under any computable time bound at all there exist binary strings that appear incompressible (ie. that are not generated by any short program within that time bound, but that have extremely short descriptions if we do not limit in advance the amount of computation allowed.) More precisely, we have: Theorem 1.1 Let r and o be any computable functions, with o(n) > 2. Then there exists a ¢) such that for all ¢ > to there exist binary strings s with |s| = o(t) such that K(s) <i but K,(s) > a(t). We call such a string r-incompressible. To emphasize the generality of this result, consider letting a(n) = A(n,n) and r(n) = A(o(n),a(n)), where A is Ackermann’s generalized exponential. The theorem says that there is a program of length n that generates an enormous string, but takes a very long time to do it. But further, if we require a program to generate that string “fast” (and we should emphasize that A(o(n),o(n)) is huge) then we are completely stuck: we cannot get by with a program even one bit shorter than the string itself. Proof The proof proceeds by constructing a Turing machine which attacks the problem by brute force: we examine the output of every short program that halts quickly, and then select a string not in the list of produced outputs. The proof is constructive, that is, it gives a procedure for exhibiting a r-incompressible string. We construct a Turing Machine M. Let to = |p(M)|, and consider any instance p(M)w of p(M) of length ¢. This proof relies heavily on the fact that Turing machines may be composed. Each step described below is complex, but clearly computable. The Turing Machine M started on the input string w (or, equivalently, U started on the input string p(M)w : (1) Computes o(t) and r(|s|) = r(o(z)). We note that t does not need to be specified as a parameter to the computation: the program remains available on the input tape of U; (2) Generates a list £ of all binary strings of length o(t) in lexicographic order; (3) Simulates the operation of U on each binary string of length < a(t) — 1 until it (ie. the simulated U) either halts or has computed for r(o(t)) steps without halting; (4) Removes from the list £ every string of length exactly a(t) produced by a simulation; (A simulation must halt to be considered to have produced an output.) (5) Prints the w' remaining string; (We show below that there are at least 2'”/ +1 strings in £ not produced by any simulation; hence the w'" remaining string exists.) (6) Halts. We note that M simulates U on 2° + 2! +... 4 2°4)-1 = ole()-1)t+1 __ 4 — oof) _y potential programs. Since o(t) > t, the 2!” instances of p(M) are in this collection, and each of them clearly computes for more than r(o(t)) steps before it halts. Thus no more than 274) — 1 — alwl strings are eliminated from £, and each instance of p(M) of length t will produce a distinct string of length a(t). The construction above gives a program of length ¢ that generates the string s. Thus K(s) < t. But by the operation of M, s is not produced within 7(a(t)) steps by any program of length < o(t) — 1. Thus K,(s)>o(t). I Suppose we are given a binary string and wish to know whether or not it is T-incompress~ ible. We can simply enumerate all r-incompressible strings of the same length as the given string, and then check to see if the given string is in the list. The time complexity of doing this is clearly a multiple of the time complexity of the operation of M, with the multiplier exponential in the length of the given string. The point is that the problem of generating r-incompressible strings and the problem of deciding if a given string is r-incompressible are essentially the same. This has interesting ramifications for physics. Erber and Putterman [7] have recently suggested that the validity of Quantum Me- chanics be tested empirically by observing spectral emissions of single atoms stimulated by a laser. They hope that “...a search for unexpected patterns of order by cryptanalysis of the telegraph signal generated by the on/off time of the atom’s fluorescence will provide new experimental tests of the fundamental principles of the quantum theory.” The above theo- rem says that we can never increase our confidence in the validity of Quantum Mechanics on the basis of such an experiment: there could be an extremely short, but computationally complex, explanation for the string generated by the experiment. There arc some assumptions about the fundamental nature of computation and physi- cal systems implicit in the discussion above. If the string generated truly requires enormous amounts of time to be produced, then how does the electron “decide” what to do quickly? The fundamental relation between randomness as studied in Quantum Mechanics and ran- domness as studied in computability theory is not at all well understood. Dentsch [6] has addressed the question, but it is far from entirely settled. 3. On the Significance of Apparently Random Strings We now investigate how significant these apparently random strings are. That is, given r and o, how many strings of length o(n) are r-incompressible? Leonid Levin [10] formulated the problem thus: Let S,,n = {8 € {0,1} |K(s) < K,(s)}. Conjecture: lim [Sean] > 0 for any computable r. N—-00 ON The following theorem settles this conjecture affirmatively. Theorem 1.2 For any fixed k and any computable function r, there is an ng such that a constant fraction of all strings of length n > no have K(s) < n—k but K,(s) >n. Proof We use the definitions of theorem I.1, and base the proof on the machine M of that theorem. Let o(m) = m+k. We again call |p(M)| = to. Since |w| = t — to, we have 2'-to instances of the encoding p(M), each of which produces a distinct string of length t+k. Thus 2-(to+*) — a fraction independent of n — of all strings of sufficient length can be compressed by k bits (i.e. are produced by programs k bits shorter than the strings themselves) if we are patient, but appear maximally random if we require that generating programs run under the time constraint +. (We require that ng = tp. To see that this suffices, take o(m) = m +1, and consider the string produced by p(M)A.) Chapter 2 On the Algorithmic Information of Halting Oracles We have already noted that there are functions not computable by Turing machines. Com- puting any function from the natural numbers to the natural numbers can be reduced to the problem of deciding some language, that is, determining whether or not certain binary strings are in a particular subset of 5*. This provides a convenient framework in which to study questions of relativized computability. Suppose some agency provides us with a magical source of answers to a specified set of questions which we might be otherwise unable to answer. In this chapter we investigate some aspects of the additional computing power we would gain from such an oracle. The Kolmogorov—Chaitin complexity can be thought of as a measure of the degree of uncomputability of infinite strings. If X,, denotes the first m bits of an uncomputable infinite binary string X, the algorithmic information K(X,,) is the minimum number of bits needed to compute X,, on a universal Turing machine. How K (Xm) varies with m, for example, as log m, ,/m, im, etc., is a measure of how uncomputable X is. On the other hand, the degree of uncompntahility can he measured in terms of a hierarchy of halting oracles. If any desired number of bits of X can be computed by a fixed Turing machine which consults the n*® order halting oracle, but not by any machine that consults the (n — 1)**, then its degree of uncomputability is n. The purpose of this section is to relate these two concepts of “degree of uncomputabil- ity,” by giving exact estimates (identical lower and upper bounds) for the algorithmic infor- mation of halting oracles. Specifically, the algorithmic information of the :*" order halting oracle relative to a universal Turing machine which consults the j** order halting oracle is 10 estimated for all 7,7. The result shows a sharp contrast between the algorithmic informa- tion of the first order halting oracle (previously investigated by Chaitin [4]) and the second order halting oracle. Also, the essential changes in the Kolmogorov—Chaitin complexity of certain strings for different consulted oracles are discussed. l. Notation and Definitions An oracle for a language L C &" is an infinite binary string, where the n™ bit of the oracle is a 1 if and only if the n*® string of D* (in lexicographic order) is in L. An oracle consulting Turing machine (“OTM”) is a Turing machine with an additional read-only tape, infinite in one direction (the “oracle tape” ). At any stage of the computation the action and next state of the machine are determined by the current state and the symbols scanned on the work tape and the oracle tape. To the usual actions are adjoined actions for moving the oracle tape scanning head left or right. Intuitively, the oracle will be inscribed (by some means other than a Turing machine) on the oracle tape, and queries to the oracle will be accomplished by examining a particular bit of the oracle. A universal oracle consulting Turing machine takes strings as input and halts with a specific output if and only if the input string is a syntactically correct encoding of an OTM (possibly including an input string for that machine) that halts with that output. (This is analogous to the definition of universal Turing machines given earlier.) We denote the universal OTM with some particular oracle O on its oracle tape by U(O). Note that the halting behavior of the universal OTM for some fixed string may be different for different oracles. (That is, a computation which depends on the contents of the oracle tape will proceed differently if the oracle tape is changed.) We say that a function is computable relative to the oracle O (or “O-computable”) if the function can be computed by an OTM with O on its oracle tape. We define the halting oracle for OTM’s relutive to the oracle O to be the oracle for the language L(O) = {s: U(O) halts on 5}. Finally, we define the complexity of a string s relative to the oracle O thus: K°(s) = min{ |p| : U(O) given p halts leaving s as output }. li That is, the complexity of a string is the length of the shortest program which produces the string. If the oracle tape is blank, then this is the usual Kolmogorov—Chaitin complexity. (In fact, if the oracle tape contains any computable string, then the relativized Kolmogorov- Chaitin complexity differs from the usual Kolmogorov—Chaitin complexity only by an ad- ditive constant.) If X is some infinite binary string, X» denotes the first m bits of X. For the remainder of this thesis, we will use the following hierarchy of oracle strings: H? is the empty string. H” is the halting oracle for OTMs relative to H*~!. Thus H? is the halting oracle for normal Turing machines. This hierarchy corresponds to the sequence 0, 0', O”, ... of Turing degrees (see, ¢.g., Rogers [14]). 2. On Discussing the Complexity of Infinite Binary Strings The complexity of an infinite binary string is a little harder to define than the complexity of a finite string. Clearly, we cannot expect a Turing machine to print an infinite string and then halt. The solution is to look at the complexity of all initial substrings. Intuitively, an infinite string X is computable if there exists a fixed Turing machine which can compute X for any specified m. A string is uncomputable if we must specify not only how much we want, but also some information about the string. It might seem that the complexity of (initial substrings of) computable strings does not grow with the length of the substring, but the complexity of (initial substrings of) uncomputable strings does. The problem is that it is possible for the numeral m to have high complexity. It is therefore impossible to describe the behavior of the complexity of infinite strings by means of limits. We can, however, make the following statements about the Kolmogorov— Chaitin complexity of a computable infinite string X: lim inf K (Xm) = m—oco loglog---logm 12 The first case is justified by noting that the numeral which represents the number m never requires more than [logm] digits. In the second case, we take the machine which computes X,, from m, and compose it with a machine that computes a function that grows extremely fast. We can always find a function that grows faster than the inverse of any fixed number of iterations of log, and thus generate enormously long initial substrings of X from very short inputs. 3. Remarks ou Relativized Kolmogorov—Chaitin Complexity 1. H+! is not H'-computable. The case 7 — 0 is a slalement of the usual halting problem. Other cases can be proved with exactly the same techniques. 2. K (a) is not H'-computable. (Assume that it is. Take the program that computes it and modify it to look for strings of very high complexity and print one. Since the program is of constant length, and we can specify how high we want the complexity to be with a logarithmic number of bits (the length of a numeral is log of the number it represents), we get a contradiction.) But K4'(s) is H'+1-computable. (Simply simulate all machines of appropriate length which the oracle says will halt and look for the shortest one generating 8.) 3. A given string can have different complexities relative to different oracles. As an example, consider the worst string of length n relative to H’, that is, the string with the highest complexity (breaking any tie by lexicographic ordering). Relative to H'+1 we need only a constant program and logn bits of specification. 4. On the Algorithmic Information of Halting Oracles, Small Jumps In this section and the next, we completely analyze the relative complexity of pairs of halting oracles. We find the somewhat surprising result that specifying an oracle one step above one we have requires much less information than specifying one two or more steps up. To be precise, we show: i pes O(logm), t=J5-1; H I) — ’ ’ KO Fin) = {ong i<j-L 13 (© is Knuth’s [10] “Big Theta”; f(n) = @(g(n)) means that f = O(g) and g = O(f), or, there exist c, and cz such that cig(n) < f(n) < ceg(n), for all n sufficiently large.) The first case says that given some halting oracle H', m bits of H't! can be compressed into a description of length essentially log m, but no further. The second case says that all higher order halting oracles may be compressed only to some fraction of their length, but no further. We note that the omitted case, i > 7 — 1, is not interesting: given any halting oracle, we can compute lower order halting oracles at will. Lemma about Lower Order Halting Oracles Having said that the i > 7 — 1 case is uninteresting, we hasten to add that it is needed for later results. Therefore let. us assume that we have Hi’ on the oracle tape and want bits of H'-!, We define a special OTM called the “checker,” denoted C. Given the binary number w as input on the work tape, C reads the w*® bit of whatever is on its oracle tape (here assumed to be H*~!) and halts if that bit is a 1. If the bit is a 0, C enters an infinite loop. Since we can use Hi’ to decide the fate of C on any input w, we can determine the w*t bit of H'-!. By building checkers of checkers of checkers (etc.), we can work our way down to any halting oracle of degree lower than the one we have. For completeness, we note that we can always copy bits from the oracle tape to the work tape: this coverssi=j. [ff Theorem 2.1 We now wish to show that K™ (Hit) — @(log m), or, equivalently, that K™ (Hit) = @(m). Proof This proof is in two pieces: first, we demonstrate by construction that the oracle may be compressed logarithmically; and second, we prove that it cannot be compressed further. We define 0'+1 to be the number of 1’s in Hit ,. (This is by no means the only way to compress a halting oracle. Chaitin’s number 1) is equally dense; the proof using m bits of that string is essentially the same as what follows. See Gardner [8] for an excellent discussion of this material.) 14 We must first verify that if we are given Q'+! we have enough information to construct approximately 2™ bits of H't! using U(H"). We note that the number of 1’s in some section of a halting oracle is the count of the number of programs which halt. In this case, we know how many programs of length less than m will halt. So we simulate the operation of all such programs until the correct, number have halted. We then know which bits of Hy are 1’s, and can write 0’s in the other places, and thus print the entire 2” — 1 bits. (In the course of these simulations, we will need to refer to a great many bits of H?. In fact, it can be proved by a diagonalization argument that the number of bits we will need grows faster than any H’-computable function of m.) Now assume that the halting oracle can be compressed further, i.e., that for some ¢ > 0, K¥' (Bit) < m- (1-6). This says that. it is possible to use m — em bits to determinc the fates of all programs of length less than m. Call such a string f, and consider the following Turing machine (called T): (1) Use 1 to decide which programs of length less than m will halt; (2) simulate all those programs; (3) for every string that has been generated as the final output of one or more programs, find the shortest program that generates that string; (4) find the longest of these programs; (5) erase everything except the output of that program; (6) halt. We observe that there is a string of length m of complexity at least m. This follows from the fact that there are 2” strings of length m, but only 29+214...49m-1—9m_y4 programs of length less than m. Now note that the encoding p(T) of ‘I’ has some fixed length; call it t. We recall that no string of length m has complexity greater than m+ |p(E)|. For large m, m—em+t<m-— $m. But now we have found a contradiction. For, by the observation above, the output of T will be a string of complexity near m, but T and (© describe it with significantly fewer bits. Hence 1) does not exist, and K™ (Hit!) = @(logm). | 15 5. On the Algorithmic Information of Halting Oracles, Big Jumps Now we wish to show that Theorem 2.2 i<j—1-> KH (Hi) = O(m). Proof Our approach will be to use 2" -m bits of Hi to construct m bits of Qi+!, The exponent r depends only on 7 —7 and a constant. Without loss of generality, let i = 7 — 2. (We have seen that. we can compute lower order oracles from higher order ones.) Consider the following OTM M with |p(M)| =k when started on a binary string w of length m: (1) calculate the (w + 1)* bit of the binary numeral which represents the number of 1’s in the first 2?" — 1 bits of whatever is on its oracle tape; (2) If that bit is a 1, halt; (3) If it is a 0, enter an infinite loop. If the oracle tape read by M contains H't!, then M halts if and only if the (w + 1)* digit of O85) is a1. Assume we have 1: ee By definition, this contains halting information for all OTM programs of length less than or equal to m + k with H't! on their oracle tapes. In particular, it contains halting information for M with input strings of length m. There are 2™ of these programs, and each one yields exactly one bit of oft. We are done, since we have already shown that 0+! is uot compressible. ff 16 Chapter 3 On the Time Complexity of Extracting Bits from a Compressed Halting Oracle It is well known that the Kolmogorov—Chaitin complexity of initial substrings of the halting oracle is logarithmic in the length of the oracle which they specify. All the usual examples of corresponding compressions (e.g. Chaitin’s number 2) require unbounded amounts of time for expansion. Any method which requires simulating a group of Turing machines until all which will ever halt have halted must require an amount of time which grows faster than any computable function; if the time could be bounded above, we would be able to solve the halting problem. We now show that this is true of all such drastic collpressions. Theorem 3.1 Let H! bea compressed version of the halting oracle H!. Suppose that f(n) bits of H! suffice to specify the first n bits of H!, that is, that there exists a fixed Turing machine which can compute H} from At.) for any n. Assume that lim f(r) = 0. n0o Then there is no computable bound on the amount of time required to extract any single bit of H! from H?. Proof Assume that a block u of r bits of H1 ending on the s*" bit, i.e. the bits with indices from s—r-+1 to s, can be extracted from a sufficiently long block H1, , of H! in time f(r) T(s,r), where T is a computable function, i.e., that there exist M" and 7 such that (90,A, #,e(M")[s,r, Hy ny) EO '(—E8, A, #,U }. 17 We observe that this is equivalent to assuming that there is a computable bound on the time required to extract a single bit of H! from H!. The assumption above clearly implies a computable bound on the time required to get one bit: set r = 1. If we have a bound on the time required to extract one bit, we can simply compose the Turing machine which meets that bound with itself r times. The resultant machine will run in time boundable by a computable function. (See, e.g. Lewis and Papadimitriou [13] for more details on composition of Turing machines.) Let T(syr)= D> T(i,9). Isjstss This expression has no explicit dependence on r, but T'(s,r) is obviously not defined for r > s. We define T(s,r) in order to avoid putting requirements on T(s,r). Note that 7 is monotonic and bounds T above. Recall the Turing machine M of theorem I.1. Let a(n) = n+ 1, and let r(n) = F(2",n + 1). We will be considering the instances of M of length 2* — 1 of the form p(M)00---0. Let M’ be a Turing machine which takes a k-bit string n as input and (1) computes the (n + 1)** bit of the output of the appropriate instance of M; (2) halts if that bit is a 1; (3) enters an infinite loop if that bit is a 0. Note that for all sufficiently large k, |o(M')n| = |o(M')| +k < 2 —k—-1, and also |e(M’)| + |o(M")| + 24 +1 < 2°. Choose k large enough to satisfy the second inequality above. By the construction of M!, the 2* bits of H! describing the halting behavior of the programs from p(M')00- --0 to p(M’)11--+1 (the instances of M’ with data of length k) are exactly identical to the string generated by M. Since f bounds T above, we can use M" to print these bits in time at most P(Qe(M +e 4 1 ok) < 7(2*). 18 Further, we can use fewer than 2* bits of input to U to do this: e |p(M")| is constant, ¢ specifying which bit of H! gives the halting information for p(M')11---1 requires no more than |p(M’)|-+ &+ 1 bits (this is the parameter s), e specifying r requires k bits, e by assumption, specifying Fo peyitett_y requires fewer than 2*~° bits, for all b, e encoding the three data parameters requires at most 2(|p(M’)|+A+1+k+ |") +4 bits, and we are done, for the sum of all these lengths [e(M")| + 2|o(M"’)| + 4k + 6 + 2*-8 can be made less than 2" for some b. It might appear that we have proved a stronger result than originally stated, viz., that there is some maximal fraction 2~° limiting the degree of compression. The problem is that as T gets larger, r gets larger, and as r gets larger, |p(M)| grows, and thus we cannot bound |p(M’)| absolutely. ff 19 Conclusions and Directions for Future Research Randomness is a subtle and slippery idea. This thesis has tried to enhance our understand- ing of this important concept by exploring algorithmic notions of complexity. The results on time bounded Kolmogorov—Chaitin complexity touch on the difficulty of discovering patterns. It is not always possible to find structure with a reasonable amount of effort. In the last two chapters, we have illustrated the enormous power of halting oracles. We have made repeated use of the idea of reducing a computation to a yes or no answer, having a Turing machine halt or not halt depending on that answer, and then extracting the answer—without having tu go tliough potentially prodigious amounts of computation— from a halting oracle. It is this powerful property of halting oracles which makes them so hard to compress—either in space, as with the hicrarchy of halting oracles (Chapter 2); or in time, as with the first order halting oracle (Chapter 3). There is a large literature on relativized computability, and there is a well understood hierarchy of recursive degrees. It would be interesting to characterize the Kolmogorov— Chaitin complexity of arbitrary oracles in the lattice of Turing degrees in a general manner. The degrees which are weaker than the halting oracle but not recursive are especially inter- esting. 20 Appendix Some of the results presented in this thesis are not original. The final theorem was originally called a result on general recursive majorants of complexity. It was first proved by Barzdin’ [2], and was presented again, with a different proof, by Zvonkin and Levin [18]. These articles were unknown to the author until L. Levin [12] mentioned the references. Theorem 1.1 is, according to Levin, not at all deep. But there is some value in the proof given, in that it provides an easy way to prove theorem 1.2. The results on algorithmic information of halting oracles are, so far as the author knows, original. 21 References [1] Abu-Mostafa, Y.S., Information and Complexity, in preparation. [2] Barzdin’, Ja. M., “Complexity of Programs to Determine Whether Natural Numbers Not Greater Than n Belong to a Recursively Enumerable Set,” Soviet Math Doklady 9:5 (1968), pp. 1251-1254. [3] Chaitin, G. J., “Information-Theoretic Limitations of Formal Systems,” Journal of the ACM 21 (1974), pp. 403-424. [4] Chaitin, G. J., “A Theory of Program Size Formally Identical to Information The- ory,” Journal of the ACM 22 (1975), pp. 329-340. [5] Davis, M. D, and E. J. Weyuker, Computability, Complexity, aud Lauguages, New York: Academic Press, 1983. [6] Deutsch, D. “Quantum Theory, the Church—Turing Principle and the Universal Quan- tum Computer,” Procedings of the Royal Society of London A 400 (1985), pp. 97-117. [7| Erber, T. and S. Putterman, “Randomness in quantum mechanics—nature’s ultimate cryptogram?,” Nature 318 (7 November 1985), pp. 41-43. [8] Gardner, M., “Mathematical Games,” Scientific American 241 (November 1979), pp. 20-34. [9] Hopceroft, J. E. and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Reading, Massachusetts: Addison-Wesley, 1979. [10] Knuth, D. E., “Big Omicron and Big Omega and Big Theta,” ACM SIGACT News (April-June 1976), pp. 18-24. [11] Kolmogorov, A. N., “Three Approaches to the Quantitative Definition of Information,” Problemy Peredachi Intormatsii 1 (1965), pp. 3-11. [12] Levin, L., private communication. [13] Lewis, H. R. and C. H. Papadimitriou, Elements of the Theory of Computation, En- glewood Cliffs, New Jersey: Prentice-Hall, 1981. [14] Rogers, H., Theory of Recursive Functions and Effective Computability, New York: McGraw-Hill, 1967. [15] Shannon, C. E. and W. Weaver, The Mathematical Theory of Communication, Urbana: University of Illinois Press, 1963. [16] ‘luring, A. M., “On Computable Numbers, with an Application to the Entscheidungs- problem,” Proceedings of the London Mathematical Society, ser. 2 42 (1936), pp. 230- 265, and ser. 2 43 (1936), pp. 544-546. [17] Turing, A. M., “Systems of Logic Based on Ordinals,” Proceedings of the London Mathematical Society, scr. 2, 45 (1989), pp. 161-228. [18] Zvonkin, A. K. and L. A. Levin, “The Complexity of Finite Objects and the Devel- opment of the Concepts of Information and Randomness by Means of the Theory of Algorithms,” Russian Mathematical Surveys 25:6 (1970), pp. unknown 23