Que peuvent faire les ordinateurs en principe? Quelles sont leurs limites théoriques inhérentes? Ce sont des questions auxquelles les informaticiens doivent se poser. Le cadre théorique qui permet de répondre à de telles questions a été développé au cours des cinquante dernières années à partir de l’idée d’une fonction calculable : intuitivement une fonction dont les valeurs peuvent être calculées de manière efficace ou automatique. Ce livre est une introduction à la théorie de la calculabilité (ou théorie de la récursivité comme l’appellent traditionnellement les mathématiciens). Le Dr Cutland commence par une caractérisation mathématique des fonctions calculables à l’aide d’un simple ordinateur idéalisé (un enregistreur); Après quelques comparaisons avec d’autres caractérisations, il développe la théorie mathématique, y compris une discussion complète de la non-calculabilité et de l’indécidabilité et la théorie des ensembles récursifs et récursivement énumérables. Les chapitres suivants fournissent une introduction à des sujets plus avancés tels que les degrés d'insolvabilité du théorème d'incomplétude de GÜDEL, les théorèmes de récursivité et la théorie de la complexité du calcul. La calculabilité est donc une branche des mathématiques qui est également pertinente pour les informaticiens et les philosophes. Les étudiants en mathématiques sans connaissance préalable du sujet et les étudiants en informatique qui souhaitent compléter leur expertise pratique avec un peu de connaissances théoriques trouveront ce livre d’utilisation et d’intérêt. Langue: Anglais