Can one build a "mechanical" universal Turing machine?

This question connects different disciplines so it's awkward to choose a SE site for it, but I'll go with this one because here (I hope) the shared culture will make information transfer easier.

So computers as we know them use electricity and I don't know what other invisible things that I don't understand. I was wondering, is this a matter of efficiency, or of necessity? Can one achieve universal computation with just "moving parts"? Perhaps "Newtonian physics" is some term for this, although I guess it includes gravity which isn't really what I mean. You know, just good old solid pieces of matter moving around.

To get some picture of what I mean, here is a "LEGO Turing machine". I'm afraid that the big gray block on top uses electricity, but could one replace it with a "mechanical" thing, powered perhaps by rotating a piece? I have no idea how such things be designed, and the state transitions for a universal TM have to be fairly complicated, so I have no intuition for whether this is possible or not.

• It looks like the LEGO Turing Machine is just using electricity to power the motor. You could easily replace that with a crank, water wheel, etc. Dec 30, 2020 at 16:49
• You might be interested in this paper on arXiv: arxiv.org/abs/1904.09828. It goes pretty well beyond ‘no electricity’. Dec 30, 2020 at 17:06
• @Barmar: No, the big gray block at the top is an electronic computer (specifically an NXT Intelligent Brick). The sensors are electronic, the decision-making logic is electronic, etc. Dec 31, 2020 at 1:22
• @Barmar basically this big block is the DFA part of the Turing machine, the mechanical part is just the tape access. Replicating this in mechanics would make the whole thing a lot bigger. Dec 31, 2020 at 10:21
• Relevant XKCD: xkcd.com/505 Dec 31, 2020 at 21:02

Sure. Electricity is unrelated to the model of computation. The only thing you can't actually build is the infinite tape, for obvious reasons. In this sense, anything that can be built is essentially equivalent to a deterministic finite automaton.

