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?


  • 3
    $\begingroup$ 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. $\endgroup$ Commented Feb 17, 2021 at 18:37
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Feb 17, 2021 at 18:38
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Feb 17, 2021 at 18:40
  • 1
    $\begingroup$ 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 ... $\endgroup$ Commented Feb 17, 2021 at 18:45
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Feb 19, 2021 at 12:02


Your Answer

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