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
-
2$\begingroup$ I think it's an exaggeration. Modern hardware looks nothing like Turing machines. $\endgroup$Yuval Filmus– Yuval Filmus2016年11月03日 06:33:05 +00:00Commented Nov 3, 2016 at 6:33
-
2$\begingroup$ The abstract machine model corresponding to imperative programming is the Random access machine. $\endgroup$Yuval Filmus– Yuval Filmus2016年11月03日 06:34:57 +00:00Commented Nov 3, 2016 at 6:34
-
$\begingroup$ @YuvalFilmus Neither in the sense that both uses sequence of statements? $\endgroup$Alexandre Demelas– Alexandre Demelas2016年11月03日 06:37:36 +00:00Commented Nov 3, 2016 at 6:37
-
$\begingroup$ Turing machines gave rise to automatic programming, which is what compilers use to parse code. $\endgroup$Yuval Filmus– Yuval Filmus2016年11月03日 06:39:20 +00:00Commented Nov 3, 2016 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 Demelas– Alexandre Demelas2016年11月03日 06:42:34 +00:00Commented Nov 3, 2016 at 6:42
1 Answer 1
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.
Explore related questions
See similar questions with these tags.