8 ms·

I've never understood what the fascination with Turing machines is or what they actually are.

by beaker52 7y ago

goto11 7y ago
It is the simplest possible computer which can actually be built.
- mitchtbaum 7y ago
  They don't look so simple tonight.
  - TuringTest 7y ago
    That should make you think about the complexity of all other possible computers
  - fnrslvr 7y ago
    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.
  - bspammer 7y ago
    There are plenty of visualizers out there to help out e.g. http://turingmachine.io/ 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.
  - arethuza 7y ago
    If you consider the actual complexity of any computer that has actually been built then a TM is, by comparison, very simple.
- ncmncm 7y ago
  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.
Sharlin 7y ago
Well, surely the former is a consequence of the latter. Maybe it’s time to learn?
kd5bjo 7y ago
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
- beaker52 7y ago
  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.
  - caspper69 7y ago
    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.
    - The_rationalist 7y ago
      I don't quite understand how mathematics are more adapted to model the world than a programming language.
      - caspper69 7y ago
        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.
dietr1ch 7y ago
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.
devxpy 7y ago
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.
- ncmncm 7y ago
  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.
gregorygoc 7y ago
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).
- daveFNbuck 7y ago
  You don't need Turing machines for P and NP. Most reasonable models of computation are equivalent to Turing machines up to polynomial factors.
  - fnrslvr 7y ago
    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.
    - daveFNbuck 7y ago
      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.
      - fnrslvr 7y ago
        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.
TsiCClawOfLight 7y ago
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.
- User23 7y ago
  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.html https://www.cs.utexas.edu/~EWD/transcriptions/EWD04xx/EWD472...
mattkrause 7y ago
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.
mcguire 7y ago
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.
- watersb 7y ago
  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 https://news.ycombinator.com/item?id=13918465 videos: http://www.youtube.com/playlist?list=PLE18841CABEA24090 http://www.youtube.com/playlist?list=PLE18841CABEA24090
jen729w 7y ago
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/ https://www.turingtumble.com/ Totally unaffiliated. Actually saw this via the only Twitter ad I’ve ever found even remotely relevant.

I've never understood what the fascination with Turing machines is or what they actually are.

goto11 7y ago

It is the simplest possible computer which can actually be built.

mitchtbaum 7y ago
They don't look so simple tonight.
- TuringTest 7y ago
  That should make you think about the complexity of all other possible computers
- fnrslvr 7y ago
  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.
- bspammer 7y ago
  There are plenty of visualizers out there to help out e.g. http://turingmachine.io/ 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.
- arethuza 7y ago
  If you consider the actual complexity of any computer that has actually been built then a TM is, by comparison, very simple.
ncmncm 7y ago
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.

Sharlin 7y ago

Well, surely the former is a consequence of the latter. Maybe it’s time to learn?

kd5bjo 7y ago

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

beaker52 7y ago
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.
- caspper69 7y ago
  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.
  - The_rationalist 7y ago
    I don't quite understand how mathematics are more adapted to model the world than a programming language.
    - caspper69 7y ago
      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.

dietr1ch 7y ago

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.

devxpy 7y ago

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.

ncmncm 7y ago
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.

gregorygoc 7y ago

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).

daveFNbuck 7y ago
You don't need Turing machines for P and NP. Most reasonable models of computation are equivalent to Turing machines up to polynomial factors.
- fnrslvr 7y ago
  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.
  - daveFNbuck 7y ago
    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.
    - fnrslvr 7y ago
      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.

TsiCClawOfLight 7y ago

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.

User23 7y ago
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.html https://www.cs.utexas.edu/~EWD/transcriptions/EWD04xx/EWD472...

mattkrause 7y ago

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.

mcguire 7y ago

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.

watersb 7y ago
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 https://news.ycombinator.com/item?id=13918465 videos: http://www.youtube.com/playlist?list=PLE18841CABEA24090 http://www.youtube.com/playlist?list=PLE18841CABEA24090

jen729w 7y ago

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/ https://www.turingtumble.com/ Totally unaffiliated. Actually saw this via the only Twitter ad I’ve ever found even remotely relevant.