Calculabilité

Ce cours offre une introduction complète à la calculabilité effective en se basant sur la Thèse de Church. Il commence par examiner l'idée fondamentale que tout est un mot et explore ensuite les concepts d'encodage. La formalisation de la calculabilité est explorée à travers l'approche classique de la Machine de Turing . Les étudiants découvriront en profondeur les mécanismes des Machines de Turing, y compris les notions de langages acceptés et décidés, ainsi que les distinctions entre les langages récursifs et récursivement énumérables. Des extensions modernes des Machines de Turing sont également abordées, telles que les machines à ruban multiples et les machines à mémoire à accès direct. Enfin, le cours examine des questions importantes telles que la terminaison et conclut en récapitulant les principales idées et résultats présentés.