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 some 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 ∞, 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 three-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, similar 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" if and only if 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 we 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 referring to x(t) - d rather than just x(t) is 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. We could even consider letting it do both, or letting d be controllable by the state of the machine, but presumably 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² 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? The answer would seem to be no, but this is really part of the question we’re asking: How do we quantify the information content of a real-valued function? Shannon's work in analog communication systems may be relevant here, and the key concept is probably bandwidth. Also, we should keep in mind that information is context-sensitive, although it’s not trivial to quantify 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