Collaborative articulation of how abstraction and language is employed in the computational manifestation of numbers -- including analysis of the role of syntax, semantics, and meaning in the specification and use of software interfaces.
The nfoCentrale Blog Conclave
nfoCentrale Associated Sites
Technorati Tags: Stephen Wolfram, Alex Smith, Foundations of Mathematics, FOM, Universal Turing Machine, Alternative Computation Models, Miser Project
On October 24, 2007, Stephen Wolfram announced the awarding of a $250,000 prize for a proof that a particular 2-state 3-color Turing Machine is indeed universal. [I selected a specific Wikipedia page on Wolfram because it covers the prize and the ensuing discussion on FOM in a form that is accurate enough at this point. It is unimportant to this post how later developments may be reported there.]
Controversy and Problems of Definition
Ignoring the controversy around the metaphysical aspects of A New Kind of Science, there is now a new controversy around the way this prize was awarded, the definition of the conditions for the prize, and also the conditions to be satisfied under which the (2,3)-TM achieves UTM-hood, demonstration of Universal Turing Machine capability. Considering that the machine has only two states, for a total of six rules with a three-mark alphabet, most of the work is knowing how to prepare the input and then how to recognize "the answer" of any of its computations.
On the Foundations of Mathematics discussion list, FOM, there is ongoing discussion on how universality is to be understood, how one knows that a terminating computation has indeed been completed (there being no halt state), and how one encodes the initial tape and starting condition before setting the machine loose. In particular, it might be unfair to require some other universal machine to create the initial tape for the (2,3)-TM, and it is not clear whether that is the case or not. There is also some concern for the apparent requirement that the tape may require an infinite extent of initial markings and how difficult that may be to accomplish.
This questioning will play itself out. On the FOM list, award-winner Alex Smith, Stephen Wolfram, and others are testing, clarifying, and testing again with a variety of examples and speculations, all designed to narrow down the discussion and conclude how the (2,3)-TM fits into the universality pantheon, and just exactly where.
To help frame the discussion, some useful resources have been pointed out:
Although it is not crucial to the analysis of the (2,3)-TM and agreement on the way in which it is to be accepted as universal, the demonstration of such universality is claimed by Wolfram to be evidence for his thesis, the Principle of Computational Equivalence (PCE). Wolfram's argument is that "most systems are computationally equivalent. For example, the workings of the human brain or the evolution of weather systems can, in principle, compute the same things as a computer. Computation is therefore simply a question of translating inputs and outputs from one system to another." This principle should not be confused with the Church-Turing thesis, which does not suggest where computation models are manifest, merely what the limitation of any of their powers seems to be. Wolfram accepts the Church-Turing thesis to the extent that the PCE claims an equivalent ceiling on what these ubiquitous computational mechanisms can achieve and the UTM is its exemplar. [It strikes me as ludicrous to consider it a simple matter to arrange "inputs" --conditions on the planet -- by which the weather system carries out an arbitrary desired computation. It is interesting that there are, at this point, also concerns over how inputs for the (2,3)-TM are to be arranged.]
Higher-Level and Practical Computation-Model Formulations
Meanwhile, Richard Heck, noticing Vaughn Pratt's rundown, asks for more about more-abstract axioms for recursion theory. Further contributions accumulate:
And we find ourselves at an interesting point of practical application (e.g., algorithms) of abstract (universal?) computation models. I find Gurevich's work to be interesting, especially because of the way it is being applied. (The Miser Project is not anywhere close to being able to address computation at that level.)
[update 2007-11-22: I added some of the latest FOM material and I think that is more than enough. I am satisfied to have shown how the discussion is going (and how this level of scrutiny should have preceded awarding of the prize, just as for the Millenium Challenge prizes. I don't think my interests in universal computation in the limited context of the Miser Project are impacted by this struggle universality and the principle of computational equivalence. The topic of higher-level and practical computation models remains of interest to me for later.]
Dennis, this whole exposition is quite interesting for an outsider like me. I was particularly interested in the empirical nature of the PCE. I find the idea that a "principle" is amenable to empirical testing plausible. But I also think that principles are abstractions; they don't really exist. At least not in my world of lived experience.
But this really shows my naivete regarding the philosophical issues here. On the other hand I feel pulled in two directions. I resist reduction because it removes the nuance from my actual work experience and practice. I use reduction in all my systems engineering work, because simplification and removal of detail are required for successful system building.
It's a balancing act.
|You are navigating The Miser Project.|