Modèle de calcul

En informatique théorique, un modèle de calcul est un formalisme abstrait qui modélise l'exécution d'un algorithme. Les modèles de calcul sont le fondement de l'informatique théorique. Par exemple :

• en calculabilité, ils permettent de définir la notion de fonction calculable ;
• en complexité, ils définissent le temps et la mémoire nécessaires à un calcul ;
• la théorie des automates étudie une famille de modèles de calcul, les automates, qui sont souvent plus faibles que les modèles Turing-complets de la calculabilité et de l'algorithmique.

Quelques modèles de calcul courants

• Logique combinatoire
• Automate à pile
• Automate fini
• Machine de Turing
• Machine à registres illimités
• Random access machine
• Grammaire formelle
• λ-calcul
• Fonction récursive générale, fonction récursive primitive
• Système de réécriture
• Automate cellulaire
• Réseau de Petri

Liens externes