5 ms·

Turing machine works going left or right writing/reading on a tape of 1s and 0s. Your CPU works on RAM writing and reading 1s and 0s. CPU in principle isn't th

Turing machine works going left or right writing/reading on a tape of 1s and 0s. Your CPU works on RAM writing and reading 1s and 0s. CPU in principle isn't that different and is largely just using a more sophisticated instruction set. Move 5 vs right right righy right right. swap vs read, write, right, write. etc Definitely not necessary for programming but it's not some completely theoretical mumbo jumbo. Moreover what's really interesting to me is that Turing came up with the idea from following what he himself was doing as he did computation on graph paper

DonaldPShimoda 1y ago
> Definitely not necessary for programming but it's not some completely theoretical mumbo jumbo. While I'm a big fan of teaching theory, I regret to inform you that the Turing machine is kind of completely theoretical mumbo jumbo. The theoretical equivalent of the modern processor is the Von Neumann machine. Certainly there is a direct connection to be made to the Turing machine, as all computation can be framed as a program run on such a theoretical device, but there is not really much practical use in teaching students that modern computers are Turing machines. There's just too much difference, I think. The utility of the Turing machine as a pedagogical device stems more from, like, being able to formalize a decidable problem in a particular way, following a rigorous algorithmic approach to computation, thinking about abstraction, etc. I think the lambda calculus is also useful to teach for similar (though also different) pedagogical reasons, but I would never tell students that the lambda calculus "in principle isn't that different" from how their favorite language works. Practically all programming languages can be framed as lambda calculi, but some of them are sufficiently far removed from the theory for that comparison to be mostly useless to the majority of students.
- andoando 1y ago
  I'm not sure what were arguing to be honest. You definitely don't need to understand Turing machines to understand how computers work, and certainly not how to do programming. But as far as understanding computer science, computational theory, etc certainly you'd want to study Turing machines and lambda calculus. If you were say, writing a programming language, it would be nice to understand the fundamentals. I mean, I don't think Turing machines or Lambda calculus are even that far removed to call them completely theoretical. You can easily implement a few functions in lambda calculus that already resemble modern programming interfaces.
  - dooglius 1y ago
    Suppose I were to teach theoretical CS using only RAM models of computation, with no reference to Turing Machine tapes. Would there be any downside to doing this, pedagogically? (Other than, of course, the backward compatibility concern of students being able to engage with existing literature, which is the main reason this isn't done I think)
    - skydhash 1y ago
      You could do this with the C abstract machine. because it’s Turing complete. But we go with TM because they’re the most basic. Anything else is an abstraction. So you can stop at any level you like.
      - dooglius 1y ago
        In what way is a TM the most basic? If you mean in terms of simplicity I think a queue automatic is simpler to explain.
        skydhash 1y ago
        The usual theory of computation textbooks usually goes on to explain finite automata first, then context free grammar and finally the Turing machine. Why? Because the execution part of a TM is a finite automata, while the instructions can use the generative process of CFG. And then you got the whole computing world. Just from these principles (the other chapters are mostly about what's possible and what's not and exploration of other properties) The nice thing about finite automata is that they can be composed together. That leads to a recursive pattern. This leads to the creation of higher abstractions, leading to general purposes CPU and special processors (gpu, npu, cryptographic chipset, hardware encoding,...). The same things applied to CFGs lead to the creation of programming languages.
      - DonaldPShimoda 1y ago
        > You could do this with the C abstract machine. I don't think there is a "C abstract machine". I think there are some, like, minimal versions of C (there's probably a Featherweight C out there or something), but the C specification is not given in terms of an abstract machine, and any abstraction of the machinery of C will necessarily lose important implementation details (e.g., undefined or unspecified behaviors, for instance).
