<p>There is no essential difference, e.g. Lisp was originally defined as a computational model. Agda is a programming language, which is also a language for writing mathematical theorems (which is equivalent to a computational model).</p>
<p>The difference are the features that the language/model supports. Languages are tweaked for solving problems, math models are tweaked for proving math theorems. Generally speaking, models of computation are <em>simpler</em>, as having a lot of features would make it hard to prove what the model can and cannot do.</p>
<p>Note that this is true only if when I you say languages you mean the <em>specification</em> of the language, and not the implementation.</p>
<p>Note, also that some models mentioned here, such as the Actor model, are not formally defined, which means that this answer is not valid for them.</p>

CC BY-SA 4.0
2024-12-20T11:18:23.087Z
2024-12-20T11:18:23.087Z
Jencel
<p><a href="https://en.wikipedia.org/wiki/Model_of_computation" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Model_of_computation</a> includes sequential models, functional models and concurrency models.</p>
<ul>
<li><p>Sequential models include finite state machine, Turing machines, random access machine.</p>
</li>
<li><p>Functional models include lambda calculus.</p>
</li>
<li><p>Concurrency models include pi calculus, the actor model.</p>
</li>
</ul>
<p>I have seen lambda calculus, pi calculus, and the actor model are formulated as languages with syntax and semantics.</p>
<ol>
<li><p>Some books (such as Varela's <em>Programming Distributed Computing
Systems</em>) present models of computations and then programming
languages which &quot;follow&quot; the models.</p>
<ul>
<li><p>What is the difference between a model of computation and a programming language, if both can be formulated as languages with
syntax and semantics meaning computation? (For example, I didn't realize to make any distinction, and called lambda calculus as a programming language, but was corrected.)</p>
</li>
<li><p>What is the definition of the &quot;follow&quot; relationship between models of computation and programming languages?</p>
</li>
</ul>
</li>
<li><p>I haven't found out whether finite state machine, Turing machines,
and random access machine are formulated as languages with syntax
and semantics. I wonder if they can be and why they aren't or are
not often formulated as such?</p>
</li>
</ol>
<p>Thanks.</p>

CC BY-SA 4.0
2021-02-17T18:37:33.860Z
There is no sharp difference!  A programming language is fully formal:
there is a compiler or interpreter that executes programs on a
machine. Models of computing are specified at the level of
"normal mathematics" which is somewhat informal. For
example: models of computing often use mathematical integers and
reals. Programming languages, use finite precision integers and
floats. Other idealisations include infinite vs finite memory, and
how to generate fresh names. So one could argue that models of
computing are slightly imprecise programming languages.
Martin Berger
CC BY-SA 4.0
2021-02-17T18:38:55.900Z
This informality let's you see core ideas more clearly, rather than drowning them out in edge cases like overflow/underflow and rounding modes of floats, at least when you are not interested in details of floats.
Martin Berger
CC BY-SA 4.0
2021-02-17T18:40:34.040Z
Sometimes a model of computing becomes so popular that people do formalise it, but then it is not always clear how exactly to do this, with the actor model being a good example.
Martin Berger
CC BY-SA 4.0
2021-02-17T18:45:17.370Z
Regarding $\lambda$-calculus, it might be worthwhile to see it as a
  family of calculi, one for each reduction strategy.
  $\lambda$-calculus, as originally conceived of for the purposes of
  formalising logic, reduces under $\lambda$ which you never do when
  using $\lambda$-inspired programming languages (well, almost never,
  there is partial evaluation ...) Strictly speaking you should also be clear what notion of program equivalence you assume ...
Martin Berger
CC BY-SA 4.0
2021-02-18T18:24:36.340Z
@MartinBerger Thanks. (1)  Is it correct that an algorithm models a computation, and an algorithm and a model of (a) computation are the same concept? (2) Does it make more sense to compare a **universal** model of computation and a programming language, than to compare a model of computation and a programming language?
Tim
CC BY-SA 4.0
2021-02-19T08:33:52.100Z
(1) Programs are instances of algorithms, but we don't have a good abstract concept of algorithm, in the sense that the same algorithm can be implemented by distinct programs. For this reason algorithms and models of computation are very different. (2) As I said above: model of computation is a vague concept and usually used in a way that is similar to programming language, but less precise and focussing on a single feature.
Martin Berger
CC BY-SA 4.0
2021-02-19T10:44:54.173Z
@MartinBerger (2) Do you by any chance miss my point of distinguishing between model of computation and universal model of computation. (1)  An algorithm is defined as anything which a Turing machine can simulate. A model of computation is defined as a model of a computation. An algorithm and a model of computation are the same thing
Tim
CC BY-SA 4.0
2021-02-19T12:02:51.907Z
it's fine to have a private language and define whatever you like. But if you want meaningful feedback from *others*, you will have to communicate in a language they understand, and, whether you like it or now, for your audience here,  algorithm and a model of computation are very much *not* the same thing.
Martin Berger
CC BY-SA 4.0
2021-02-19T12:26:25.503Z
@MartinBerger I don't have a "private" language, whatever you meant by that. My post is precisely asking about what I don't understand from publications of other people
Tim
<computability><pl.programming-languages><concurrency><universal-computation>
What is the difference between a model of computation and a programming language?
Tim
# What is the difference between a model of computation and a programming language?

(Asked by: username_0 on 2021-02-17)

<https://en.wikipedia.org/wiki/Model_of_computation> includes sequential models, functional models and concurrency models.

* Sequential models include finite state machine, Turing machines, random access machine.
* Functional models include lambda calculus.
* Concurrency models include pi calculus, the actor model.

I have seen lambda calculus, pi calculus, and the actor model are formulated as languages with syntax and semantics.

1. Some books (such as Varela's *Programming Distributed Computing
   Systems*) present models of computations and then programming
   languages which "follow" the models.

   * What is the difference between a model of computation and a programming language, if both can be formulated as languages with
     syntax and semantics meaning computation? (For example, I didn't realize to make any distinction, and called lambda calculus as a programming language, but was corrected.)
   * What is the definition of the "follow" relationship between models of computation and programming languages?
2. I haven't found out whether finite state machine, Turing machines,
   and random access machine are formulated as languages with syntax
   and semantics. I wonder if they can be and why they aren't or are
   not often formulated as such?

Thanks.

**Tags:** computability, pl.programming-languages, concurrency, universal-computation

> **Comments:**
> **username_1**: There is no sharp difference!  A programming language is fully formal: there is a compiler or interpreter that executes programs on a machine. Models of computing are specified at the level of "normal mathematics" which is somewhat informal. For example: models of computing often use mathematical integers and reals. Programming languages, use finite precision integers and floats. Other idealisations include infinite vs finite memory, and how to generate fresh names. So one could argue that models of computing are slightly imprecise programming languages.  
> **username_1**: This informality let's you see core ideas more clearly, rather than drowning them out in edge cases like overflow/underflow and rounding modes of floats, at least when you are not interested in details of floats.  
> **username_1**: Sometimes a model of computing becomes so popular that people do formalise it, but then it is not always clear how exactly to do this, with the actor model being a good example.  
> **username_1**: Regarding $\lambda$-calculus, it might be worthwhile to see it as a   family of calculi, one for each reduction strategy.   $\lambda$-calculus, as originally conceived of for the purposes of   formalising logic, reduces under $\lambda$ which you never do when   using $\lambda$-inspired programming languages (well, almost never,   there is partial evaluation ...) Strictly speaking you should also be clear what notion of program equivalence you assume ...  
> **username_0**: @MartinBerger Thanks. (1)  Is it correct that an algorithm models a computation, and an algorithm and a model of (a) computation are the same concept? (2) Does it make more sense to compare a **universal** model of computation and a programming language, than to compare a model of computation and a programming language?  
> **username_1**: (1) Programs are instances of algorithms, but we don't have a good abstract concept of algorithm, in the sense that the same algorithm can be implemented by distinct programs. For this reason algorithms and models of computation are very different. (2) As I said above: model of computation is a vague concept and usually used in a way that is similar to programming language, but less precise and focussing on a single feature.  
> **username_0**: @MartinBerger (2) Do you by any chance miss my point of distinguishing between model of computation and universal model of computation. (1)  An algorithm is defined as anything which a Turing machine can simulate. A model of computation is defined as a model of a computation. An algorithm and a model of computation are the same thing  
> **username_1**: it's fine to have a private language and define whatever you like. But if you want meaningful feedback from *others*, you will have to communicate in a language they understand, and, whether you like it or now, for your audience here,  algorithm and a model of computation are very much *not* the same thing.  
> **username_0**: @MartinBerger I don't have a "private" language, whatever you meant by that. My post is precisely asking about what I don't understand from publications of other people  

---

## 1 answers

### Answer by username_2 on 2024-12-20. Score: -2

There is no essential difference, e.g. Lisp was originally defined as a computational model. Agda is a programming language, which is also a language for writing mathematical theorems (which is equivalent to a computational model).

The difference are the features that the language/model supports. Languages are tweaked for solving problems, math models are tweaked for proving math theorems. Generally speaking, models of computation are *simpler*, as having a lot of features would make it hard to prove what the model can and cannot do.

Note that this is true only if when I you say languages you mean the *specification* of the language, and not the implementation.

Note, also that some models mentioned here, such as the Actor model, are not formally defined, which means that this answer is not valid for them.


---

