Quadrature. N° 86. p. 17-28. Initiation à la calculabilité.
English Title : Introduction to computability. (ZDM/Mathdi)
Auteur : Monniaux David
Résumé
Le problème de savoir si un système d’équations diophantiennes, c’est-Le problème de savoir si un système d’équations diophantiennes, c’est-à-dire polynomiales et à solutions entières, qui a des solutions n’a a priori rien à voir avec les bugs des logiciels informatiques. Abstract Whether or not Diophantine equations (that is, polynomials equations with integer coefficients and solutions) have solutions does not seem, a priori, to be related to bugs in computer programs. Computability theory establishes such a link: a classical result is that the problem of finding out whether a system of Diophantine equations has a solution is the same as determining whether the execution a computer program will eventually stop. This article introduces computability theory: the difficulty of defining the class of computable functions (primitive recursive functions are insufficient), Turing machines, the Church thesis, and classical results (Halting problem, Rice’s theorem, etc.). (ZDM/Mathdi)
La théorie de la calculabilité établit pourtant un lien : un résultat classique est que savoir si un système d’équations diophantiennes a une solution est un problème du même type que déterminer si un programme informatique va atteindre un certain état.
Notes
Quadrature est un magazine de mathématiques pures et appliquées. Il
s’adresse aux enseignants, étudiants, ingénieurs et amateurs de
mathématiques.
Tout internaute peut acheter le numéro en cours et les anciens numéros sur la site de la revue quadrature.info (ISSN de l’édition électronique : 1760-4826).
Données de publication
Éditeur Quadrature Revigny-sur-Ornain , 2012 Format A4, p. 17-28 Index Bibliogr. p. 27-28
ISSN 1142-2785
Public visé élève ou étudiant, enseignant, tout public Niveau licence Âge 18, 19, 20
Type article de périodique ou revue, vulgarisation, popularisation Langue français Support papier
Classification