Dylan16807 1y ago
If the only principle you look at is "does this compute?" then they're not that different. Otherwise they're about as far apart as you can get. A Turing machine (at least one that isn't designed in some super wacky way to prove a point) has a few bits of internal state and no random access memory. If you want RAM you have to build a virtual machine on top of the Turing machine. If you try to program it directly it's going to be a byzantine nightmare. Being restricted to tape, and in particular a single tape, makes Turing machines absolutely awful for teaching programming or how a CPU implements an algorithm. Instructions, data, and status all have to fit in the same place at the same time. It's so bad that Brainfuck is an order of magnitude better, because it at least has separate instruction and data tapes. from your other comment > But as far as understanding computer science, computational theory, etc certainly you'd want to study Turing machines and lambda calculus. If you were say, writing a programming language, it would be nice to understand the fundamentals. Turing machines are not fundamental. They're just one way to achieve computation that is close to minimal. But they're not completely minimal, and I strongly doubt studying them is going to help you make a programming language. At best it'll help you figure out how to turn something that was never meant to compute into a very very bad computer.
- andoando 1y ago
  Turing machine in essence is a finite state machine + memory (the tape) + some basic instructions for reading and writing to the memory. Its a very simple, rudimentary computer, not some completely abstract mathematical object, which was what I was responding to. With universal turing machines, its not difficult to start writing composable functions, like an assembly instruction set, adders, multipliers, etc. TMs certainly arent fundemental, but when you look at TMs, lambda calculus and understand why they are equivalent, wouldnt you say you gain an understanding of what is fundamental? Certainly constructions like for loops, the stack etc are not fundamental, so youd want to go deeper in your study of languages
  - skydhash 1y ago
    One realization with TM is that programs and data are essentially the same and separation is usually imposed. When you think about your program as data, it’s hard to not notice patterns and you start to yearn for metaprogramming to more expressively express those.

DonaldPShimoda 1y ago

> Definitely not necessary for programming but it's not some completely theoretical mumbo jumbo. While I'm a big fan of teaching theory, I regret to inform you that the Turing machine is kind of completely theoretical mumbo jumbo. The theoretical equivalent of the modern processor is the Von Neumann machine. Certainly there is a direct connection to be made to the Turing machine, as all computation can be framed as a program run on such a theoretical device, but there is not really much practical use in teaching students that modern computers are Turing machines. There's just too much difference, I think. The utility of the Turing machine as a pedagogical device stems more from, like, being able to formalize a decidable problem in a particular way, following a rigorous algorithmic approach to computation, thinking about abstraction, etc. I think the lambda calculus is also useful to teach for similar (though also different) pedagogical reasons, but I would never tell students that the lambda calculus "in principle isn't that different" from how their favorite language works. Practically all programming languages can be framed as lambda calculi, but some of them are sufficiently far removed from the theory for that comparison to be mostly useless to the majority of students.

andoando 1y ago
I'm not sure what were arguing to be honest. You definitely don't need to understand Turing machines to understand how computers work, and certainly not how to do programming. But as far as understanding computer science, computational theory, etc certainly you'd want to study Turing machines and lambda calculus. If you were say, writing a programming language, it would be nice to understand the fundamentals. I mean, I don't think Turing machines or Lambda calculus are even that far removed to call them completely theoretical. You can easily implement a few functions in lambda calculus that already resemble modern programming interfaces.
- dooglius 1y ago
  Suppose I were to teach theoretical CS using only RAM models of computation, with no reference to Turing Machine tapes. Would there be any downside to doing this, pedagogically? (Other than, of course, the backward compatibility concern of students being able to engage with existing literature, which is the main reason this isn't done I think)
  - skydhash 1y ago
    You could do this with the C abstract machine. because it’s Turing complete. But we go with TM because they’re the most basic. Anything else is an abstraction. So you can stop at any level you like.
    - dooglius 1y ago
      In what way is a TM the most basic? If you mean in terms of simplicity I think a queue automatic is simpler to explain.
      - skydhash 1y ago
        The usual theory of computation textbooks usually goes on to explain finite automata first, then context free grammar and finally the Turing machine. Why? Because the execution part of a TM is a finite automata, while the instructions can use the generative process of CFG. And then you got the whole computing world. Just from these principles (the other chapters are mostly about what's possible and what's not and exploration of other properties) The nice thing about finite automata is that they can be composed together. That leads to a recursive pattern. This leads to the creation of higher abstractions, leading to general purposes CPU and special processors (gpu, npu, cryptographic chipset, hardware encoding,...). The same things applied to CFGs lead to the creation of programming languages.
    - DonaldPShimoda 1y ago
      > You could do this with the C abstract machine. I don't think there is a "C abstract machine". I think there are some, like, minimal versions of C (there's probably a Featherweight C out there or something), but the C specification is not given in terms of an abstract machine, and any abstraction of the machinery of C will necessarily lose important implementation details (e.g., undefined or unspecified behaviors, for instance).

Dylan16807 1y ago

If the only principle you look at is "does this compute?" then they're not that different. Otherwise they're about as far apart as you can get. A Turing machine (at least one that isn't designed in some super wacky way to prove a point) has a few bits of internal state and no random access memory. If you want RAM you have to build a virtual machine on top of the Turing machine. If you try to program it directly it's going to be a byzantine nightmare. Being restricted to tape, and in particular a single tape, makes Turing machines absolutely awful for teaching programming or how a CPU implements an algorithm. Instructions, data, and status all have to fit in the same place at the same time. It's so bad that Brainfuck is an order of magnitude better, because it at least has separate instruction and data tapes. from your other comment > But as far as understanding computer science, computational theory, etc certainly you'd want to study Turing machines and lambda calculus. If you were say, writing a programming language, it would be nice to understand the fundamentals. Turing machines are not fundamental. They're just one way to achieve computation that is close to minimal. But they're not completely minimal, and I strongly doubt studying them is going to help you make a programming language. At best it'll help you figure out how to turn something that was never meant to compute into a very very bad computer.

andoando 1y ago
Turing machine in essence is a finite state machine + memory (the tape) + some basic instructions for reading and writing to the memory. Its a very simple, rudimentary computer, not some completely abstract mathematical object, which was what I was responding to. With universal turing machines, its not difficult to start writing composable functions, like an assembly instruction set, adders, multipliers, etc. TMs certainly arent fundemental, but when you look at TMs, lambda calculus and understand why they are equivalent, wouldnt you say you gain an understanding of what is fundamental? Certainly constructions like for loops, the stack etc are not fundamental, so youd want to go deeper in your study of languages
- skydhash 1y ago
  One realization with TM is that programs and data are essentially the same and separation is usually imposed. When you think about your program as data, it’s hard to not notice patterns and you start to yearn for metaprogramming to more expressively express those.