Model de computació

En la teoria de la computabilidad i en la teoria de la complexitat computacional, un model de computació és la definició un conjunt d'operacions permitibles usades en el còmput i els seus respectius costs. Solament assumint un cert model de computació és possible analisar els recursos de còmput requerits, com el temps d'eixecució o l'espai de memòria, o discutir les llimitacions d'algoritmes o computadorés.

Alguns eixemples de models inclouen les màquines de Turing, les funcions recursivas, càlcul lambda, i sistema de producció.

En l'ingenieria dirigida per models, el model de computació explica cóm el comportament del sistema sancer és el resultat del comportament de cada u dels seus components.

En el camp del temps d'eixecució del anàlisis d'algoritmes, és comú especificar un model computacional en térmens de operacions primitives permeses que tinguen un cost unitari, o simplement operacions cost unitari. Un eixemple comunament usat és la màquina d'accés aleatori, que té cost unitari per a accés de llectura i escritura per a totes les seues celes de memòria. En este respecte, es diferencia del model de màquina de Turing mencionat dalt.

Hi ha molts models de computació, diferenciant-se en el conjunt d'operacions admissibles i del seu cost computacional. Ells entren en les àmplies categories següents:

• La màquina abstracta, usada en proves de computabilidad i dels llímits superiors en la complexitat computacional d'algoritmes, i
• El model d'arbre de decisió, usat en les proves dels llímits més baixos en la complexitat computacional de problemes algorítmics.