Registered: Oct 2003
Posts: 103

The following was posted earlier today on the FOM mailing list.

Below it is a response that hopefully clears up the confusion.
---------------

Not wanting to push my luck I'll settle for one question.

How did an argument containing such an elementary fallacy get through the filter?

Smith gives a series of what I'll call finitary systems each of which runs the computation for a specified number of steps, each simulating its predecessor, then gives a non-finitary system (PDF page 21, Table of Contents page 19) that concatenates the initial conditions of progressively longer computations and runs one of the finitary systems on that concatenation.

The non-finitary system is evidently universal, and the program performing the concatenation is equally evidently non-universal. Smith infers from this that the machine checking each of the concatenated initial conditions in turn must be universal.

The analogous argument for numbers in place of machines and "infinite" in place of "universal" would be, if x+y is infinite and y is finite then x must be infinite.

This line of reasoning works for numbers but not machines. For machines it would show that a linear-bounded automaton (LBA) is universal: a non-universal machine can easily add to the input a string giving in unary the number of steps to emulate the given Turing machine, and a suitable LBA can then run the computation that far without exceeding its linear space bound.

As Chomsky showed half a century ago, linear bounded automata are not universal Turing machines.

Had I pushed my luck my second question would have been, who has verified this proof that has taught an automata theory course at a suitably accredited institution?

Vaughan Pratt

===================================

The issue mentioned by Vaughan Pratt was, in fact, one of the central points of discussion during the judging of the Wolfram 2,3 Turing Machine Research Prize.

When Minsky posed the question of finding the smallest universal Turing machines in 1967 [1], he restricted the problem to Turing machines with finite initial conditions. Indeed, arbitrary infinite (but non-computable) initial conditions can allow a machine to solve the halting problem and perform other miraculous computations that are seemingly impossible in our physical universe. Clearly, Minsky was justified in forbidding arbitrary infinite initial conditions.

But later researchers, namely [2], noted that although arbitrary infinite initial conditions should not be allowed, that interesting results could be obtained if Minsky's
restrictive definition of a 'universal Turing machine' were relaxed to allow repetitive infinite initial conditions. This relaxing of the restriction on a Turing machine's initial condition generalizes the definition of a universal Turing machine, and allows machines that were previously non-universal to be considered universal.

Of course, once one allows repetitive infinite initial conditions, one is compelled to ask what sort of non-repetitive infinite initial conditions might be allowable. Again, one does not want to allow arbitrary infinite initial conditions, since trivial machines would become universal, but how far can one relax the restriction on initial conditions, and still retain a reasonable definition of a universality?

> > The non-finitary system is evidently universal, and the
>> program performing the concatenation is
>>equally evidently non-universal. Smith infers from this that the machine checking each of the
>>concatenated initial conditions in turn must be universal.

Alex Smith did not only show that the encoding of the initial condition is non-universal. He showed that the encoding is very computationally weak and then concludes that the Turing machine is universal in a generalized sense.


> > The analogous argument for numbers in place of machines
> > and "infinite"in place of "universal"
> >would be, if x+y is infinite and y is finite then x must be infinite.

This is an inappropriate analogy because it does work for numbers. More to the point is that there are no interacting systems here, just a simple function that computes the initial configuration, then the Turing machine runs on its own.

Smith's use of non-repetitive infinite initial conditions is controversial, but is a natural extension of current definitions which allow infinite repetitive initial conditions. We hope that the ensuing discussion will enrich debate in the scientific community concerning the nature of computational universality.

Whenever a generalization of the definition of a universal Turing machine is put forward, the status of some machines will necessarily change from 'non-universal' to 'universal'. It is a challenge to explicitly construct a machine with initial conditions similar in spirit to Smith's, that is obviously too simple to be considered universal, and which is performing a universal computation with those infinite initial conditions.


[1] Marvin Minsky, Computation: Finite And Infinite Machines, Prentice-Hall, Englewood Cliffs, 1967

