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”?

  • 1
    $\begingroup$ This is not an answer but I can't post comments and I felt the need to give the link to this incredible xkcd comic: [A Bunch of Rocks][1] which is related to this question :). [1]: xkcd.com/505 $\endgroup$ – Zenon Mar 28 '11 at 3:18

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/

  • $\begingroup$ +1 for the Legos -- whee! I hoped to find a phrase a little easier to roll off the my tongue than "A Turing Machine physical implementation can be composed out of this set of parts" -- but this is still vastly better than the alternatives I've seen so far. $\endgroup$ – David Cary Mar 29 '11 at 17:04

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.

  • $\begingroup$ This text is packed with interesting concepts and terminology. Alas, I don't see any phrase here which I can use as "This is a <phrase> set of components, while those are a <not-phrase> set of components". $\endgroup$ – David Cary Mar 29 '11 at 18:25

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.

  • $\begingroup$ Light bulbs and light switches can implement NAND. There is a configuration of 2 ordinary light switches and an output light bulb (and a second hidden light bulb) where the output light bulb stays BRIGHT except when a human turns both switches to ON, then the output bulb goes DARK. Alas, it is apparently(?) not possible to build a Turing-complete machine entirely out of light switches and light bulbs. Is there some term I can use that includes the 74HC132 NAND but excludes the light-switches-and-lightbulbs NAND? $\endgroup$ – David Cary Mar 29 '11 at 17:44
  • $\begingroup$ Well the problem is that the input is mechanical and the output is electrical, so switches are like a conversion nand gate between two domains (kinetics to electronics). Assuming it functions just like a nandgate you COULD make a Turing complete computer out of them, it's just that you'd have to facilitate converting between these two mediums to make output from one gate be input to another, possibly a motorized switch flipper, but yeah impractical. A term you could use that I'll just makeup now is same-medium nandgate, which stipulates the input and output be in the same medium. $\endgroup$ – acp10bda Mar 30 '11 at 7:20
  • $\begingroup$ +1 good idea -- just make up a term and define it to be exactly the term for which I am looking. The set { (a box with 2 input lightswitches and a output lighbulb that implements AND), (a light-activated motorized switch flipper that implements NOT) } is a d-universal cascading set. But the set { lightbulbs, lightswitches } alone is not a d-universal cascading set. $\endgroup$ – David Cary Mar 31 '11 at 19:20
  • $\begingroup$ Is it possible to build a Turing machine out of things that are not same-medium nandgates? $\endgroup$ – David Cary Mar 31 '11 at 19:23
  • $\begingroup$ Sorry for the lateness of this reply, but yes. A Turing machine could be made out of any assembly of components using any variety of input and output mediums so long as the components are arranged in such a way that the result is a Turing complete mechanism. However, Given that the medium of computation would become so wildly variant and potentially very interesting to watch work, I'd like to refer to such a mechanism as a Rube-Goldberg-Turing complete mechanism. :) $\endgroup$ – acp10bda Aug 23 '13 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.