Théorème de Matiiassevitch

Ajouter des liens
Un article de Wikipédia, l'encyclopédie libre.
Ceci est une version archivée de cette page, en date du 13 décembre 2020 à 00:03 et modifiée en dernier par Ledublinois (discuter | contributions). Elle peut contenir des erreurs, des inexactitudes ou des contenus vandalisés non présents dans la version actuelle.

Cet article court présente un sujet plus développé dans : Ensemble diophantien et Dixième problème de Hilbert.

Cet article est une ébauche concernant les mathématiques et l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En mathématiques et en informatique théorique, le théorème de Matiiassevitch (orthographié également Matiyasevich[1]), dit encore théorème de Davis-Putnam-Robinson-Matiyasevich[1], démontré en 1970, établit que les ensembles diophantiens, c'est-à-dire les ensembles des solutions entières positives d'une équation diophantienne à paramètres eux-mêmes entiers positifs, sont exactement les ensembles récursivement énumérables d'entiers naturels. Il a pour conséquence immédiate l'indécidabilité du problème général de savoir si un entier naturel (ou un n-uplet d'entiers naturels) est solution ou non d'une équation diophantienne, ce qui est une solution négative au dixième problème de Hilbert.

Démonstration

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Notes et références

  1. ↑ a et b (en) Yuri Matiyasevich, « Hilbert's Tenth Problem: What Was Done and What Is to Be Done », dans Hilbert's Tenth Problem: Relations with Arithmetic and Algebraic Geometry, AMS, coll. « Contemporary Mathematics » (no 270), (ISBN 978-0-82182622-5, lire en ligne), p. 1-47 (voir p. 14).
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Théorème_de_Matiiassevitch&oldid=177567991 ».