I’m learning about Turing Machines for the first time. I think I get the gist of it, and I’m asking myself the question, “What’s the big deal?”. Here’s my attempt at an answer:
Consider the idea of Thingspace. Things are there components/properties. You could plot a point in Thingspace that describes everything about, say John Smith.
You could encode that point in thingspace. Ie. you could create a code that says, “001010111010101001...1010101010101” represents point (42343,12312,11,343223423432423,...,123123123123) in Thingspace.
A Turing Machine seems like it basically says, “If the state is 0001010101011...10101011, change it to this.” It’s looking at things at a really really low level—the level of individual bits. These bits are a map that, in theory, seem to actually represent the territory with perfect accuracy (or really, it’s capable of doing so).
So a Turing Machine could:
a) Look at a model of reality on the lowest level possible.
b) Manipulate a model of reality on the lowest level possible using a).
So back to the original question—what’s the big deal? The big deal seems to be that “When you operate on such a low level, you could ‘do anything’. The model could be perfectly accurate, and you aren’t limited to making coarse adjustments to the model.”
To what extent is my understanding accurate? Can anyone elaborate?
EDIT: It seems somewhat obvious that “if you had such precise control, you’d be able to perfectly model reality and all of that”. But to me, the hard parts seem to be:
1) Creating a physical machine that does this. That has enough memory, that computes things quickly enough, and that is wired to do things based on state. (hardware)
2) Giving the machine the right instructions. (software)
I sense that these initial impressions are ignorant of something though—I just don’t know what.
You first need to realize that Turing machine were invented before the first computer was ever built, and they were born as a mathematical model, an ideal construction. The problem at the time was that there were certain natural classifications of functions on natural numbers, the recursive functions, and the Turing machine model helped to understand that partial recursive functions = computable functions. Computable, at the time, meant that a human being was able to calculate them with the aid of pen and paper.
Nowadays, depending on the branch of computer science you want to study, either recursive functions or Turing machines are used as the default general model of ‘computability’, either to study specializations of that concepts (complexity) or to show that some class of functions cannot be computed (Turing jumps, oracles, etc.) You can think of them as idealized computer, and they are a big deal in the sense that they are the cornerstone upon which all computer science is built, the same way ‘the continuum’ is a big deal for calculus.
Turing machines are a big deal because when you change the definition of a Turing machine (by letting it use arbitrarily many symbols, or giving it multiple tapes or a multi-dimensional tape, or letting it operate nondeterministically, or making its tape finite in one direction...) it usually can still solve exactly the same set of problems, which strongly suggests that Turing completeness is a “natural concept”. A lot of computational systems are Turing-complete, and all of the discrete computational systems we’ve built are no more powerful than Turing machines. Physical reality might also be Turing-computable (Church-Turing-Deutsch principle), though we don’t know that for sure (for instance, physics might involve infinite-precision calculations on non-computable numbers).
An important property of Turing machines is that they have only one kind of instruction, which is very simple. That comes useful in various mathematical proofs, where you don’t have to enumerate many options. (Try to imagine the horror of writing a mathematical proof that something cannot be solved by a C program.)
I’m learning about Turing Machines for the first time. I think I get the gist of it, and I’m asking myself the question, “What’s the big deal?”. Here’s my attempt at an answer:
Consider the idea of Thingspace. Things are there components/properties. You could plot a point in Thingspace that describes everything about, say John Smith.
You could encode that point in thingspace. Ie. you could create a code that says, “001010111010101001...1010101010101” represents point (42343,12312,11,343223423432423,...,123123123123) in Thingspace.
A Turing Machine seems like it basically says, “If the state is 0001010101011...10101011, change it to this.” It’s looking at things at a really really low level—the level of individual bits. These bits are a map that, in theory, seem to actually represent the territory with perfect accuracy (or really, it’s capable of doing so).
So a Turing Machine could:
a) Look at a model of reality on the lowest level possible.
b) Manipulate a model of reality on the lowest level possible using a).
So back to the original question—what’s the big deal? The big deal seems to be that “When you operate on such a low level, you could ‘do anything’. The model could be perfectly accurate, and you aren’t limited to making coarse adjustments to the model.”
To what extent is my understanding accurate? Can anyone elaborate?
EDIT: It seems somewhat obvious that “if you had such precise control, you’d be able to perfectly model reality and all of that”. But to me, the hard parts seem to be:
1) Creating a physical machine that does this. That has enough memory, that computes things quickly enough, and that is wired to do things based on state. (hardware)
2) Giving the machine the right instructions. (software)
I sense that these initial impressions are ignorant of something though—I just don’t know what.
You first need to realize that Turing machine were invented before the first computer was ever built, and they were born as a mathematical model, an ideal construction.
The problem at the time was that there were certain natural classifications of functions on natural numbers, the recursive functions, and the Turing machine model helped to understand that partial recursive functions = computable functions.
Computable, at the time, meant that a human being was able to calculate them with the aid of pen and paper.
Nowadays, depending on the branch of computer science you want to study, either recursive functions or Turing machines are used as the default general model of ‘computability’, either to study specializations of that concepts (complexity) or to show that some class of functions cannot be computed (Turing jumps, oracles, etc.)
You can think of them as idealized computer, and they are a big deal in the sense that they are the cornerstone upon which all computer science is built, the same way ‘the continuum’ is a big deal for calculus.
Turing machines are a big deal because when you change the definition of a Turing machine (by letting it use arbitrarily many symbols, or giving it multiple tapes or a multi-dimensional tape, or letting it operate nondeterministically, or making its tape finite in one direction...) it usually can still solve exactly the same set of problems, which strongly suggests that Turing completeness is a “natural concept”. A lot of computational systems are Turing-complete, and all of the discrete computational systems we’ve built are no more powerful than Turing machines. Physical reality might also be Turing-computable (Church-Turing-Deutsch principle), though we don’t know that for sure (for instance, physics might involve infinite-precision calculations on non-computable numbers).
An important property of Turing machines is that they have only one kind of instruction, which is very simple. That comes useful in various mathematical proofs, where you don’t have to enumerate many options. (Try to imagine the horror of writing a mathematical proof that something cannot be solved by a C program.)