4 ms·

I have to vote the opposite direction. I don't think it's ever been relevant. As an example, A practical walk through of what a simple CPU is doing was quite u

I have to vote the opposite direction. I don't think it's ever been relevant. As an example, A practical walk through of what a simple CPU is doing was quite useful for getting the idea of what's going on. The concept of a Turing machine, which was originally intended for mathematical proofs, was not.

tialaramex 1y ago
I completely disagree. For example understanding the theory gives me a very powerful bullshit detector because entire categories of problem which might sound merely difficult are in fact Undecidable. Knowing that the actual regular expressions can be recognised by a finite automaton but PCRE and similar "LOL, just whatever neat string matching" extensions cannot means you can clearly draw the line and not accidentally make a product which promises arbitrary computation for $1 per million queries. I agree that understanding something of how the CPU works is also useful, but it's no substitute for a grounding in theory. The CPU is after all obliged to only do things which are theoretically possible, so it's not even a real difference of kind.
skydhash 1y ago
The CPU is an implementation of theory. It just happens that the realization of several axioms in the Turing machine is realizable physically. And the rest hold true. The nice thing with notation is that they're more flexible than building/creating/executing the thing they describe.
- nitwit005 1y ago
  If you look back at the history, CPUs were often designed for specific tasks, and some of the early ones lacked conditional jumps that you'd normally consider nessesary for a Turing machine. We've made them more general purpose as that sells better, not because people cared about making Turing machines.
  - skydhash 1y ago
    Jump is not required for a Turing machine, only being able to move to a specific case by sliding. Conditional jump is an abstraction. Just like looping.
    - deleted 1y ago
      [deleted]
    - nitwit005 1y ago
      I suspect you have forgotten this was a conversation about relevance in the day to day.
      - skydhash 1y ago
        TM is the basic theory. It's a more advanced finite automata that is able to modify it's own instructions. The latter can be generated from a context free grammar. Both CFG and FA have a recursive nature that allows to build more advanced mechanism from those simple elements. And that's how you get CPUs (and more specialised ones like GPUs, NPUs, etc) and programming languages. There are other computation mechanism like lambda calculus and Hoare logic. They all can be mapped to each other. So what we usually do is to invent a set of abstractions (an abstract machine) that can be mapped down to a TM-equivalent. Then denote those abstractions as primitives and then build a CFG that we can use to instruct the machine. In the case of CPUs, the abstractions are the control unit, the registers, the combinational logic, the memory,... and the CFG is the instruction set architecture. On top of that we can find the abstract machine for the C programming language. On top of the latter you can find the abstract machine for programming language like Common Lisp (SBCL) and Python. It's turtles all the way down. You just choose where you want to stop. Either at the Python level, the C level, the assembly level, the ISA level, or the theorical TM level.
        Dylan16807 1y ago
        A Turing machine isn't the only way to improve a finite automaton to make it universal. It doesn't have to be the bottom turtle.
andoando 1y ago
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.

tialaramex 1y ago

I completely disagree. For example understanding the theory gives me a very powerful bullshit detector because entire categories of problem which might sound merely difficult are in fact Undecidable. Knowing that the actual regular expressions can be recognised by a finite automaton but PCRE and similar "LOL, just whatever neat string matching" extensions cannot means you can clearly draw the line and not accidentally make a product which promises arbitrary computation for $1 per million queries. I agree that understanding something of how the CPU works is also useful, but it's no substitute for a grounding in theory. The CPU is after all obliged to only do things which are theoretically possible, so it's not even a real difference of kind.

skydhash 1y ago

The CPU is an implementation of theory. It just happens that the realization of several axioms in the Turing machine is realizable physically. And the rest hold true. The nice thing with notation is that they're more flexible than building/creating/executing the thing they describe.

nitwit005 1y ago
If you look back at the history, CPUs were often designed for specific tasks, and some of the early ones lacked conditional jumps that you'd normally consider nessesary for a Turing machine. We've made them more general purpose as that sells better, not because people cared about making Turing machines.
- skydhash 1y ago
  Jump is not required for a Turing machine, only being able to move to a specific case by sliding. Conditional jump is an abstraction. Just like looping.
  - deleted 1y ago
    [deleted]
  - nitwit005 1y ago
    I suspect you have forgotten this was a conversation about relevance in the day to day.
    - skydhash 1y ago
      TM is the basic theory. It's a more advanced finite automata that is able to modify it's own instructions. The latter can be generated from a context free grammar. Both CFG and FA have a recursive nature that allows to build more advanced mechanism from those simple elements. And that's how you get CPUs (and more specialised ones like GPUs, NPUs, etc) and programming languages. There are other computation mechanism like lambda calculus and Hoare logic. They all can be mapped to each other. So what we usually do is to invent a set of abstractions (an abstract machine) that can be mapped down to a TM-equivalent. Then denote those abstractions as primitives and then build a CFG that we can use to instruct the machine. In the case of CPUs, the abstractions are the control unit, the registers, the combinational logic, the memory,... and the CFG is the instruction set architecture. On top of that we can find the abstract machine for the C programming language. On top of the latter you can find the abstract machine for programming language like Common Lisp (SBCL) and Python. It's turtles all the way down. You just choose where you want to stop. Either at the Python level, the C level, the assembly level, the ISA level, or the theorical TM level.
      - Dylan16807 1y ago
        A Turing machine isn't the only way to improve a finite automaton to make it universal. It doesn't have to be the bottom turtle.

andoando 1y ago

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.