Portail:Informatique théorique/Calculabilité

Modèles de calcul

• Automate 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

• Thèse de Church
• Décidabilité
• Problème de l'arrêt
• Ensemble récursif
• Ensemble récursivement énumérable