Traditionally, the usual definition you find for model of computation is "an abstract description of how an output is computed given an input" (Wikipedia and my TCS course are my sources, but the other websites I've seen seem to agree). To me, this seems really close to the informal notion of algorithm, which is "a step by step description on how to calculate something". Furthermore, a function is called calculable if we can give an algorithm for it.

What is the relationship between this two concepts? For what I've seen, computational models such as Turing Machines or Lambda calculus are just formalisms to write algorithms within a particular syntax and semantics. For instance, a Turing machine specifies how to describe steps (n-uples) and gives a semantic of how this algorithm is interpreted. Similarly the lambda calculus specifies the syntax and the interpretation of calculus.

So, are models of computation syntactic/semantic rules for the formalization of algorithms? Why/why not? At this point, what's the difference between model of computation and programming language? Thank you for your replies.

  • 1
    $\begingroup$ It might be worthwhile to add where you have your definitions from. For instance, your "traditional" definition for a model of computation is only vaguely compatible with the one stated in Wikipedia ("a model which describes how a set of outputs are computed given a set of inputs"), which—at least in my personal experience—seems to be closer to the usual meaning; in particular, the may in "may be carried out" appears to imply nondeterminism, which is only present in a strict subset of computation models. $\endgroup$ – dkaeae Dec 11 '18 at 9:55
  • 2
    $\begingroup$ In relative terms, I'd see an algorithm as an abstract description of a method to compute the output given the input. A model of computation would then be a formal definition of an ideal device (machine/automaton/programming language/...) which is able to concretely perform an algorithm. So, yes, I'd see a model of computation as something which is used to turn algorithms (informal ideas) into a proper mathematical (executable) definition. $\endgroup$ – chi Dec 11 '18 at 10:21
  • 1
    $\begingroup$ Related: Is a Turing Machine “by definition” the most powerful machine? $\endgroup$ – David Richerby Dec 11 '18 at 12:37
  • $\begingroup$ So the Von Neuman architecture, a Turing Machine or a massive parallel architecture, are Models of Computation that can perform Algorithms? $\endgroup$ – Paul Ogilvie Dec 11 '18 at 14:39
  • 2
    $\begingroup$ chi: this is the answer, why not turn it into an answer? $\endgroup$ – reinierpost Dec 11 '18 at 15:35

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.