

Article 298 of comp.theory.cell-automata:
Path: mimsy!haven!purdue!tut.cis.ohio-state.edu!cs.utexas.edu!swrinde!ucsd!ogicse!emory!hubcap!ncrcae!usceast!park
>From: [email-masked] (Kihong Park)
Newsgroups: comp.theory.cell-automata
Subject: S. Wolfram and computational irreducibility
Message-ID: <[email-masked]>
Date: 7 Jan 90 22:27:42 GMT
Reply-To: [email-masked] (Kihong Park)
Organization: University of South Carolina, Columbia
Lines: 67

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.