• An infinite tape is just a finite tape which you promise to extend whenever the machine gets to the end (whilst pausing the computation, so the machine doesn't even notice there was an end). In case petty practical hurdles arise (like, the Earth running out of iron for the magnetic tape) the pausing may take somewhat longer (until sufficiently many asteroids have been mined, solar systems explored, the horizon of the visible universe extended etc. etc.). Dec 30, 2020 at 19:35
• You don't need an infinite tape to be more powerful than a DFA. A linear bounded automaton can be thought of as a Turing machine restricted to rewriting cells on the input tape, and can recognize context-sensitive languages. Dec 30, 2020 at 22:14
• @chepner: Sorry if this is a stupid question, but . . . doesn't a bounded tape mean that the machine+tape system has finitely many distinct states, and is therefore at most a DFA? (For example, if the tape has n cells and supports m symbols, and the machine has q internal states, then the machine+tape system has only mⁿnq possible states. No?) Dec 31, 2020 at 0:37
• @ruakh This number of states is not constant, but depends on the length of the input. A linear bounded automaton can detect palindromes, for example, while a DFA cannot. Dec 31, 2020 at 1:45
• There is a fundamental difference between a linear bounded automaton and a DFA: a DFA is "online" in the sense that it reads the input letter by letter. Thus, you can potentially feed unbounded input to a DFA. However, a TM has to have all the input on its tape at the start (and can go back and forth on it). This means that a TM has infinitely many possible configurations, even if it's space bounded, whereas a DFA only has finitely many configurations over all inputs. Dec 31, 2020 at 7:48

Sure. Not only is it possible, the first design for a Turing-complete computer was purely mechanical. This was Charles Babbage's Analytical Engine. Babbage published its design in 1837, long before electricity was considered a practical source of energy, and even longer before electronics was even imagined.

The Analytical Engine was inspired by looms. Already in the 18th century there were looms that could be controlled by a punched tape which described the pattern to weave. Babbage had first designed a mechanical calculator, the Difference Engine, where a tape described mathematical operations. The Difference Engine could only perform prearranged calculations: it didn't have the ability to run arbitrary loops. The Analytical Engine could control the direction in which it processed its control tape, and since it also had conditional execution capabilities, it could perform arbitrary loops. The Engine had an internal memory where it could store data, which made it practically Turing-complete in the sense that an arbitrary program can be run on an engine given enough memory (which is the sense in which modern computers are Turing-complete). Everything was based on moving parts (wheels, pistons, etc.), and a complete description of the state of the engine would be a description of the position and orientation of these moving parts.

The Analytical Engine was never built. It was too complex and would have been too expensive and too slow to be worth the while. It didn't even have any direct influence on the design of the first electromechanical computers in the 1930s and 1940s, because their designers were not aware of the Analytical Engine. But it had indirect influence, partly through the work of Ada Lovelace. If Babbage was the first computer hardware designer, Lovelace was the first computer programmer. She realised that the Analytical Engine could not only make numerical calculations, but more generally could process data. Lovelace's contribution also fell into obscurity, but Babbage and Lovelace's work fostered an interest into the mathematics of computation.

Beyond looms, which translated instructions into cloth patterns, there were other mechanical engines existed with no or limited power to make numerical calculations before the first electronic computers. In particular, Herman Hollerith's mechanical tabulating machine could sort data and count records matching certain conditions; it was first used to process census data.

The progress of electronics, was what made general-purpose computers practical by the 1930s to 1940s. But the fundamental ideas of machine computation had been around for about a century. Electronics aren't the only way to design a computer, they're just (so far) the only economically viable way.

• Fluidics is where water is used instead of electricity for logic gates: en.wikipedia.org/wiki/Fluidics Dec 30, 2020 at 17:05
• Like all finite machines with repeating elements, the Analytical Engine can only be thought of as universal 'in the limit' as the number of elements approaches infinity. For register machines like the Analytical Engine, we can EITHER consider the limit as the size of each register gets larger -- and in fact, a register machine with only two or three registers is universal in this sense. Babbage planned the A.E. with 40 decimal digits per register, which we could charitibly concede is close enough to inifinity. Dec 31, 2020 at 20:30
• OR we can consider the limit as the number of registers grows, always assuming that each register is wide enough to hold the address of an arbitrary register in the machine. Here the A.E. is more problematic, for although Lovelace designed a program that computed successive Bernoulli numbers from an array of previous ones, the details of how the indexing would work do not seem to have been finalised by Babbage. So along this dimension the universality of the A.E. is harder to establish. Dec 31, 2020 at 20:34

See: YouTube Matt Parker has made some small scale logic gates out of dominoes. Highly impractical, but theoretically, with enough time and space, one could build a functional computer that way. Apparently

• Interesting, and relevant enough for an upvote, but dominoes by themselves can't form a universal Turing machine. Such domino-circuits are only able to do a single computation. Without some ability to mechanically reset the gates, looping would be impossible. Dec 31, 2020 at 17:15
• If a roomful of dominoes can do one step in a computation, then we can transmit the result along a row of dominoes into the next room, where the next step happens. The only detail to settle is how we are going to suspend the computation when we run out of rooms, while more rooms are built and their floors laid out with dominoes. The same problem afflicts any physical realisation of Turing machines, as @leftaroundabout notes in another comment. Dec 31, 2020 at 20:39
• @JohnColeman That particular implementation relies on humans to do a reset, but there is no fundamental reason why a device could not be built to reset the dominoes automatically, along the lines of the machine that resets the pins of a bowling alley. In any case, I don't see that needing humans to do a reset entirely counts this out, any more than the need for human input would have invalidated Babbage's machine. Jan 4, 2021 at 8:58

All computers can be though of as "mechanical", broadly speaking, be they electronic, digital or analog, even "fluid" computers. What's interesting about universal Turing machines is that they allow us to consider machines as encodings in a systematic and general way. Not unlike the numbers they're supposed to compute.

That allows us to virtualize computers, which is arguably what makes them so interesting, both theoretically and in practice.