park@usceast.UUCP (Kihong Park) (01/08/90)
Steven Wolfram has coined a term called "computational irreducibility" to mean(to the best of my interpretation) that for cellular automata capable of universal computation, there exist problems concerning their behavior which are undecidable. That is, to compute the global configuration of a CA at the n'th iterative step, in general, an algorithm has no recourse but to compute(i.e., simulate) all the intermediate steps to arrive at the outcome. This is all dandy and fine since the undecidability of the halting problem and other undecidable problems have been known for some time. But here is the problem that I have: He seems to very well know that the concept of undecidability is applicable only to problems which have an infinite number of instances. This means that IN GENERAL, there does not exist an algorithm, i.e., a halting turing machine which solves the halting problem for any turing machine / input word pair. But in some of his writings where he uses the term "computational irreducibility"(a listing is appended), he makes statements strongly suggesting(this is my subjective impression) that even for individual problem instances, one has no recourse but to explicitly simulate a computational process(e.g. CA) to compute its outcome. Based on this, he makes "matter of fact" claims that many physical systems are of such character and hence their exact behavior predictable by observation through explict simulation only. It annoys me that he uses undecidability results in such a free and rather misleading fashion. Undecidability, and hence computational irreducibility(as he uses it) are results of a very general character and hence not applicable to everyday problem instances. One should not confuse problems having infinite instances with "one-instance" problems. Here is a problem where the term "computational irreducibility" takes on a more comprehensive meaning, but totally different in its implication and interpretation from what Steven Wolfram has used: One can write a procedure for computing the decimal expansion of root of 2 which at every interative i'th step outputs the i'th digit of the expansion. One can then ask a question such as, "will the one-way infinite sequence associated with this non-halting procedure contain a finite substring of some specified pattern?". To the best of my knowledge, there do not exist known short-cuts to answering this question without peforming the computation ad infinitum in case the answer to the question is "no". For this question, and for any other one-instance problems, undecidability results are of no use. This is so because undecidability of the halting problem does not imply that there exist halting problem instances for which the answer cannot be obtained by effective means. Hence a valid question and more interesting usage of the term "computational irreducibility" would be its association with one-instance problems. Thus, a generalization of the root of 2 problem would be as follows: Does there exist a non-halting procedure with its corresponding infinite sequence such that to compute the n'th symbol of the sequence, the n-1 preceding output symbols have to be computed, i.e., there does not exist a short-cut? If indeed this can be proven, then one has good occasion to use the term "computational irreducibility" to describe this situation. Moreover, one can modify the infinite procedure so that it halts if and only if the associated infinite sequence contains a finite subsequence satifying a certain computable condition. In addition, if one can show that there must exist computable properties of the associated infinite sequence that are false, one has a proof of the halting problem. I would be thankful for comments regarding a proof for the redefined "computational irreducibility" concept as illustrated above. Here are some references to Steven Wolfram's articles: 1. S. Wolfram "Origins of randomness in physical systems", Phys.Rev.Lett.55, 1985,449. 2. S. Wolfram "Undecidability and intractability in theoretical physics", Phys.Rev.Lett.54,1985,735. 3. S. Wolfram "Twenty Problems in the Theory of Cellular Automata", Physica Scripta, Vol.T9,170-183,1985.
baez@x.ucr.edu (john baez) (01/08/90)
In article <3035@usceast.UUCP> park@usceast.uucp.UUCP (Kihong Park) writes: >Here is a problem where the term "computational irreducibility" takes on a >more comprehensive meaning, but totally different in its implication and >interpretation from what Steven Wolfram has used: >One can write a procedure for computing the decimal expansion of root of 2 >which at every interative i'th step outputs the i'th digit of the expansion. >One can then ask a question such as, "will the one-way infinite sequence >associated with this non-halting procedure contain a finite substring of >some specified pattern?". To the best of my knowledge, there do not exist >known short-cuts to answering this question without peforming the computation >ad infinitum in case the answer to the question is "no". > >For this question, and for any other one-instance problems, undecidability >results are of no use. This is so because undecidability of the halting >problem does not imply that there exist halting problem instances for >which the answer cannot be obtained by effective means. Hence a valid >question and more interesting usage of the term "computational irreducibility" >would be its association with one-instance problems. Thus, a generalization >of the root of 2 problem would be as follows: >Does there exist a non-halting procedure with its corresponding infinite >sequence such that to compute the n'th symbol of the sequence, the n-1 preceding >output symbols have to be computed, i.e., there does not exist a short-cut? >If indeed this can be proven, then one has good occasion to use the term >"computational irreducibility" to describe this situation. Moreover, one can >modify the infinite procedure so that it halts if and only if the associated >infinite sequence contains a finite subsequence satifying a certain computable >condition. In addition, if one can show that there must exist computable >properties of the associated infinite sequence that are false, one has a proof >of the halting problem. > >I would be thankful for comments regarding a proof for the redefined >"computational irreducibility" concept as illustrated above. It seems that you are working your way towards the concept of algorithmic randomness, closely tied to Kolmogorov complexity. References include: Li, M. and Paul Vitanyi, Kolmogorov Complexity and Its Applications, in Handbook of Theoretical Computer Science, (J. van Leeuwen, Ed.) North-Holland, 1989. A preliminary version of the same work is in the Proceedings of the 3d IEEE Structure in Complexity Theory Conference, 1988. The same authors have a book out by Addison-Wesley, An Introduction to Kolmogorov Complexity and its Applications (1989). Chaitin has developed the idea of algorithmic randomness: Chaitin, G.J., "Randomness and Mathematical Proof" Scientific American, 232 (May 1975), pp47-52 Chaitin, G.J., "Algorithmic Information Theory", IBM J. Res. Dev. 21, 350-359 (1977) Chaitin, G.J., Information, Randomness and Incompleteness. (World Scientific Pub, 1987) other surveys are: Zvonkin, A.K. and L.A. Levin, "The complexity of finite objects and the development of the concepts of information and randomness by the means of the Theory of Algorithms", Russ. Math. Survey 25, 83-124 (1970) Schnorr, C.P., "A survey of the theory of random sequences", in Basic Problems in Methodology and Linguistics (Butts, R.E. Ed.) 1977, pp. 193-210. If Wolfram hasn't defined `computational irreducibility', he may have some of these concepts in mind, more or less vaguely (I haven't read the references you cite). Perhaps even more relevant is the notion of `logical depth' due to Charles Bennett, which grew out of the above work. I have a preprint of his entitled "On the logical "depth" of sequences and their reducibilities to incompressible sequences". (The title should indicate the relation to `computational irredubility'.) It's late here, so rather than try to explain how I think these notions could address your (very valid, in my opinion) complaints, I'll just quote a bit from the Bennett paper: `Roughly speaking, a finite object's information content is the size of its most concise description, and its "logical depth", or stored mathematical work, is the time required to reconstruct it from that description [he gives precise definitions].... A "deep" or dynamically complex object would then be one whose most plausible origin, via an effective process, entails a lengthy computation.' One could hope to prove that certain INDIVIDUAL states or histories of certain cellular automata are logically deep. object '