The Power of One-State Turing Machines (2018)
nearly42.org
nearly42.org
Turning Machines are a simple, purely hypothetical, machines that have allowed computer scientists/mathematicians to conclude very profound properties of computation. Although they are mentioned with some frequency here, it's not a subject that most of us have any training in.
I had the good fortune to study computer science while in college many years ago. There was a lot less to learn back then and I was introduced to the theory of computation at the undergraduate level.
For those that haven't had the pleasure of problem sets covering Turing Machines but would like to learn something about them, I recommend the Stanford Encyclopedia of Philosophy entry on Turing machines [1]. It goes into more depth than Wikipedia while being very easy to understand.
Turing machines are extraordinarily simple, much simpler than any real computer. The fact that Turing Machines deserve an entry in a Philosophy reference is because of their power in elucidating the very nature of computation.
About 80+ years ago, it was discovered that the set of problems that can be solved/computed by a Turing Machine is exactly the same set that can be solved with the Church's Lambda Calculus, [2] and recursive functions as formalized by Gödel's [3]. This, to me surprising, result led to the Church-Turing thesis: the hypothesis that any effectively computable (i.e. solvable through some mechanistic procedure) can be solved by a Turning Machine. From this we know, for example, that true algorithms don't exist for a whole host of problems. This isn't the same claim that some problems are hard and don't have tractable exact solutions (e.g. the knapsack problem or the traveling salesman problem [4]); there are algorithms for these problems--they simply take a very long time. Some interesting problems on the other hand have no algorithm at all. This can be shown by demonstrating that no Turing Machine could be constructed to solve the problem (e.g. the halting problem [5]).
What about quantum computers? They look like an approach so different and so powerful that maybe they will provide a stronger model of computation than that limited by the bounds of Church-Turing. Unfortunately, the qubit based approaches that we are now pursuing have been demonstrated to be "equivalent" to classical (Turing) machines, just with different performance time/space tradeoffs. So qubit based quantum computers may someday solve challenging, exponential time problems, but they won't solve every problem.
## Turing machines
Turing's insight was that any mechanical procedure for computation could be modeled by a simple machine, the Turing Machine. A Turing Machine has a "tape", think of it as an infinite strip of paper divided into cells, like an infinite array: tape[k]. Each cell can hold a symbol from some finite alphabet.
There is a single read/write head positioned at a location on the tape. The head can read a symbol from the location or erase/write a symbol the location, and then it can move one location left or right.
Turing machines also have a state from some finite range of states, say 1...N. One state is designated as the initial state.
Finally, there is a state transition table in the Turing Machine that determines its operation. For each combination of (1) current state and (2) current symbol under the read/write head, the transition table gives (a) the new internal state and (b) the symbol that should be written on the tape at the current location and (c) the direction the head should move--left or right.
When I first saw the definition of a Turing Machine, I thought that it looked unlike a computer. The state table seemed to encode the entire operation of the machine. It could potentially be a huge table of specific operations to solve some problem. Turing machines seemed to me to be special purpose constructions unlike the more flexible architectures of programmable computers. Indeed, we studied a number of different Turing Machines that would solve simple problems with inputs from the tape.
The big surprise for me was seeing a Universal Turing Machine. It turns out that there are Turing Machines, having a fixed reasonably small state transition table that can do anything that any other Turing Machine can do. These "Universal" machines use a program on the tape that provides the instructions to process the remaining input data from the tape.
The idea of a Turing Machine doesn't rely on lots of states, a few is enough to construct a universal machine. Likewise, there are Universal machines that need a tape that extends in only one direction and tape vocabularies that have a very limited number of symbols.
[1] https://plato.stanford.edu/entries/turing-machine/
[2] https://plato.stanford.edu/entries/lambda-calculus/
[3] https://plato.stanford.edu/entries/recursive-functions/
[4] https://en.wikipedia.org/wiki/Travelling_salesman_problem
It takes the paper where Turing originally introduced and analyzed Turing machines, and explains it line by line, provides examples and corrections, and historical and biographical material to put it all in the context of the time and of Turing's life.
OUTPUT: https://en.m.wikipedia.org/wiki/Arbitrariness#See_also
#~~
(trying to scratch together code you can run that'll answer your question.. hm, the initial function is untyped without a better sense of 'number'.)
This means, in particular, that you can annotate symbols on the tape by having different variants of each input symbol, so long as the number of variants is strictly bounded.
(1) There are many equally-powerful variants, so there’s no guarantee that others will be working with the same definition.
If your single state has the increment lookup table for a single cell, you just need to move to the next cell to do carries, and move to the previous cell to leave the counter when you're done. A special carry character is written instead of zero to make sure you leave the whole counter, and you convert it to zeroes as you leave.
* only binary alphabet, or allow any finite alphabet on the tape(s)
* tape is infinite in a single direction or in both (and various possibilities as to how to handle reaching the edge)
* there is one tape or there are more
* the head has to move every time, or can it remain on the same cell
* etc.
And they are all equivalent in terms of computability (ie. they can compute the same functions), and mostly equivalent in terms of algorithmic complexity (ie. they take the same time to run, up to a polynomial).
So almost no one bothers actually saying which model they use, unless they are doing a rigorous proof.
However, when papers like this one say "Hey, let's take my favorite model of Turing Machines and restrict it so that [X]", then the results highly depends on what their favorite model is. Except they don't always bother saying which one it is.
For example, if you restrict yourself to Turing Machines with a single state, two tapes, and any alphabet allowed on at least one of the tapes, then it's enough to emulate any one-tape Turing machine, simply by writing the state on a single cell of the second tape and repeatedly read it. Which in turn are known to be able to emulate any conventional model of Turing Machines.
It is explicit about having an arbitrary alphabet, a single tape that's infinite in both directions and that the head has to move every time.
I don't think I've ever seen anyone restrict a Turing machine in a novel way and not follow that up with a rigorous proof.
The parent's point is that the Turing machine model of computation admits a very concise definition -- roughly a page depending on brevity and formatting. An industrially viable programming language or hardware architecture typically requires a standard spanning hundreds of pages to define.
The simplest way I can describe them without any maths is that at any point in time they have two inputs, and three outputs.
The inputs:
* The current "state" of the machine, which is usually shown as a letter - there are a finite number of states the machine can be in, but this number can be as big as you like.
* The value currently being pointed at on the tape. The possible values are again finite, but can be as big as you like.
The outputs:
* A new value to write on the tape.
* A new state to be in.
* Whether to shift the tape left or right.
If you choose your mappings from inputs to outputs carefully, this machine can solve literally every problem your desktop computer can solve. I'd call that pretty amazing.
Conway's game of Life is simpler, and universal. People have invented probably hundreds simpler than it. TM gets pride of place as the first, and for no other reason.
(1) The other is Church’s lambda calculus
There's some understanding that I'm fundamentally lacking which I've been searching to correct for years. I've put it down to "Math" which seems to be a whole impenetrable language itself. A language that my lack of understanding of (despite many unguided attempts) means I'll continue to be downvoted and snorted at when I say I still don't understand what a Turing machine or a monad actually is.
And yes, mathematics is a language; it is the language for modelling the phenomena we experience in the world, including the non-physical (contracts, data / counting, etc.).
I so, so, so wish that people were taught that mathematics is a language of relationships rather than one of rote numerical calculation. I think more people would stick with it. It's a shame, because the doors it opens are huge.
The long(er) answer? Mathematics are more limited, and thus, at least on the surface, provide a more rigid model.
Plus, we have about 4500 years worth of equations that we know to be accurate; not so true for C or any other programming language. Plus, we can model all the way down in mathematics, as it is more abstract in nature.
The long(est) answer? It's turtles all the way down.
The fundamental point of the Church-Turing thesis is to show that everything computers can do can be described by mathematics, so any programing language has either the same or less power than math. They are certainly easier to use for many problems, though.
Additionally, Gödel showed that there are true statements that can be described but not proven by math, ao it can never be a perfect model of the real world.
I assume you are refering to Gödel's incompleteness theorems; but this is not what they "say".
What they say is that any formal system powerful enough to contain basic arithmetic is either inconsistent (ie. it can both prove and disprove a particular theorem) or incomplete (ie. cannot either prove or disprove all theorems).
If you take the ZF set theory, for example, it is incomplete, because some statements cannot be either proved or disproved within ZF, such as the Axiom of Choice (AC) or Zorn's Lemma.
However, that doesn't imply that ZF cannot be "a perfect model of the real world", because the AC is irrelevant in a the real world, because the AC only applies to infinite sets, which do not exist in the real world.
Slightly longer answer: To the extent that they are formal languages, they both have the same ability to express things.
More philosophical answer: Mathematics has a tradition of extension. Have a new idea you want to express as concisely as possible because you are going to be using it a lot? Grab a handful of Greek letters, symbols, funny fonts, and random other typography, and go to town. Outside of Lisp,[1] this flexibility is hard to do in most programming languages.
[1] But inside a dog, it's too dark to read.
Probably the most visible outcomes of this work is complexity analysis of algorithms- you can’t talk about how much computational effort you need to do something until you have an agreed measure of computational effort. How many steps or tape cells a Turing machine would need is that fundamental measure, in a similar way to how the speed of light is our fundamental measure of velocity; they’re essential to our understanding of the field but not used on a day-to-day basis. Instead, we use more convenient ones that are themselves derived from the first-principles units.
As with many other interfaces, there are a few rules in the comments that implementations are expected to adhere to.
Consider the notion of an algorithm. You are probably familiar with an algorithm: a series of steps to be completed by a computer (aka a person).
This is the launch point for what a Turing machine is. Turing asks the question: if there exists a machine that can slavishly follow instructions, what can such a machine do, and what can such a machine NOT do?
To answer this question without invoking the AI problem, Turing started with the simplest possible set of objects to work with: binary numbers. A simple machine then would be a machine that reads a "tape" of binary numbers. The machine is simple, so it can only read one number at a time. Based on the number read, the machine may either move the tape left (reading the next number), move the tape right (read the previous number), replace the digit on the current cell, or halt.
You can see why such a machine is considered simple: The range of inputs and the action space is VERY limited.
And yet despite its simplicity, it's shown that such a simple machine can do addition. Specifically it can perform computation on recursively enumerable problems. It is in this very narrow and specific sense that Church's Lambda Calculus and Turing's machines are considered equivalent. Modern authors tend to extend the reach of Lambda Calculus, but you should bear in mind that the Church Turing thesis is valid only for functions N->N. That is to say if a Turing Machine can calculate the result of a function that takes a natural number and returns a natural number, lambda calculus can calculate the same result, and vice versa [sidenote].
Now, having a machine that can do all that is pretty cool. Ideally you'd want to be able to describe the rules of the machine. That's called a programming language. This notion really only formalized itself way after Turing died. Aho, Ulman and gang were really the ones who made the connection between languages and automata. Wang's B machine introduced the notion of abstraction in Turing machines by adding compound features that can be translated to simple Turing machines (for example, an instruction that would be "delete the value, and move right"). This led to the study of programming languages. The family of imperative programming languages are inspired by Turing machines in this manner.
[Sidenote]: If only functions of N->N are comparable for the Church Turing thesis, then why do people generalize it to all kinds of functions? A cheap trick is to say, all functions can be Gödel-string encoded. A G-string is a huge natural number that represents a function. Thus if you can find the Gödelized function, then all functions are computable by both formalisms. I find this a bit distasteful - when we compute with CPUs we don't actually compute Gödel numbers!
This is not correct. The concept of algorithm has nothing intrinsic to do with natural numbers. You could use any data structure, e.g. finite strings of symbols from a fixed (per application) finite alphabet as is used in Post normal systems. The Lambda Calculus is also an example, as it doesn't use natural numbers, but its own expressions.
The class of computations that Church and Turing are equivalent are the functions from N to N (encoding required obvs), as proven by Turing. Everything else is conjecture.
Turing gives "computable by Turing machine", and Church gives "effectively calculable by the lambda calculus". Kleene holds them both to be the same, culminating in Theorem XXX. This misses a subtle point that this only applies up to the class of functions from N->N.
When the class of functions is S->S, where S is a string or tree of symbols, lambda calculus runs into some minor issues. For example, you cannot define equality of terms in lambda calculus nor can lambda calculus realize itself.
Bob Harper's book is the only book I know of that was explicit about this fact, though he dismisses it as a minor issue. Barendregt surprisingly also missed this.
> Young man, in mathematics you don't understand things. You just get used to them.
This was John von Neumann talking.
I'd be careful with that, you need to formalize "any possible algorithm" first, and that's the content of Church-Turing I believe.
Edit: Also, don't forget recursive functions (dating from I don't know when, actually)
To my knowledge, recursive functions alone are not sufficient to describe all computation. To do that, you need to consider functions as first-class values which is the innovation Alonzo Church came up with concurrently with Turing’s work.
> recursive functions alone are not sufficient to describe all computation.
Any function computable with TM is recursive, and vice versa, so they should be, if you understand "computable" as "computable with a TM". I don't see how this "functions as first class" comes into play here, but I'd be interested anyway?
Before Church, functions weren’t considered mathematical objects that could be passed as arguments to another function, for instance. I don’t recall the details, but this allows some computations that can’t be described by recursion of fixed functions.
This strikes me as profoundly ahistorical. Mathematicians have considered function spaces as families of objects to be operated upon by higher-order functions (themselves considered objects to be operated on, and so on) long before the 1930s. I'm sure some version of this thinking has been part of the "folklore" of mathematics for centuries, but at the very least you have to recognize that the idea of higher-order functions is subsumed by Cantorian set theory in the 19th century.
Edit: if you mean to say that a formalism for higher-order functions was novel in its presence in a computational calculus, your remark makes a little more sense. But a few remarks on that:
* Already in 1933, Herbrand–Gödel μ-recursion had given a model of computation that was equivalent to the lambda calculus. (This could be the "recursion" that the post you're responding to was referencing.) I guess the μ operator could be regarded as a higher-order function, but functions don't really play a first-class role in the μ-calculus.
* It's probably more accurate to say that the lambda calculus was conceived as a logical formalism, of which Church published only a computational fragment when it became apparent that the original calculus was afflicted with the Kleene-Rosser paradox. Higher-order functions (and predicates) had already played a role in formal logic systems for decades prior to this.
This is why you see some "shitty" esoteric programming languages where you think that nothing useful can be done, like Brainfuck end up being Turing-complete. The same is true for logic circuits, alone NOT, AND and OR are sort of useless, but get NOT and another one and now you can start building anything. Even some board games are Turing-complete, probably MtG is not the simplest example, but I bet there's a bunch of other ones that I don't know about.
*Or some other simple model of computation that's polynomially invariant wrt Turing machines, but at this point I don't think "you don't need Turing machines" remains as salient.
I think we agree that as a matter of actually building the topic of NP-completeness, nailing down a concrete model of computation for the verifiers which can itself be operated upon constructively is vital.
The only other influential, foundational turing-complete language is Church's lambda calculus, which is much nicer to reason about and led to the development of functional programming.
In fact, comparing Turing machines and Lambda calculus gives you an approximation of how much easier functional programs are to write (provably) correctly than more conventional ones.
That said, since in this case one is working with predicate transformers, which are mathematical objects, perhaps one can support the claim that it's just applying functional methods to imperative programming. I'm not so sure, but in the end it's not very important to me either way. I just like knowing that I have strategies for writing good programs be they functional or imperative.
This does make me doubt the practical usefulness of the Turing machine model for the professional software engineer though. I'm not aware of any technique that derives nontrivial correct programs using Turing machines. While the most formal predicate transformer based approaches are relatively rarely used and only for the trickiest problems, anyone who is familiar with both will recognize that properly applied TDD is extremely similar, so much so that I consider it a sufficiently rigorous informal approximation for the vast majority of practical cases.
[1] https://www.cs.utexas.edu/~EWD/transcriptions/EWD04xx/EWD472...
A Turing machine shows how you can recreate all of this with just a strip of paper and a lookup table. It is incredibly simple, and yet it can reproduce any operation your shiny new machine can (at least in theory). This formalism provides a way to study computation abstractly, without worrying about how much RAM something has, or whether it uses RISC or MIPS instructions. Since it’s so simplified, it can also be used as a yardstick to determine whether other “symbol-processing systems” (C Macros, PostScript, Magic: the Gathering) can support general-purpose computing.
So, once upon a time, Alan Turing needed a formal model of computation, as in what a mathematician could do to solve a problem with a sufficient supply of pencils and paper.[1] What Turing came up with is essentially a finite state machine attached to a "tape" which could read and write symbols and move left or right. (In the simplest model, the machine starts at one end of the tape, which is unbounded in the other direction.) There are two neat facts about this machine:
(1) The Turing machine is universal: you can construct a machine that takes as input a description of any other Turing machine and its input, and can perform the same computation as the other machine.
(2) You cannot do anything obvious to increase the power of the machine, as in constructing a machine that can compute something a Turing machine cannot. Examples: making the tape unbounded in both directions? Adding multiple tapes? A two-dimensional tape? Nope, all can be emulated by a standard machine. You can reduce the power of a Turing machine; remove the tape entirely and you have a finite state machine;[2] limit the use of the tape to the most recently written symbol and you have a stack machine.
(3) Turing machines are closely related to other, rather different, things. On one hand, those finite state machines are equivalent to regular languages, stack machines are equivalent to context-free languages, and Turing machines are equivalent to context-sensitive languages. On the other hand, Turing machines are equivalent to the other "reasonable" definitions of computation: general recursive functions and the lambada calculus, for example. In addition to not being able to extend the Turing machine for more power, all of the models of computation that are more powerful "cheat"; for example, being able to do an unbounded amount of computation in a single step.
For more details, see your local automata theory course.
[1] Turing needed the computation model because he wanted to know whether you could separate Gödel's unprovable sentences from normal-human-being, provable sentences. But that's not important right now.[3]
[2] Side note: All physically implementable computers are equivalent to finite state machines. But we generally hand-wave that away.
[3] You can't.
But my head exploded, contemplating the awesome power of the "lambada calculus".
(I am revisiting SICP this month, you have profoundly affected my enjoyment of the Abelson-Sussman video lectures [2]. In a good way, I think.)
SICP: https://news.ycombinator.com/item?id=13918465
videos: http://www.youtube.com/playlist?list=PLE18841CABEA24090
Totally unaffiliated. Actually saw this via the only Twitter ad I’ve ever found even remotely relevant.