Is there a name for "physical things out of which one can build a Turing machine"?

Question

One of the amazing things about computer science is that the physical implementation is in some sense "irrelevant". People have successfully built computers out of several different substrates -- relays, vacuum tubes, discrete transistors, etc. People may soon succeed in building Turing-complete computers out of non-linear optical materials, various biomolecules, and a few other substrates. In principle, it seems possible to build a billiard-ball computer.

However, the physical substrate is not completely irrelevant. People have found that certain sets of components -- in particular, diode-resistor logic -- are "incomplete": no matter how many of them you connect to a power supply and to each other, there are certain very simple things that it cannot do. (The diode-resistor logic can implement AND, OR, but fails to implement NOT). Also, certain ways of connecting components -- in particular, single-layer perceptrons -- are "incomplete": there are certain very simple things that they cannot do. (A single-layer perceptron can implement AND, OR, NOT, but fails to implement XOR).

Is there a less-awkward phrase for "physical things out of which one can build a Turing machine"? Or for the opposite, "physical things that, no matter how many of them one has, cannot form a Turing machine"?

For a while I used the phrase "functionally complete set" or "universal set of gates" -- or, when speaking to mathematicians, "physical things that can implement a functionally complete set" -- but I've been told that isn't quite correct. Some sets of components can implement a functionally complete set; and yet it is not possible to build a Turing-complete machine entirely out of these components. For example, light bulbs and manually-operated 4-way light switches can implement a functionally complete set (AND, OR, NOT, XOR, etc.); and yet it is not possible to build a Turing-complete machine entirely out of light switches and light bulbs, since the (electrical or optical) output of one cannot be fed into the (mechanically rotating) input of the next.

related: Is there an official name for a notion of "reusably universal"? and Is there a name for “chips out of which one can build a CPU”?

Answer 1

Physics models reality with theories that define a concept of time-dependent state associated to a system and a time-evolution operator that describes how this state evolves. As soon as you find a physical system that (after some state-space discretization) implements the state space of your Turing machine, and that features interaction terms that implement (maybe after some time discretization) the time evolution according to the state transition table of your Turing machine on its state space, you have found a Turing-complete physical model of your system. Thus you can arguable say, your system "is" Turing-complete.

When looking at quantum computing, you will find discussions of implications physical theories have on the Turing model of computation. For example, physical theories have to be reversible. A property, which is not shared by ordinary Turing machines. Yet there is no loss in generality, as any Turing machine can be simulated by a reversible one, with some overhead that can trade-off time vs. space, etc.

Answer 2

Just thought I'd point out that completeness of a physical medium to simulate the logic required to make a Turing complete computing machine can be established solely in it's ability to embody a NAND gate, as all other gates can be derived from NAND gates (one might ask what then comprises the NAND gates, and that's a very clever question, but it's NAND gates all the way down!).

You should look at the work of Charles Babbage, and the people he inspired. Babbage made a physical computer to tabulate polynomial functions into printed tables for Math indexes (back in the day you'd have stacks of books that had nothing but function names followed by sheets of f(x) values) He latter started work on what would have become a Turing complete computer using cogs cams and such. His son I believe it was continued his work and the only physical manifestation of their combined efforts was a fully functioning mechanical ALU which is the basis of those mechanical calculators you may or may not know about. However the funding for these projects dropped off as a mechanical computer in the size and manner that they could be made in that time was very impractical. However since then, and especially in recent events, people have gone through and are furthering Charles Babbage's research. This approach may have it's last laugh, as there are those who think the only way to make serial CPUs any faster than they are now would be to implement some of these mechanical approaches within a CPU averting the issues spurring from electromagnetics at a scale smaller than the one we use now. Mechanics work on any scale seemingly.

Similarly, work has gone into what is called the Quantum computer which seeks to facilitate large computations through quantum theory, I'm not entirely sure how it all works. But it physically appeals to particle physics experiments that rely on quantum theory.

There are I'm sure many more different mediums of computing being explored, even rocks in the desert, but of them I have no experience.

Answer 3

I believe an appropriate term is "a Turing Machine physical implementation".

The main problem with any implementation is how to provide "infinite tape" or in a more abstract level, infinite memory. An easy solution to this problem is to use a special symbol to indicate the last tape square. When a Turing Machine reaches it, it enters a special state which requires user intervention, who is supplying extra tape. Then, the TM can continue its operation. Unfortunately, such implementations being "physical" involve physics. If the universe is finite and due to the Planck scale, there is a finite amount of tape available. This is where problems arise that perhaps cannot be answered by computer scientists but by physicists. Note that physicists have not reached a conclusion on those matters, which are considered major open problems of the magnitude of $P \neq NP$, so it would be unlikely that a computer scientist would resolve them.

You can read more in Scott Aaronson's paper NP-complete Problems and Physical Reality , especially in the Analog and Relativity computing section.

You can also find a lego implementation (with finite tape) in the following page: http://legoofdoom.blogspot.com/