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.