Wikipedia says
A model of computation is a formal description of a particular type of computational process. The description often takes the form of an abstract machine that is meant to perform the task at hand.
What other forms can a model of computation take than an abstract machine?
- What are the difference and relation between a model of computation and an abstract machine? I thought that they were the same, until I saw the the quote above.
$\begingroup$
$\endgroup$
8
-
2$\begingroup$ Abstract machines are one example of a model of computation. The lambda calculus is a model of computation but not an abstract machine. $\endgroup$– Benjamin HodgsonCommented Nov 7, 2015 at 9:31
-
$\begingroup$ Thanks. Why is lambda calculus not an abstract machine? What category (i.e. a peer of abstract machines) does it belong to then? $\endgroup$– TimCommented Nov 7, 2015 at 9:34
-
2$\begingroup$ I guess you'd call it a "calculus". Another example of such a calculus might be the pi calculus which is designed to model concurrent computation. Neither of these are abstract machines because they don't attempt to model hardware. The Turing machine or the SECD machine are examples of abstract machines. $\endgroup$– Benjamin HodgsonCommented Nov 7, 2015 at 9:38
-
2$\begingroup$ I suppose the difference is that calculi are denotational in nature - they model computation mathematically and have meaning outside of their implementation - and abstract machines are operational in nature - they model computation as a series of steps to be carried out by some imaginary hardware, and this tie their meaning to the behaviour of said hardware. $\endgroup$– Benjamin HodgsonCommented Nov 7, 2015 at 9:40
-
1$\begingroup$ Let us continue this discussion in chat. $\endgroup$– Benjamin HodgsonCommented Nov 7, 2015 at 9:45
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
An abstract machine typically defines instructions with opcodes and operands. A Warren abstract machine, a java virtual machine, a Turing machine. A programming model defines operations at a higher level, and could be independently supported by a number of different machines. For example the actor programming model says that an actor can send a message, create a new actor, and define internal state for its next message to be handled. This is said without defining specific opcodes and operands, though one could envision an abstract machine that supported that.
