<p>I think that different mathematical models of computation capture different aspects of physical reality. Similar to models of solid state physics (say), these mathematical models may be largely incomparable. Think of analog computers, where the model may not even be described with discrete math. When it comes to automata and formal languages (of finite words over a finite alphabet), an early attempt of an overarching mathematical definition was the abstract family of acceptors, which encompasses Turing machines, finite automata,  stack automata,  pushdown automata and similar notions: Ginsburg, Seymour; Greibach, Sheila (1967). "Abstract Families of Languages". Conference Record of 1967 Eighth Annual Symposium on Switching and Automata Theory, 18–20 October 1967, Austin, Texas, USA. IEEE. pp. 128–139. Needless to say, that notion does not describe L-systems, nonuniform circuit families, quantum devices, probabilistic models, membrane computing etc.</p>

CC BY-SA 4.0
2019-11-13T19:27:12.107Z
I think that limiting to 'different aspects of reality' is too restrictive; it's consistent with the now popular [physicalist interpretations of the Church-Turing thesis](https://egtheory.wordpress.com/2014/09/01/falsifiability-and-gandys-variant-of-the-church-turing-thesis/), but it is less compatible with other variants like [Kleene's](https://egtheory.wordpress.com/2014/04/06/kleenes-variant-of-the-church-turing-thesis/) (much more Platonic) or [Post's](https://egtheory.wordpress.com/2014/09/11/transcendental-idealism-and-posts-variant-of-the-church-turing-thesis/) (much more pragmatist).
Artem Kaznatcheev
CC BY-SA 4.0
2019-11-13T20:19:25.217Z
@Artem: good point. I did not want to imply that this is the primary purpose of modeling computation.
Hermann Gruber
CC BY-SA 4.0
2019-11-12T19:03:00.760Z
2019-11-12T19:03:00.760Z
Hermann Gruber
<p>As others have pointed out, "model of computation" is an open-ended concept that can hardly be captured by a single defintion. A similar example in traditional mathematics is "space".</p>

<p>However, this should not prevent us from giving precise definitions of "model of computation". As our understanding and motivations change, so will the definitions. And keep in mind that various definitions capture various aspects of an idea.</p>

<p>I am going to point you to just one possibility, namely <a href="https://ncatlab.org/nlab/show/partial+combinatory+algebra" rel="nofollow noreferrer">partial combinatory algebras</a>, and others may suggest other general definitions.</p>

CC BY-SA 4.0
2019-11-12T21:03:14.883Z
2019-11-12T21:03:14.883Z
Andrej Bauer
<p><a href="https://www.staff.science.uu.nl/~ooste110/talks/NMC53.pdf" rel="nofollow noreferrer">https://www.staff.science.uu.nl/~ooste110/talks/NMC53.pdf</a></p>

<p>this reference says MoC’s are structured in a category (in fact, a 2-category).</p>

CC BY-SA 4.0
2019-11-12T14:53:41.777Z
2019-11-12T14:53:41.777Z
DeeDee
<p>Where can I find a mathematical definition for "model of computation"? <a href="https://en.m.wikipedia.org/wiki/Model_of_computation" rel="nofollow noreferrer">https://en.m.wikipedia.org/wiki/Model_of_computation</a> doesn't provide a precise definition for "model of computation"--it doesn't treat it as a maths object, it states it in English. Contrast this to clear maths definition for formal language: subset of finite set of symbols together with Kleene star</p>

CC BY-SA 4.0
2019-11-13T02:54:02.377Z
Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/100955/discussion-on-question-by-ringminustwo-what-is-a-model-of-computation-mathemati).
Bjørn Kjos-Hanssen
<fl.formal-languages><big-picture><machine-models>
what is a model of computation, mathematically?
DeeDee
# what is a model of computation, mathematically?

(Asked by: username_0 on 2019-11-11)

Where can I find a mathematical definition for "model of computation"? <https://en.m.wikipedia.org/wiki/Model_of_computation> doesn't provide a precise definition for "model of computation"--it doesn't treat it as a maths object, it states it in English. Contrast this to clear maths definition for formal language: subset of finite set of symbols together with Kleene star

**Tags:** fl.formal-languages, big-picture, machine-models
> **Comments:**
> **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/100955/discussion-on-question-by-ringminustwo-what-is-a-model-of-computation-mathemati).  

---

## 3 answers

### Answer by username_2 on 2019-11-12. Score: 5

I think that different mathematical models of computation capture different aspects of physical reality. Similar to models of solid state physics (say), these mathematical models may be largely incomparable. Think of analog computers, where the model may not even be described with discrete math. When it comes to automata and formal languages (of finite words over a finite alphabet), an early attempt of an overarching mathematical definition was the abstract family of acceptors, which encompasses Turing machines, finite automata, stack automata, pushdown automata and similar notions: Ginsburg, Seymour; Greibach, Sheila (1967). "Abstract Families of Languages". Conference Record of 1967 Eighth Annual Symposium on Switching and Automata Theory, 18–20 October 1967, Austin, Texas, USA. IEEE. pp. 128–139. Needless to say, that notion does not describe L-systems, nonuniform circuit families, quantum devices, probabilistic models, membrane computing etc.

> **Comments:**
> **username_3**: I think that limiting to 'different aspects of reality' is too restrictive; it's consistent with the now popular [physicalist interpretations of the Church-Turing thesis](https://egtheory.wordpress.com/2014/09/01/falsifiability-and-gandys-variant-of-the-church-turing-thesis/), but it is less compatible with other variants like [Kleene's](https://egtheory.wordpress.com/2014/04/06/kleenes-variant-of-the-church-turing-thesis/) (much more Platonic) or [Post's](https://egtheory.wordpress.com/2014/09/11/transcendental-idealism-and-posts-variant-of-the-church-turing-thesis/) (much more pragmatist).  
> **username_2**: @Artem: good point. I did not want to imply that this is the primary purpose of modeling computation.  

---

### Answer by username_4 on 2019-11-12. Score: 3

As others have pointed out, "model of computation" is an open-ended concept that can hardly be captured by a single defintion. A similar example in traditional mathematics is "space".

However, this should not prevent us from giving precise definitions of "model of computation". As our understanding and motivations change, so will the definitions. And keep in mind that various definitions capture various aspects of an idea.

I am going to point you to just one possibility, namely [partial combinatory algebras](https://ncatlab.org/nlab/show/partial+combinatory+algebra), and others may suggest other general definitions.


---

### Answer by username_0 on 2019-11-12. Score: -3

<https://www.staff.science.uu.nl/~ooste110/talks/NMC53.pdf>

this reference says MoC’s are structured in a category (in fact, a 2-category).


---

