In article <DONHAM.96Feb5153...@linex.linex.com>, don...@linex.com (Jake

  In theory, any real computer can be modeled as an FSM.  So, in theory,
  you can always analyze such a beastly FSM and figure out exactly what
  it will do. ...

Those who think they have halting intuition for small Turing machines
are fooling themselves. While the general halting problem is solvable
for machines with less than 4 states, the 4 state case is open and
the 5 state case is almost certainly unsolvable due to the fact that
it includes machines iterating Collatz-like congruential functions
(similar to the famous open 3x+1 problem), and such specific problems
are currently open (but expected unsolvable, as is the general case).

I have appended my related prior comp.theory posts below. See the
cited papers for further details. The papers of Brady and Machlin
are concerned with computing Busy Beavers and will quickly convince
you of the complexity of the halting problem for small machines.
In fact the discovery of the open Collatz-like functions in 5 state
machines happened accidentally while analyzing the behavior of the
current record-holding candidate for the 5 state Busy Beaver [Mic]
1993.  A look at the analysis of the Busy Beaver candidate in [Mic]
should convince you of the power of these small machines. It is
very unlikely that a human programmer would have discovered the
Collatz algorithm encoded in this machine. Such results go to show
just how bad human intuition is on the upper reach of such "small"
machines.

As for "real-world" problems, it is known that Collatz-like
iterations represent various problems in number theory and
discrete dynamical systems (cf. Lagarias 1992) and such problems
may be encoded in surprisingly small Turing machines--just as
we have seen in the 5 state Busy beaver candidate. And lest
you think such problems have no application in the "real world"
simply have a look at the other papers in the volume in which
Lagarias 1992 appears, namely "The Unreasonable Effectiveness
of Number Theory". I would not be surprised to discover that
nature has already discovered some of these marvelously concise
algorithms and has exploited them in the design of basic
biological organisms--you can't get more "real world" than that.

-Bill

Date: Fri, 12 Jan 96 21:41:15 -0500
From: Bill Dubuque <w...@martigny.ai.mit.edu>
To: l...@cs.bu.edu
Cc: W.Tay...@math.canterbury.ac.nz, min...@media.mit.edu, wimv...@sci.kun.nl,
        w...@martigny.ai.mit.edu
In-Reply-To: Leonid Levin's message of Fri, 12 Jan 1996 13:51:16 -0500 <199601121851.NAA13...@csb.bu.edu>
Subject: universal Turing machines

[this is a CC of a post to comp.theory]

...My recent interest in small Turing machines stems not from
universality but rather from the recent discovery of (Busy Beaver)
representations of open problems such as the Collatz (3x+1) like
congruential iteration discovered by R. Robinson and Michel [Mic].
I think it is interesting to investigate just what open problems
lie in these small machines and thus to discover the "boundary" of
undecidability in such models of computation. I find it rather
fascinating that if the early Busy Beaver researchers had pushed a
little further on the five state problem then they would have
discovered open Collatz-like congruential problems perhaps before such
problems were independentally discovered by Collatz, Erdos, Ulam, etc.
with independent motivation. It is now known that such congruential
iterations arise in many important problems (e.g. see Lagarias' very
interesting survey [Lag] for the connections with discrete dynamical
systems, diophantine approximations, continued fractions (metric
theory), quasicrystals, tiling, etc.). If other known open problems
arise in a similar manner in these small Turing machines this would
prove very interesting; perhaps yet another vindication of Wigner's
"the unreasonable effectiveness of mathematics".

Does anyone else know of other open or undecidable problems
that determine undecidability boundary points in the
(symbol, state) Turing machine space?

-Bill

[Lag] J.C. Lagarias, Number Theory and Dynamical Systems,
pp. 35-72 in "The Unreasonable Effectiveness of Number Theory",
Proc. Symposia in Applied Math vol 66 (1992), AMS.

[Mic] Busy beaver competition and Collatz-like problems,
Arch. Math. Logic (1993) 32:351-367.

Date: Wed, 3 Jan 96 21:53:28 -0500
From: Bill Dubuque <w...@martigny.ai.mit.edu>
Return-Path: <w...@martigny.ai.mit.edu>
To: l...@csb.bu.edu, min...@media.mit.edu, wimv...@sci.kun.nl
Cc: w...@martigny.ai.mit.edu
Subject: Turing Machines: Universality & Halting Problem [was: Minimum states+alphabet for Univ. Turing Machine]

[This is a CC of a post to comp.theory]

  From: l...@csb.bu.edu (Levin)
  Date: 2 Jan 1996 20:18:29 GMT

  In <4cbgcj$...@zeus.cs.kun.nl>, Wim van Dam <wimv...@sci.kun.nl> wrote: [...]

  >>> Anyway, he concluded with a statement that the problem of determining a
  >>> minimal state/alphabet product was an unsolved problem (in 1956). [...]

  >> but his 4 symbol/7 state UTM is certainly worth looking at. [...]

  >Marvin Minsky emailed me about this, saying:
  >I have not heard of anything smaller, even now. [...]

There are universal Turing machines known with smaller
(symbol,state) product than the value of 28 for Minsky's
(4,7) machine.  For example, Rogozhin found a (6,4) machine
(see the abstract of [Rob] below).

Note, however, that the (symbol,state) product may be dubious
as a rule for conservation of computing power in light of
recent results on Busy Beaver computations (see pp. 264-266
of [Bra]).

Since universal machines must have unsolvable halting problems,
lower bounds may be gleaned from work on the halting problem
for small machines. Here are some results along these lines:

The restricted halting problem (i.e. the halting problem on
blank input tape) is decidable for (2,3) and (2,4) Turing
machines. This was achieved during the solution of the Busy
Beaver Problem for 3 and 4 state machines [Bra] [Br2] [Mac].
These machines were enumerated by lazily defining their
instruction trees.  Looping behavior was algorithmically
classified into a handful of classes, and the remaining
unclassified machines were analyzed by hand (ad hoc).

However, (2,5) machines probably reach intractability since
these machines can compute Collatz-like congruential
functions [Mic], and in general Conway [Con] [Bur] [Gu2] has
shown that deciding the termination of such iterations is
undecidable.  Indeed, the famous 3x+1 problem is a notorious
example of such an open problem [Lag] [Guy]. Surprisingly,
the fact that (2,5) machines can compute Collatz-like
congruential functions was discovered by accident during
the analysis of the conjectured (2,5) beaver [Mic].

The general halting problem (i.e. with arbitrary vs. blank
input) is known decidable for (2,3) and (3,2) machines [Pav].
It is currently an open problem if the same is true for (2,4).
If so, then Collatz type congruential iterations may be
the 'simplest' example of undecidable behavior in Kleene
Turing machines.

You can find discussions of these matters and much more in
the papers referenced below.

-Bill

[Bra] Brady, A. H., The busy beaver game and the meaning of life,
in Herkin, R. (Ed) The Universal Turing Machine, pp. 259-277,
Oxford Univ Press 1988

[Br2] Brady, A.H. The determination of Rado's noncomputable
function Sigma(k) for four-state Turing machines,
Math. Comp. 40 #62 (1983) 647-665.

[Bur] Burckel, S. Functional equations associated with congruential
functions, Theor. Comp. Sci. 123 (1994) 397-406.

[Con] Conway, J. H. Unpredictable Iterations, Proc. 1972 Number
Theory Conference, Univ. of Colorado, Boulder, (1972) 49-52.

[Guy] Guy, Richard, Unsolved Problems in Number Theory, 2nd Edition,
Springer-Verlag, 1994, Section E16: Collatz's Sequence.

[Gu2] Guy, Richard, Conway's prime producing machine,
Math. Mag. 56 (1983) 26-33.

[Lag] Lagarias, J. The 3x+1 problem and its generalizations,
Amer. Math.  Monthly, Jan 1985, 3-23.

[Mic] Michel, Pascal, Busy beaver competition and Collatz-like
problems, Arch. Math. Logic (1993) 32:351-367.

[Mac] Machlin, R (nee Kopp), and Stout, Q, The Complex Behavior
of Simple Machines, Physica D 42 (1990) 85-98

[Obe] Oberschelp, A. et. al. Castor Quadroplorum, Arch. Math.
Logic, (1988) 27:35-44.

[Pav] Pavlotskaya, L.M. Solvability of the halting problem
for certain classes of Turing machines, Math. Notes
USSR. 13 (1973) 537-541.

[Rob] Robinson, R.M. Minsky's small universal Turing machine,
Int'l Jnl. Math, 2 #5 (1991) 551-562.

Abstract of [Rob]:

  Marvin L. Minsky constructed a 4-symbol 7-state universal Turing
machine in 1962. It was first announced in a postscript to [2]
and is also described in [3, Sec. 14.8]. This paper contains
everything that is needed for an understanding of his machine,
including a complete description of its operation.

  Minsky's remains one of the minimal known universal Turing
machines. That is, there is no known such machine which decreases
one parameter without increasing the other. However, Rogozhin [6],
[7] has constructed seven universal machines with the following
parameters (symbols, states):

        (2,24) (3,11) (4,7) (5,5) (6,4) (10,3) (21,2).

His (4,7) machine is somewhat different than Minsky's, but all of
his machines use a construction similar to that used by Minsky.
The following corrections should be noted...

 A generalized (4,7) Turing machine closely related to Minsky's
was constructed in [5].

[1] John Cocke and Marvin Minsky, Universality of tag systems
with P = 2. Assoc. Comput. Mach. 11 (1964), 15-20

[2] M.L. Minsky, Size and structure of universal Turing machines
using tag systems, Recursive Function Theory, Proc. Sympos. Pure
Math. vol. V, AMS, Providence, R.I., 1962, pp. 229-238.

[3] Marvin L. Minsky, Computation: Finite and Infinite Machines,
Prentice-Hall, Englewood Cliffs, N.J., 1967

[4] Raphael M. Robinson, Primitive recursive functions, Bull.
Amer. Math. Soc. 53 (1947), 925-942.

[5] Raphael M. Robinson, Undecidability and nonperiodicity for
tilings of the plane, Invent. Math. 12 (1971), 177-209.

[6] Yu. V. Rogozhin, Seven universal Turing machines (Russian),
abstract, Fifth All-Union Conference on Math. Logic, Akad. Nauk.
SSSR Sibirsk. Otdel., Inst. Mat., Novosibirsk, 1979, p. 127.

[7] Yu. V. Rogozhin, Seven universal Turing machines (Russian),
Systems and Theoretical Programming, Mat. Issled. no. 69,
Akademiya Nauk Moldavskoi SSSR, Kishinev, 1982, pp. 76-90.