Understanding between lambda-calculus and other abstract machines (like Turing machine and Markov algorithm)

Question

If we look on abstract machines we could noticed analogue with modern computers (of course). What I mean? I mean this points: 1. Model of implementer (In Turing machine it is description of head, which can read/write/move, cells of memory, which are in one line and unlimited. In Markov algorithms it is description of symbol string, which also unlimited, and format of rules) 2. Program (In Turing machine it is description in special syntax (table) of states and symbols and rules how to change states and initial state) In Markov algorithms is it conversion rules.) 3. Input-Output (In Turing machine it is unlimited line of cells. In Markov algorithm it is symbol string).

So, if we try to define this three points lambda-calculus what they are could be? If "model of implementer" is the rules of reduction what "program" and "input-output" are in lambda-calculus? Is this question is correct or incorrect? If "no" what is the best way to imagine equality of this models of computation (turing machine and labmda-calculus)?

Answer 1

There are essentially two ways to describe a computational model:

1. by describing a low level arhitectural model and its command language, that is the case of Turing Machines, Random Access Machines, and at some extent, Markov algorithms
2. by providing a high level programming language for the specification of computable functions (equipped by semantic or operational rules describing how the computation is supposed to be performed). This is the case of lambda calculus, combinatory systems, primitive or general recursive languages, rewriting systems, and many others.

The historical relevance of Turing Machines is due to the fact that they have been the first model of the first class. Reasoning on specification languages, it is difficult to convince ourselves of Church's Thesis. However, if you look at a Turing Machine, it is really hard to imagine a computational agent whose basic abilities are not covered by this model of computation, namely

• reading a finite amount of information
• changing a finite internal state
• writing a finite amount of information
• moving of a finite distance in space

The other advantage of this kind of models is that it is usually easy to define a notion of cost (for time and space) for the single operations, so they turns out to be extremely handy for the foundation of complexity theory, too.

On the other side, these models suffer by all problems of low-level programming paradigms: they are extremely difficult to use in practice. So, while it is very simple to simulate a Turing Machine in lambda calculus, it is extremely painful to encode lambda calculus via Turing Machines.

Among the specification languages, lambda calculus is by far the most elegant, but probably this is not the right context to discuss this issue.