Have anyone ever thought of continuous analog Turing machine?

1.7k Views Asked by At

Have anyone ever thought of continuous analog Turing machine? The machine adopts continuous (from R) the input data from the tape, It moves to a different state depending on the value on the tape. On the output tape Turing machine writes real numbers according to its program. Is it possible to construct a computer on these principles?

2

There are 2 best solutions below

2
On

Yes. Quote:

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.)

About the question: "Is it possible to construct a computer on these principles?", analog computers were invented before the digital ones. The problem is that infinite resolution isn't more possible than infinite tape.

0
On

Certainly it is possible to build a computer on that principle: Every integer is just a special case of a real number, and thus the continuous machine can emulate a standard Turing machine.

Or the machine could emulate a TM tape by simply treating every negative number on the tape as zero, and every positive number as one. It then would write only $-1$ or $+1$. Indeed, that's essentially how our digital computers work: Voltages and currents are continuous quantities (well, at least at today's dimensions of electronic components), and electronic components are also continuous in nature. However by using non-linear electronics, it is possible to interpret every sufficiently low value as 0, and every sufficiently high value as 1.