2
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 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
    Commented Dec 11, 2018 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
    Commented Dec 11, 2018 at 10:21
  • 1
    $\begingroup$ Related: Is a Turing Machine “by definition” the most powerful machine? $\endgroup$
    – David Richerby
    Commented Dec 11, 2018 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
    Commented Dec 11, 2018 at 14:39
  • 2
    $\begingroup$ chi: this is the answer, why not turn it into an answer? $\endgroup$
    – reinierpost
    Commented Dec 11, 2018 at 15:35

0

Reset to default

Your Answer

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