[2] Shigeru Watanabe. 5-symbol 8-state and 5-symbol 6-state universal Turing machines. Journal of ACM, 8(4):476-483, October 1961.

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

A couple of papers for reference, for those interested in the discussion of contemporary definitions of universality, in more general cases than finite width initials -

From 2003, Sutner

Almost periodic configurations on linear cellular automata

Abstract. We study computational properties of linear cellular automata on configurations that differ from spatially periodic ones in only finitely many places. It is shown that the degree structure of the orbits of cellular automata is the same on these configurations as on the space of finite configurations. We also show that it is undecidable whether the cellular automaton exhibits complicated behavior on configurations of sufficiently long spatial periods and exhibit cellular automata with undecidable orbits whose orbits on backgrounds of all fixed sizes are decidable.

link to PDF -

http://www.cs.cmu.edu/~sutner/papers/backgrounds.pdf

From 2005, Delvenne, Kurka, and Blondel

Abstract. Many different definitions of computational universality for various types of dynamical systems have flourished since Turing’s work. We propose a general definition of universality that applies to arbitrary discrete time symbolic dynamical systems. Universality of a system is defined as undecidability of a model-checking problem. For Turing machines, counter machines
and tag systems, our definition coincides with the classical one. It yields, however, a new definition for cellular automata and subshifts. Our definition is robust with respect to initial condition, which is a desirable feature for physical realizability. We derive necessary conditions for undecidability and universality. For instance, a universal system must have a sensitive point and a proper subsystem. We conjecture that universal systems have infinite number of subsystems. We also discuss the thesis according to which computation should occur at the‘edge of chaos’ and we exhibit a universal chaotic system.

link to PDF -

http://www.arxiv.org/PS_cache/cs/pdf/0404/0404021v4.pdf

Report this post to a moderator | IP: Logged

Registered: Jul 2006
Posts: 3

Why the universality of Wolfram's 2,3 Turing machine is relevant for modern computer science:

* New techniques for proving universality are developed (Alex Smith’s novel approach for unbounded computations from arbitrary lengths and non-periodic initial configurations.)
* Completely new universal systems have been discovered (cyclic tag- systems, bi-tag systems).
* It provides a better comprehension of what universality is and what its limits are, and illuminates the underlying principles and the necessary and sufficient conditions.
* It is a base for actually building universal devices when only few elements can be used, such as in nanotechnology or molecular computation.
* Simple/small machines may be easier/better to embed in other systems.
* The old discovery/invention duality question arise: It sheds light on how simple and often universality is, if it is engineered or not, if one builds universal computation or finds it in the universe.
* It sheds light on the relation of potential universal Turing machines to physical systems as taking advantage of different configurations of tapes: blank character vs. repetitive word vs. non-repetitive computationally simple background.
* Questions arise on size and complexity issues: it would be interesting for instance to find out if there is a polynomial (or exponential) trade-off between program size and the concept of simulating a process.
* Some questions arise on algorithmic complexity: Will the encoding always be more complex if the machine is simpler? all theorems in algorithmic information theory depend on additive constants, which depend on sizes of typical universal Turing machines. What is the impact of different generalizations of universality on algorithmic complexity and what is the role of the encoding in such a measure?
* Some questions arise on the relation between several variations of universality definitions: Is there an effective and efficient encoding for each non-periodic encoding preserving universality? If so, how does this impact their complexity? Is there a non-periodic encoding with blank characters for each periodic blank word encoding, and what would such an encoding’s impact be on the size/complexity of the Turing machine in question?

The field is active and still an important subject of research. Several computer science conferences have talks on small computational systems, for instance, Computability in Europe (CiE) and Machines Computations and Universality (MCU). Both conferences this year had small computational systems talks, in particular for reversible cellular automata and universal Turing machines.

Report this post to a moderator | IP: Logged