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)?

  • $\begingroup$ The best way to imagine equality of the models is that they are all Turing-Complete. $\endgroup$
    – pdexter
    Commented Jul 12, 2016 at 14:36
  • $\begingroup$ I have read proof that lamba-calculus is equal Turing machine here. And I've noticed other interpretation in which this computational models are equal. At first we should think not about Turing machine, but about universal Turing machine (machine with von Neumann architecture). So, if we are speaking about computational models we should speaking about a set of rules which modify string (with symbols). And this rules are such that we could one set of rules simulate (encode and perform) through other set of rules. $\endgroup$
    – barammba
    Commented Jul 14, 2016 at 18:14
  • $\begingroup$ This is not a research-level question. Can it be migrated to cs.stackexchange.com? $\endgroup$ Commented Feb 8, 2017 at 20:29

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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