4 ms·

No computers have ever been programmed via Turing Machines, or built on an architecture resembling TMs(Von Neumann architecture can be described as a register m

by wz1000 9y ago

No computers have ever been programmed via Turing Machines, or built on an architecture resembling TMs(Von Neumann architecture can be described as a register machine). TMs are simply a mathematical formalisation of the notion of computation, equivalent in power to the lambda calculus. However, most programming languages(including C, Java, etc.) look much more similar to lambda calculus than a description of a Turing Machine - and for very good reason. Have you ever tried describing a TM that encodes even the simplest logic? It is a pain in the ass. Indeed, most courses on the theory of computation that discuss Turing Machines etc. don't ever expect students to fully describe a Turing Machine. Many times they use a language reminiscent of the lambda calculus to describe Turing Machines. Just take a look at the definition of Turing Machines on wikipedia and examples of TMs: https://en.wikipedia.org/wiki/Turing_machine#Formal_definition https://en.wikipedia.org/wiki/Turing_machine#Formal_definiti... https://en.wikipedia.org/wiki/Turing_machine_examples https://en.wikipedia.org/wiki/Turing_machine_examples That resembles no description of programs that are written by humans to run on computer systems, unlike the lambda calculus.

jcranmer 9y ago
Random-access, multi-tape Turing machines are actually very good descriptions of computer hardware. The description of Turing machines in practice (using unary or binary notation on a single tape) is generally done because they're simpler and no less powerful, but modern computers hew much closer to a state-transition model embodied by Turing machines than a symbol rewriting process embodied by Lambda calculus.
coldtea 9y ago
>However, most programming languages(including C, Java, etc.) look much more similar to lambda calculus than a description of a Turing Machine - and for very good reason. Have you ever tried describing a TM that encodes even the simplest logic? It is a pain in the ass. That's because we don't actually have tape, but random access memory. But a turing machine is just a limited form of imperative programming, and much closer to Assembly, or C, Fortran, BASIC, or even Java, than Lambda Calculus. >That resembles no description of programs that are written by humans to run on computer systems, unlike the lambda calculus. Actually looks like a pretty run of the mill description of working with memory locations, gotos, conditional jumps and so on. Substitute the need to run through the tape for random access memory, and you're there. The examples don't remind you of programs written by humans mostly because they're visual examples showing the whole state configuration. If we similarly mapped the memory states during various steps of the execution of a common imperative program, it would look very much like those tables.

by wz1000 9y ago

jcranmer 9y ago

Random-access, multi-tape Turing machines are actually very good descriptions of computer hardware. The description of Turing machines in practice (using unary or binary notation on a single tape) is generally done because they're simpler and no less powerful, but modern computers hew much closer to a state-transition model embodied by Turing machines than a symbol rewriting process embodied by Lambda calculus.

coldtea 9y ago

>However, most programming languages(including C, Java, etc.) look much more similar to lambda calculus than a description of a Turing Machine - and for very good reason. Have you ever tried describing a TM that encodes even the simplest logic? It is a pain in the ass. That's because we don't actually have tape, but random access memory. But a turing machine is just a limited form of imperative programming, and much closer to Assembly, or C, Fortran, BASIC, or even Java, than Lambda Calculus. >That resembles no description of programs that are written by humans to run on computer systems, unlike the lambda calculus. Actually looks like a pretty run of the mill description of working with memory locations, gotos, conditional jumps and so on. Substitute the need to run through the tape for random access memory, and you're there. The examples don't remind you of programs written by humans mostly because they're visual examples showing the whole state configuration. If we similarly mapped the memory states during various steps of the execution of a common imperative program, it would look very much like those tables.