2
$\begingroup$

Since Turing machines has great influence on typical hardware architecture (Von Neumann) and both uses concept of state, is correct to say that an imperative program is analogous to how a Turing machine works?

“Computability via Turing machines gave rise to imperative programming. Computability described via λ-calculus gave rise to functional programming.” — Cooper, S. B., Leeuwen, J. (2013) . Alan Turing: His Work and Impact.

And

"Imperative programming languages such as Fortran, Pascal etcetera as well as all the assembler languages are based on the way a Turing machine is instructed: by a sequence of statements." - Barendregt, H., Barendsen, E. (2000) . Introduction to Lambda Calculus

$\endgroup$
  • 2
    $\begingroup$ I think it's an exaggeration. Modern hardware looks nothing like Turing machines. $\endgroup$ – Yuval Filmus Nov 3 '16 at 6:33
  • 2
    $\begingroup$ The abstract machine model corresponding to imperative programming is the Random access machine. $\endgroup$ – Yuval Filmus Nov 3 '16 at 6:34
  • $\begingroup$ @YuvalFilmus Neither in the sense that both uses sequence of statements? $\endgroup$ – Alexandre Thebaldi Nov 3 '16 at 6:37
  • $\begingroup$ Turing machines gave rise to automatic programming, which is what compilers use to parse code. $\endgroup$ – Yuval Filmus Nov 3 '16 at 6:39
  • $\begingroup$ @YuvalFilmus What you think about this: "Imperative programming languages such as Fortran, Pascal etcetera as well as all the assembler languages are based on the way a Turing machine is instructed: by a sequence of statements." - Barendregt, H., Barendsen, E. (2000) . Introduction to Lambda Calculus $\endgroup$ – Alexandre Thebaldi Nov 3 '16 at 6:42
3
$\begingroup$

At a high enough level and when contrasted with functional programming, sure. Turing machine models and imperative programs have in common that they start from an input and take a series of steps that change a state stored in memory, ending with some output.

This contrasts with lambda calculus and functional programming which generally and loosely do not have the above features.

I think reading any more into the comparison than this, or trying to take it any farther, is probably a mistake. As Yuval says, Turing machines are quite different from modern machines and program execution environments.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.