Portail:Informatique théorique/Calculabilité
Modèles de calcul
modifierAutomate fini • Automate sur les mots infinis • Transducteur fini • Automate à pile • Automate linéairement borné • Automate cellulaire • Machine de Turing • Lambda-calcul • Fonction récursive • Random access machine • Parallel random access machine
Problématiques
modifierThèse de Church • Décidabilité • Problème de l'arrêt • Ensemble récursif • Ensemble récursivement énumérable