Livre calculabilité

Raskolnikov · July 2021

Bonjour,
connaîtriez-vous un livre traitant des fonctions récursives et des machines de Turing dans le détail. J'ai déjà le tome 2 du Cori Lascar et j'ai beaucoup de mal à construire ne serait-ce qu'une machine de Turing qui calcule $\lambda x.x^{2}$ (un des exercices). Par ailleurs, dans les démonstrations, il est souvent demandé au lecteur d'établir par lui même la table de la machine. J'en suis incapable. Par avance merci.

M.Floquet · July 2021

Bonsoir, dans le domaine il y a les deux ouvrages de Piergiorgio Odifreddi "Classical Recursion Theory" qui expliquent tout cela et bien plus (tu) ! Sinon il y a également le livre de Hartley Rogers "Theory of Recursive Functions and Effective Computability" !

Raskolnikov · July 2021

Merci beaucoup !

Raskolnikov · July 2021

J'ai trouvé le livre de Hartley Rogers à un prix raisonnable. Quant aux deux volumes de Odifreddi, ils sont hors de prix. On peut les trouver sur le net, mais je préfère lire la version papier. Le premier volume a l'air de correspondre à mes attentes. Faut-il chercher la deuxième édition (celle de 1992, couverture souple, légèrement plus abordable) ou l'édition de 1989 fait-elle l'affaire ? Je n'ai pas envie de me retrouver avec un livre mal imprimé et peu solide (cela m'est encore arrivé récemment), et ce, pour 80 euros...
Merci pour vos conseils.

M.Floquet · July 2021

Effectivement le premier volume est suffisant pour la théorie que tu demandes. N'ayant que les versions pdf, je ne peux pas t'aider sur quelles éditions choisir... Peut-être que la plus abordable financièrement fera largement l'affaire (même s'il y a un peu moins de confort) !

Livre calculabilité

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 11