Continuous Turing Machines

A typical Turing Machine has a fixed number of "states" and an 
infinitely long tape containing discrete "cells" where any one of a 
finite set of "marks" may be placed.  The machine "looks at" a 
particular cell and, depending on the contents of that cell and the 
current state of the machine, executes a specific action (possibly 
replacing the mark in the cell with some other mark and changing 
its own "state") and then "moves its attention" to some other cell
at a specified relative position on the tape.

Suppose, instead, we define a machine whose "state" at any time t 
is a real number s(t), and the "tape" is magnetized with intensity 
m(x) at location x (where x is the real-valued distance from the 
starting position).  The machine is initially set to the state s(0)=0 
and placed at location x=0 on the tape, which has been "programmed" 
with some initial profile of magnetic intensities over a finite range 
of the tape.  (I'm treating m(x) as an ideal continuous function.)

For time t>0 the machine determines its (real-valued) acceleration 
a(t) as a pre-established function of the current state s(t) and the 
magnetic intensity m(x) at the current location x(t). The machine 
can also modify the intensity of the field at location x(t)-d (where
d is a fixed constant) by setting it to any desired value, or it can 
leave the intensity at location x(t)-d unchanged.  

Notice that an ordinary audio tape recorder is an approximate 
model of a Continuous Turing Machine (CTM), although its program 
is computationally trivial.  With some fairly minor modifications 
it should be possible to turn a tape recorder into a more general 
computing machine.

This raises several interesting questions:

 (1) Is an ideal "Continuous Turing Machine" (as described above) 
     well defined in the traditional computational sense?  In 
     particular, with no bandwidth restrictions, is the amount of
     information contained in the initial "program" finite?  (It 
     certainly is unbounded, but then so is the allowable amount 
     of information in a Discrete TM program.)
 (2) What sort of "computation" could a Continuous Turing Machine 
     perform?  For example, is it meaningful to say that a CTM has
     "computed" a real number w if it halts and the state of the 
     machine is s(t_halt) = w?  Or would it be more appropriate to
     consider the final profile m(x) at the time t_halt as the 
     "output", or the time-history of x(t) from t = 0 to t_halt?
 (3) Any history of activity x(t) over a finite range of time, or
     final profile m(x) over a finite range of x, could have been
     explicitly contained in the initial program, so would it be 
     more appropriate to reverse the usual convention, and say 
     that a CTM computes a result iff it NEVER halts?  If a CTM 
     halts, it is trivial, because its "output" is, or at least 
     could be, simply a mirror of its input.  The only non-trivial
     CTMs are those that never halt, and their "output" is the 
     completed infinite time-history x(t), t=0 to inf, or profile
     m(x), x=0 to inf, implicit in the initial configuration.
 (4) Is it meaningful to compare the computational power of a 
     Continuous Turing Machine with a Discrete Turing Machine?
 (5) Can there exist a Universal Continuous Turing Machine?

We could go on to imagine three-dimensional CTMs, i.e., we could define
a 3-dimensional scalar field m(x,y,z) and several "machines", each of 
which determines its acceleration at time t as a function of its 
current "state" and the intensity of the field at its current location.
Also, the field at or near) the current location of each machine could 
be altered by the machine.  However, this model seems unsatisfactory, 
because each machine would only be able to modify the field along its 
own path, and so would not affect other machines unless their paths 
intersected.

A more interesting model would be to dispense with the concept of 
a scalar quantity attached to each point in absolute space, and 
simply let each machine deal with a quantity that is a function of
its position relative to all the other machines.  We might call
this a Mach-Turing Machine (not to be confused with a mock-theta 
function).  For example, in a system with N machines, each machine 
could base its actions on its own current "state" and the N-1 
distances to the other machines.

A "system of continuous machines" is clearly what Laplace had in 
mind when (referring to the physical universe) he remarked that in 
principle, given the total exact configuration at any time t, the 
entire history of the system, past and future, was fully determined.  
Admittedly this view of the universe as a deterministic machine 
doesn't have much appeal today, considering the presumably random 
quantum effects at small scales and the exponential sensitivity of 
the long-term outcome to the initial conditions.  

