The Power of One-State Turing Machines (2018)(nearly42.org)
nearly42.org
The Power of One-State Turing Machines (2018)
http://www.nearly42.org/cstheory/the-power-of-one-state-turing-machines/
55 comments
Another good resource, both for people whose CS education covered Turing machines well and for people who don't know much about them, is Charles Petzold's book "The Annotated Turing" [1].
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.
[1] https://en.wikipedia.org/wiki/The_Annotated_Turing
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.
[1] https://en.wikipedia.org/wiki/The_Annotated_Turing
Okay I'll volunteer to be the dummy who says I don't get it. The cell of a Turing tape can contain an arbitrary number? The head of Turing machine can add?? I think my underlying assumptions have been violated, which means either I have something interesting to learn or this is a bad result. Probably the former.
There are many ways to define Turing Machines:
* 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.
* 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.
Looking at the first page of the linked PDF, it's not explicit about whether the alphabet must be finite, although it's implied by the summary saying that addition can only be done modulo some finite value.
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.
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.
Not arbitrary. Modulo some constant k, the size of the tape alphabet. They're just choosing as the tape alphabet the set { 1, 2, …, k-1 }, and as the transition function one that maps each n to n+1 mod k. It's just a lookup table.
The transition function can only do modular addition within a cell, but the paper also describes how to build a k-ary counter.
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.
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.
In the Turing machine formalism that was taught at my university(1), the set of symbols that can be stored in a cell must be finite, but can otherwise be anything needed to solve the problem at hand. For each state in the associated state machine, there’s effectively a lookup table that maps the current tape symbol to some other, and an instruction about how to move the tape head for the next step.
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.
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.
The tape cannot contain arbitrary numbers, but symbols from any finite alphabet, which can be int256_t, and the transition function can be any partial function on pairs of tape symbols and input states.
INPUT: can? "contain an arbitrary..." & ifnot= "something interesting to learn"
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'.)
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'.)
I've never understood what the fascination with Turing machines is or what they actually are.
Hah! Coding bum, here! (Wait, no, wrong hat.) Computer scientist, here!
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.
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.
I was going to point out a typo (more likely autocorrect).
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
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
Hah! Someone noticed! My existence is validated!
What's fascinating IMO is the realization that being able to compute
anything needs very little requirements, that more complex models
of machines, way different or with "obvious" improvements like more
tapes, symbols or random access can't actually do more, but only
hope that implementations end up being faster despite having more
complex steps.
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.
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.
Well, surely the former is a consequence of the latter. Maybe it’s time to learn?
It’s one of two(1) concurrently-developed mathematical formalisms that each have been proven to be at least as powerful as any possible algorithm, and were in fact used to codify what an “algorithm” is in a formal sense. It had only been a vague, intuitive concept before.
(1) The other is Church’s lambda calculus
(1) The other is Church’s lambda calculus
This is why I've never understood what it is. I see words, (and it's not that I don't understand what those words mean) but I simply don't know what is meant by them arranged in this way.
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.
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.
Part of what makes this one hard is that it’s an essential foundational step but rarely used in practice— everything that’s actually useful about Turing machines is several levels removed from symbols on a tape.
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.
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.
Maybe this will help:
> Young man, in mathematics you don't understand things. You just get used to them.
This was John von Neumann talking.
> Young man, in mathematics you don't understand things. You just get used to them.
This was John von Neumann talking.
You are correct; you can learn what these things "are," but without at least some of the mathematics, it's going to be tough to fully grasp.
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.
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.
I don't quite understand how mathematics are more adapted to model the world than a programming language.
Short pithy answer: Exact real arithmetic is still an open research problem.
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.
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.
The short answer, they are not;
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 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.
> Mathematics are more limited
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.
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.
> 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.
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.
Gödel theorem does not say anything about the real world.
Mathematics are a superset of physics as they allow to explain all possible universes not just our.
I've yet to see one concrete statement that ZFC can't explain. There's a list of such statements on wiki if I remember well.
In programming languages, `Monad` is just an interface with the methods `map`, `flatten` and `pure`.
As with many other interfaces, there are a few rules in the comments that implementations are expected to adhere to.
As with many other interfaces, there are a few rules in the comments that implementations are expected to adhere to.
OK, let me try.
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!
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!
> ... you should bear in mind that the Church Turing thesis is valid only for functions N->N
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.
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.
Church-Turing concerns computations not algorithms. The difference is subtle. A "computation" is what we would call a function application today - given an input, compute the output based on some rules. An "algorithm" is a set of such rules, usually operational rules (do this, then do this).
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.
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.
> proven to be at least as powerful as any possible algorithm
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)
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)
Well, at this point it’s a tautology because, as you pointed out, “algorithm” is defined in terms of a Turing machine.
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.
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.
I was bothered (for lack of a milder word!) by your use of "proved".
As far as I understand, the major problem is that "algorithm" is sort of undefined.
To actually prove that TMs are universal, you need to set the formal stage, which implies having a formal definition of an algorithm.
But this is not really done, and Church-Turing essentially states that any reasonable formalization of algorithm ends up being equivalent.
But this is not tautological at all, to me.
> 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?
> 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?
> 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.
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.
> Before Church, functions weren’t considered mathematical objects that could be passed as arguments to another function, for instance.
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 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.
Recursive functions:
https://plato.stanford.edu/entries/recursive-functions/
https://plato.stanford.edu/entries/recursive-functions/
That's because for some reason, people treat computer science and programming as the same thing. IMO they're completely separate things, at least in practice.
That is why I hire people who studied Computer Engineering in preference to Computer Science. The latter are useless for making things that work well.
So the cool stuff about Turing machines is that if you get them, then you get a theoretical model of computation. And based on this knowledge you can really understand some problems, say is P = NP? Or maybe you encounter some problem at work and you cannot find an efficient algorithm to it, so you might try to prove that the thing you are working on is NP-hard (making it non trivially solvable in human words).
You don't need Turing machines for P and NP. Most reasonable models of computation are equivalent to Turing machines up to polynomial factors.
I don't think you need to reach for Turing machines to specify P or NP, but I think it's fair to say that Turing machines* play a key role in establishing NP-completeness. (And other completeness phenomena.) Computational hardness is computational universality turned on its head, e.g. a problem X is NP-hard because someone has been able to figure out how to smuggle full-blown time-bounded nondeterministic Turing machines into instances of X.
*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.
*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 meant that you don't need to know what a Turing machine is to understand what P and NP are or prove that a problem is NP-hard. I've seen a lot of people try to explain these concepts to lay audiences and Turing machines are almost never mentioned.
Fair. The topic is often taught to students without broaching the topic of Turing machines.
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.
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.
If you crack open a computer, the stuff inside looks incredibly complex. It’s filled with giant capacitors and transistors that are nanometers across (and billions of them!)You might think that you need all this stuff—-or at least the giant machines of yore—-to do interesting computation, but you don’t!
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.
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.
To expand on the why:
They are the theoretical foundation for imperative/procedural programming. Things like assembly or C would not exist without Turing machines.
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.
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.
With discipline and the proper application of the predicate calculus it's no harder to write provably correct imperative programs than it is functional ones. I'm most familiar with the work of Dijkstra and Scholten, but I'm certain that Hoare, Lamport, and many others have made great use of the technique or very similar ones. Note that this method is not proving the correctness of arbitrary programs, it is deriving programs that must be correct because of the way in which they were written. The introductory paper[1] is readable and short and I recommend anyone interested read it.
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...
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...
Get one of these. I bought one for my mate’s kid and I don’t know if the kid has been able to get near it yet. It’s a magnificent toy.
https://www.turingtumble.com/
Totally unaffiliated. Actually saw this via the only Twitter ad I’ve ever found even remotely relevant.
https://www.turingtumble.com/
Totally unaffiliated. Actually saw this via the only Twitter ad I’ve ever found even remotely relevant.
It is the simplest possible computer which can actually be built.
No. It is the simplest that they could think up at the time. Much simpler ones have been invented since.
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.
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.
They don't look so simple tonight.
There are plenty of visualizers out there to help out e.g. http://turingmachine.io/
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.
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.
You're reading a paper that analyzes the capabilities of a particular highly-constrained subclass of Turing machines. Actual research findings aren't necessarily going to be simple just because the model of computation being studied is simple. (Although a similar investigation into the capabilities of, e.g., a similarly constrained subset of Python, would probably tend to be a whole lot more lengthy and arduous.)
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 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.
That should make you think about the complexity of all other possible computers
If you consider the actual complexity of any computer that has actually been built then a TM is, by comparison, very simple.
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
[5] https://en.wikipedia.org/wiki/Halting_problem