1
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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, but it is less compatible with other variants like Kleene's (much more Platonic) or Post's (much more pragmatist). $\endgroup$ – Artem Kaznatcheev Nov 13 at 19:27
  • 1
    $\begingroup$ @Artem: good point. I did not want to imply that this is the primary purpose of modeling computation. $\endgroup$ – Hermann Gruber Nov 13 at 20:19
3
$\begingroup$

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, and others may suggest other general definitions.

$\endgroup$
-3
$\begingroup$

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).

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.