Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!tut.cis.ohio-state.edu!ucsd!ucrmath!x!baez
From: baez@x.ucr.edu (john baez)
Newsgroups: comp.theory.cell-automata
Subject: Re: S. Wolfram and computational irreducibility
Message-ID: <3231@ucrmath.UCR.EDU>
Date: 8 Jan 90 06:56:00 GMT
References: <3035@usceast.UUCP>
Sender: news@ucrmath.UCR.EDU
Reply-To: baez@x.UUCP (john baez)
Organization: University of California, Riverside
Lines: 96

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 '