Still, setting aside the physics (if that's possible), could Laplace's 
Machine be regarded abstractly as a computer and, if so, would Turing's
arguments be applicable to such a computer?  For example, considering 
the set of all possible "universes" and "programs" of this type, would 
it be possible to construct a "Universal Universe", i.e., a universe 
that, when given an appropriate input program, could simulate any 
possible universe of this type?  If so, could we construct an argument,
similars to Turing's, about the ability of such a computer to determine
whether it will halt? 

The reason for not allowing the input to explicitly occupy an infinite
range is that I'm trying to restrict the input in some way that 
distinguishes it from the output.  This is related to the notion that
a CTM "computes a result" iff it generates a function over an infinite
range.  Two ways it might do this are (1) it never halts, or (2) it 
reaches infinite x in finite time.
 
As mentioned above, the machine determines its (real-valued)
acceleration a(t) as a pre-established function of the current 
state s(t) and the magnetic intensity m(x) at the current location
x(t).  The acceleration refers to x"(t), but I didn't explicitly
mention the derivatives of the internal state s(t).  It makes sense
that the computer would regulate the second derivatives (wrt time) 
of both x(t) and s(t).  On the other hand, we should perhaps allow
s(t) to change discontinuously...

It was stated above that the machine can also modify the intensity 
of the field at location x(t)-d (where d is a fixed constant) by 
setting it to any desired value, or it can leave the intensity at 
location x(t)-d unchanged.  The reason for refering to x(t)-d rather
than just x(t) is that I was trying to be sure s(t) is uniquely 
defined.  Suppose at some instant t the machine is at location 
x(t) where the tape function has the value m(x)=q.  Based on this 
information the machine's state is determined to be s(t).  Now 
suppose that, at the same instant, the machine changes (instantly)
the value of m(x) from q to r, for example.  This, in general, would
result in a new state for the machine at the same instant s(t), so 
s(t) would not be uniquely defined.

We might just as well use x(t)+d instead of x(t)-d.  I even thought 
about letting it do both, or letting d be controllable by the state 
of the machine, but then I decided anything that could be done by a 
machine that varied d could also be done by one that didn't.

One of the questions above was whether an ideal "Continuous Turing 
Machine" (as described above) is well defined in the traditional 
computational sense?  In particular, we might wonder if, with no 
bandwidth restrictions, the amount of information contained in the 
initial "program" finite?  (It certainly  is unbounded, but then so
is the allowable amount of information in a Discrete TM program.)
Now, it might seem that a single real number already contains an 
infinite amount of information, but it's important to be careful 
about what we mean by "a real number" in a physical and computational
context.  We understand the old notion that we could encode the 
complete works of William Shakespeare by making a single dot on a 
piece of paper such that the ratio of the x and y coordinates on 
the page gave a real number whose digits represent the alphabetic 
characters of the text.  However, if we define a function m(x)=1-x^2
over the range x=0 to 1, is it correct to say that the information
contained in this locus of real values is the union of all the 
information contained in each individual real value in the range 0 
to 1?  I think it is not, but this is really part of the question 
I'm asking:  How do we quantify the information content of a real-
valued function?  I think Shannon's work in analog communication
systems is relevant here, and the key concept is probably bandwidth.  
Also, I believe information is context-sensitive, but I have trouble
quantifying the notion of "context" in any absolute sense.

Would a suitable halting criterion be based strictly on the value 
of s(t), or on the values of x(t) and its derivatives?  I suspect 
they could be made equivalent by having the machine drive its 
velocity to zero if/when the state falls within a certain range.

If m(x(t)) is allowed to be a function of _itself_ and s(t), then 
the function can be "solved" so that, effectively, m(x(t)) is 
strictly a function of s(t) alone.  In other words, if  s' = f(m,s)
and  m = g(m,s),  then there is a function G such that m = G(s), 
which implies  s' = f(G(s),s), so we have a function F such that  
s' = F(s), and the tape parameter m drops out completely.  

It may be worth mentioning that a continuous function is fully
determined by its values on the rationals, but does it necessarily
follow that we could define everything in terms of rationals?  Since
the rationals are denumerable, just like the naturals, it might seem
that we are back at a discrete Turing machine, but this is not the
case, because the "determination" of a continuous function is based
(in a sense) on the "completed infinity" of rationals, whereas there
is no completed infinity of entities in a discrete Turing machine.

It's also good to keep in mind that information is entirely _relative_
and dependent on the context.  For example, we could encode the 
Gettysburg Address as the integer 0.  The abstract conveyance of 
"information" is possible only given a pre-existing mapping between
a set ideas and a set of characters.  Such mappings are (or may be) 
entirely arbitrary.  The real puzzle is how, beginning from "absolute
ground zero", communication is ever possible.  I think most people 
eventually arrive at the view that there must be some 'a priori' 
mapping that humans share embedded in ourselves, that enables us 
to boot-strap up to higher levels of information exchange.

A real Turing Machine contains vastly more "information" than is 
explicitly acknowledged in the usual formal representation.  No 
string of bits is capable of _doing_ anything.  To act and change 
and compute requires a non-trivial interplay of time, space, and 
physics.  Even the act of _thinking_ about the action of a Turing 
Machine involves highly complex aspects of reality that are 
generally not accounted for in the formalization.

Return to MathPages Main Menu
Сайт управляется системой uCoz