Back in the 1930′s — before general-purpose computers, notice — Turing asked himself the question “what is computation?” and came up with the simplest possible model of what it means to compute something. That model is the Turing machine.
A Turing machine consists of a finite state machine interacting with an infinitely long tape divided into an infinitely long string of cells, each of which can hold a single symbol drawn from a finite alphabet. The machine can move along the tape in either direction, read symbols, and write symbols. For the exact details, see any number of sources on the Internet.
A Turing machine can be viewed as computing a function: you put a value on the tape, encoded in the alphabet, set the machine running, and if it eventually stops, decode whatever is now on the tape to give the result of that function. (If it never stops, the function is not defined for that value.) The definition of the function is encoded in the finite state machine, which will be different for each function, but there are also “universal” Turing machines which can compute any computable function by being given a finite program for calculating it on the tape when it starts.
The importance of Turing machines lies in this: every simple model of computation anyone can come up with is either less capable than the Turing machines (e.g. finite state machines with no infinite tape) or exactly equal in capability. The Turing machine model, simple as it is, exactly captures the idea of “computability”. That this is so is called the Church-Turing thesis. As it is about the intuitive idea, the thesis is not a theorem, but no-one has been able to come up with anything that is intuitively “computable”, but is not Turing-computable. In particular, all of the simple variations of a Turing machine, like giving it more tapes, or more symbols, or an n-dimensional tape, and so on, do not change what it can or cannot compute.
I was going to recommend a rather old book by Marvin Minsky, “Computation: Finite and Infinite Machines”, which I devoured in the space of a week 40 or 50 years ago, which exhaustively goes into the details of Turing machines and several equivalent models, but I see that it goes for around £50 second hand, and there does not seem to be any online copy. But the Wikipedia article is otherwise a good place to start. Especially read the historical section. The question “what can be computed by machinery?” goes back to Babbage in the 19th century.
Somehow I never understood this idea of how such a simple (even if it’s theoretical) machine really captures the idea of computability. I’m still fuzzy on the how, but I think I have a much better understanding of the what after reading your comment. Thank you!
And my interest is piqued. I’m going to pursue an understanding of this now. I’ll probably reply to this comment at some point with further questions but it’ll take me some time to read and think first.
The importance of Turing machines lies in this: every simple model of computation anyone can come up with is either less capable than the Turing machines (e.g. finite state machines with no infinite tape) or exactly equal in capability.
I’m not sure what work “simple” is doing there. There are theoretical models of hypercomputation (more power than Turing machines) , but we can’t build them, so the Turing limit appears to be a physical fact, not a mathematical one.
“Simple” is indeed doing no work and should have been omitted.
The thesis that computation beyond the Turing limit is physically impossible has also been proposed. We can imagine various sorts of hypercomputation, but as far as we know, they can’t be built. This version of the general idea that Turing-uncomputable functions cannot be computed is known as the physical Church-Turing thesis. In principle, given some particular mathematical theory of physics, one might be able to prove it as a theorem.
It has been speculated that quantum physics might reopen the question by allowing some new ways of calculating things that are not possible in classical physics. I think Scott Aaronson has written on the subject, and has proposed that if a theory of physics does allow computability beyond Turing, that in itself is evidence against the theory.
I think Scott Aaronson has written on the subject, and has proposed that if a theory of physics does allow computability beyond Turing, that in itself is evidence against the theory.
I would disagree, at least I wouldn’t give it much evidence against.
In some sense, this is me being annoyed at how much people think that the principle of normality/Egan’s law universally applies. This is a very clear failure case of the principle of normality, because conditional on hyper computers being buildable, then it doesn’t add up to normality, but to extremes.
It has been speculated that quantum physics might reopen the question by allowing some new ways of calculating things that are not possible in classical physics.
No, quantum physics does not allow you to make computers beyond Turing machines.
This. There are scenarios where mathematically speaking, you can construct machines more powerful than Turing machines, but they rely on physics that as far as we know can’t be instantiated.
On Turing machines:
Back in the 1930′s — before general-purpose computers, notice — Turing asked himself the question “what is computation?” and came up with the simplest possible model of what it means to compute something. That model is the Turing machine.
A Turing machine consists of a finite state machine interacting with an infinitely long tape divided into an infinitely long string of cells, each of which can hold a single symbol drawn from a finite alphabet. The machine can move along the tape in either direction, read symbols, and write symbols. For the exact details, see any number of sources on the Internet.
A Turing machine can be viewed as computing a function: you put a value on the tape, encoded in the alphabet, set the machine running, and if it eventually stops, decode whatever is now on the tape to give the result of that function. (If it never stops, the function is not defined for that value.) The definition of the function is encoded in the finite state machine, which will be different for each function, but there are also “universal” Turing machines which can compute any computable function by being given a finite program for calculating it on the tape when it starts.
The importance of Turing machines lies in this: every simple model of computation anyone can come up with is either less capable than the Turing machines (e.g. finite state machines with no infinite tape) or exactly equal in capability. The Turing machine model, simple as it is, exactly captures the idea of “computability”. That this is so is called the Church-Turing thesis. As it is about the intuitive idea, the thesis is not a theorem, but no-one has been able to come up with anything that is intuitively “computable”, but is not Turing-computable. In particular, all of the simple variations of a Turing machine, like giving it more tapes, or more symbols, or an n-dimensional tape, and so on, do not change what it can or cannot compute.
I was going to recommend a rather old book by Marvin Minsky, “Computation: Finite and Infinite Machines”, which I devoured in the space of a week 40 or 50 years ago, which exhaustively goes into the details of Turing machines and several equivalent models, but I see that it goes for around £50 second hand, and there does not seem to be any online copy. But the Wikipedia article is otherwise a good place to start. Especially read the historical section. The question “what can be computed by machinery?” goes back to Babbage in the 19th century.
Wow, that is extremely cool.
Somehow I never understood this idea of how such a simple (even if it’s theoretical) machine really captures the idea of computability. I’m still fuzzy on the how, but I think I have a much better understanding of the what after reading your comment. Thank you!
And my interest is piqued. I’m going to pursue an understanding of this now. I’ll probably reply to this comment at some point with further questions but it’ll take me some time to read and think first.
I’m not sure what work “simple” is doing there. There are theoretical models of hypercomputation (more power than Turing machines) , but we can’t build them, so the Turing limit appears to be a physical fact, not a mathematical one.
“Simple” is indeed doing no work and should have been omitted.
The thesis that computation beyond the Turing limit is physically impossible has also been proposed. We can imagine various sorts of hypercomputation, but as far as we know, they can’t be built. This version of the general idea that Turing-uncomputable functions cannot be computed is known as the physical Church-Turing thesis. In principle, given some particular mathematical theory of physics, one might be able to prove it as a theorem.
It has been speculated that quantum physics might reopen the question by allowing some new ways of calculating things that are not possible in classical physics. I think Scott Aaronson has written on the subject, and has proposed that if a theory of physics does allow computability beyond Turing, that in itself is evidence against the theory.
I would disagree, at least I wouldn’t give it much evidence against.
In some sense, this is me being annoyed at how much people think that the principle of normality/Egan’s law universally applies. This is a very clear failure case of the principle of normality, because conditional on hyper computers being buildable, then it doesn’t add up to normality, but to extremes.
No, quantum physics does not allow you to make computers beyond Turing machines.
This. There are scenarios where mathematically speaking, you can construct machines more powerful than Turing machines, but they rely on physics that as far as we know can’t be instantiated.