Calcul

Qu’est-ce qu’un calcul ? Que peut-on calculer ?

Calculabilité et (in)décidabilité

Fonctions calculables

Décidabilité et semi-décidabilité

Indécidabilité

Problème de l’arrêt

Théorème de Rice

Réductions

Modèles de calcul

Machines de Turing

Lambda-calcul

Fonctions récursives

Machines à registres

Réécriture

Calcul distribué abstrait

Calcul probabiliste

Calcul quantique (modèles)

Automates

Automates finis

Automates à pile

Automates temporisés

Automates probabilistes

Automates cellulaires