Voir la source de Preuve d'impossibilité


En [[mathématiques]], une '''preuve d'impossibilité''' est une [[Démonstration (logique et mathématiques)|preuve]] qui démontre qu'un problème particulier ne peut pas être résolu comme décrit dans l'énoncé, ou qu'un ensemble particulier de problèmes ne peut pas être résolu en général. Un tel cas est également connu sous le nom de '''preuve négative''', '''preuve d'un théorème d'impossibilité''' ou '''résultat négatif'''. Les preuves de l’impossibilité sont souvent les résolutions de décennies ou de siècles de recherche pour tenter de trouver une solution, avant finalement d'établir qu’il n’en existe pas. Prouver que quelque chose est impossible est généralement beaucoup plus difficile que la tâche inverse, car il est souvent nécessaire de développer une preuve qui fonctionne en général, plutôt que de simplement montrer un exemple particulier<ref>Pudlák, pp. 255–256.</ref>. Les [[Théorème|théorèmes]] d'impossibilité peuvent généralement être exprimés sous forme de propositions existentielles négatives ou de propositions universelles en logique.

L’[[Racine carrée de deux|irrationalité de la racine carrée de 2]] est l’une des plus anciennes preuves négatives. Elle montre qu'il est impossible d'exprimer la racine carrée de 2 comme un [[Rapport (mathématiques)|rapport]] de deux [[Entier relatif|nombres entiers]]. Une autre preuve conséquente de l'impossibilité fut la preuve de [[Ferdinand von Lindemann]] en 1882, qui montra que le problème de la [[quadrature du cercle]] ne peut pas être résolu <ref>{{Lien web |langue=en |auteur=Weisstein |prénom=Eric W. |titre=Circle Squaring |url=http://mathworld.wolfram.com/CircleSquaring.html |série=mathworld.wolfram.com |consulté le=2019-12-13}}</ref> parce que le nombre {{Formule|[[Pi|π]]}} est [[Nombre transcendant|transcendantal]] (c'est-à-dire non algébrique), et que seul un sous-ensemble des [[Nombre algébrique|nombres algébriques]] peut être construit [[Construction à la règle et au compas|à la règle et au compas]]. Deux autres problèmes classiques – la [[Trisection de l'angle|trisection d'un angle quelconque]] et la [[duplication du cube]] – se sont également révélés impossibles au {{S-|XVI}}, et tous ces problèmes ont donné lieu à des recherches sur des structures mathématiques plus complexes.

Un problème apparu au {{S-|XVI}} consistait à établir une formule générale utilisant des radicaux pour exprimer la solution de toute [[équation polynomiale]] de [[Degré d'un polynôme|degré]] ''k'' ≥ 5 fixe. Dans les années 1820, le [[Théorème d'Abel (algèbre)|théorème d'Abel-Ruffini]] (également connu sous le nom de ''théorème d'impossibilité d'Abel'' ) a montré que cela était impossible<ref>{{Lien web |langue=en |auteur=Weisstein |prénom=Eric W. |titre=Abel's Impossibility Theorem |url=http://mathworld.wolfram.com/AbelsImpossibilityTheorem.html |série=mathworld.wolfram.com |consulté le=2019-12-13}}</ref>, en utilisant des concepts tels que les [[Groupe résoluble|groupes résolubles]] de la [[théorie de Galois]], un nouveau sous-domaine de l'[[Algèbre générale|algèbre abstraite]].

Certaines des preuves négatives les plus importantes trouvées au {{S-|XX}} sont celles liées à l'[[indécidabilité]], qui montraient qu'il existe des problèmes qui ne peuvent être résolus dans le cas général par aucun [[algorithme]], l'un des plus importants étant le [[problème de l'arrêt]]. Les [[théorèmes d'incomplétude de Gödel]] sont d'autres exemples qui ont révélé les limites fondamentales de la prouvabilité des systèmes formels.

Dans la [[Théorie de la complexité (informatique théorique)|théorie de la complexité informatique]], des techniques comme la relativisation (l'ajout d'un [[Oracle (machine de Turing)|oracle]]) permettent d'obtenir des preuves d'impossibilité « faibles », dans la mesure où les techniques de preuves qui ne sont pas affectées par la relativisation ne peuvent pas résoudre le [[Problème P ≟ NP|problème P contre NP]]<ref>{{Article|auteur1=Baker|prénom1=Theodore|auteur2=Gill|prénom2=John|auteur3=Solovay|prénom3=Robert|titre=Relativizations of the P=?NP Question|périodique=SIAM Journal on Computing|volume=4|numéro=4|pages=431–442|date=1975|doi=10.1137/0204037|lire en ligne=https://epubs.siam.org/doi/10.1137/0204037|consulté le=2022-12-11|accès url=inscription}}</ref>. Une autre technique est la preuve de [[Complet (complexité)|complétude]] pour une [[classe de complexité]], qui fournit la preuve de la difficulté des problèmes en montrant qu'ils sont tout aussi difficiles à résoudre que n'importe quel autre problème de la classe. En particulier, un problème complet est [[Théorie de la complexité (informatique théorique)|insoluble]] si l’un des problèmes de sa classe l’est.

== Types de preuves ==

=== Par contradiction ===
Un autre type de preuve par contradiction est la preuve par descente, qui procède d'abord en supposant que quelque chose est possible, comme une solution [[Entier naturel|entière positive]]<ref>Plus généralement, une preuve par descente infinie est applicable sur tout [[ensemble bien ordonné]].</ref> à une classe d'équations, et que par conséquent il doit y avoir une plus petite solution (par le [[théorème de Zermelo]] ). À partir de la supposément plus petite solution, il est ensuite démontré qu'une solution plus petite peut être trouvée, contredisant la [[prémisse]] selon laquelle la première solution était la plus petite possible, montrant ainsi que la prémisse originale selon laquelle une solution existe doit être fausse.

==== Par descente ====
L'un des types de preuve négatives les plus utilisés est la [[Proposition contraposée|preuve par contraposée]]. Ce type de preuve fonctionne en partant d'une proposition, telle qu'une solution à une classe particulière d'équations, est supposée être vraie, puis par déduction, on établit que deux choses mutuellement contradictoires sont vraies simultanément, comme par exemple un nombre étant à la fois pair et impair ou à la fois négatif et positif. Puisque la contradiction découle de l’hypothèse initiale, cela signifie que la prémisse supposée est nécessairement impossible.

== Types de réfutation ==
Il existe deux méthodes alternatives pour réfuter une conjecture selon laquelle quelque chose est impossible : par [[contre-exemple]] ([[Démonstration constructive|preuve constructive]]) et par contradiction logique ([[Démonstration constructive|preuve non constructive]]).

Le moyen évident de réfuter une conjecture d’impossibilité est de fournir un seul contre-exemple. Par exemple, [[Conjecture d'Euler|Euler a proposé]] qu'au moins ''n'' puissances ''n''<sup>ièmes</sup> différentes soient nécessaires pour totaliser encore une ''n''<sup>ième</sup> puissance. La conjecture a été réfutée en 1966, avec un contre-exemple impliquant une somme de seulement quatre puissances cinquièmes différentes égalant une autre puissance cinquième :

:{{nobr|27<sup>5</sup> + 84<sup>5</sup> + 110<sup>5</sup> + 133<sup>5</sup> {{=}} 144<sup>5</sup>}}.

La preuve par contre-exemple est une forme de [[Démonstration constructive|preuve constructive]], dans la mesure où un objet réfutant l'affirmation est exposé. En revanche, une preuve non constructive d'une affirmation d'impossibilité procéderait en montrant qu'il est logiquement contradictoire que ''tous'' les contre-exemples possibles soient invalides : au moins ''un'' des éléments d'une liste de contre-exemples possibles doit effectivement être un contre-exemple valide à la conjecture d'impossibilité. Par exemple, une conjecture selon laquelle il est impossible qu'une puissance irrationnelle élevée à une puissance irrationnelle soit rationnelle a [[Nombre irrationnel|été réfutée]], en montrant que l'un des deux contre-exemples possibles doit être un contre-exemple valide, sans montrer lequel il s'agit.

== Preuve pythagoricienne de l'existence de nombres irrationnels ==
La preuve par [[Pythagore]] vers 500 [[Ère commune|BCE]] a eu un effet profond sur les mathématiques. Elle montre que la [[Racine carrée de deux|racine carrée de 2]] ne peut pas être exprimée comme le rapport de deux nombres entiers. La preuve a divisé « les nombres » en deux ensembles distincts : les [[Nombre rationnel|nombres rationnels]] et les [[Nombre irrationnel|nombres irrationnels]]. Cette bifurcation a été utilisée par [[Georg Cantor|Cantor]] dans son [[Argument de la diagonale de Cantor|argument de la diagonale]], qui à son tour a été utilisée par Turing dans sa preuve que l' ''[[Problème de la décision|Entscheidungsproblem]]'', le [[problème de décision]] de [[David Hilbert|Hilbert]], est indécidable.
{{Citation bloc|Il est inconnu quand, ou par qui, le "théorème de Pythagore" a été découvert. La découverte a difficilement pu être faire par Pythagore en personne, mais elle a certainement eu lieu dans son école. Pythagore a vécu autour de 570–490 BCE. Démocrité, né vers 470 BCE, a écrit ''Des droites et solides irrationnels'' ...|Heath}}
Des démonstrations ont suivi pour diverses racines carrées des nombres premiers jusqu'à 17.<blockquote>Il y a un passage célèbre du ''[[Théétète (Platon)|Théétète]]'' de [[Platon]] dans lequel il est dit que [[Théodore de Cyrène|Théodore]] (le professeur de Platon) a prouvé l'irrationalité de

: <math>\sqrt{3}, \sqrt{5}, ...,</math>

 en prenant tous les cas séparés jusqu'à la racine de 17 pieds carrés ...&#x2009;<ref>Hardy and Wright, p. 42</ref>.</blockquote>Il existe maintenant une preuve plus générale que :

: La ''m''-ième racine d'un entier ''N'' est irrationnelle, à moins que ''N'' ne soit la ''m-''ième puissance d'un entier ''n''<ref>Hardy and Wright, p. 40</ref>.

Autrement dit, il est impossible d’exprimer la racine ''m''-ième d’un entier ''N'' comme le rapport {{Fraction|''a''|''b''}} de deux entiers ''a'' et ''b'', qui ne partagent aucun [[Nombre premier|facteur premier]] commun sauf dans les cas où ''b'' = 1.

== Constructions impossibles recherchées par les Grecs antiques ==
Trois questions célèbres de la [[Construction à la règle et au compas|géométrie grecque]] étaient de savoir comment :

# [[Trisection de l'angle|diviser par 3 un angle donné]] uniquement [[Construction à la règle et au compas|à la règle et au compas]],
# construire un cube de volume égal au [[Duplication du cube|double du volume d'un cube donné]],
# construire un carré d'[[Quadrature du cercle|aire égale]] à celle d'un cercle donné.

Pendant plus de 2000 ans, des tentatives infructueuses ont été faites pour résoudre ces problèmes ; enfin, au {{s-|XIX}}, il a été prouvé que les constructions souhaitées sont logiquement impossibles<ref name=":2">Nagel et Newman p. 8</ref>.

Un quatrième problème des Grecs antiques était de construire un [[polygone équilatéral]] avec un nombre ''n'' de côtés spécifié, au-delà des cas basiques ''n'' = 3, 4, 5, 6 qu'ils savaient construire.

Tous ces problèmes sont liés à la [[Nombre constructible|construction euclidienne]], et les constructions euclidiennes ne peuvent être réalisées que si elles impliquent uniquement des [[Nombre constructible|nombres constructibles]] (par définition de ces derniers)<ref>Hardy and Wright p. 159</ref>. Les nombres irrationnels peuvent être euclidiens. Un bon exemple est la racine carrée de 2 (un nombre irrationnel). Il s’agit simplement de la longueur de l’[[hypoténuse]] d’un triangle rectangle dont les [[Apothème|apothèmes]] mesurent chacune une unité de longueur et peut être construit avec une règle et un compas. Mais il a été prouvé des siècles après Euclide que les nombres euclidiens ne peuvent impliquer aucune opération autre que l’addition, la soustraction, la multiplication, la division et l’extraction de racines carrées.

=== Trisection d'angle et duplication du cube ===
Les deux problèmes de la [[trisection de l'angle]] et de la [[duplication du cube]] nécessitent d'extraire des [[Racine cubique|racines cubiques]], qui ne sont pas [[Nombre constructible|constructibles]].

=== Quadrature du cercle ===
<blockquote><math>\pi</math> n'est pas un [[Nombre constructible|nombre euclidien]] ... et donc il est impossible de construire, par les méthodes euclidiennes, une longueur égale à la circonférence d'un cercle de diamètre unité <ref>Hardy and Wright p. 176</ref></blockquote>Il existe une preuve démontrant que tout nombre euclidien est un [[nombre algébrique]] – un nombre qui est la solution d’une [[équation polynomiale]]. Par conséquent, parce que <math>\pi</math> a été prouvé en 1882 comme étant un [[Nombre transcendant|nombre transcendantal]] et donc par définition pas un nombre algébrique, ce n'est pas un nombre euclidien. Ainsi, la construction d’une longueur <math>\pi</math> à partir d'un cercle unité est impossible<ref>Hardy and Wright p. 159 referenced by E. Hecke. (1923). ''Vorlesungen über die Theorie der algebraischen Zahlen''. Leipzig: [[Akademische Verlagsgesellschaft]]</ref>, et le cercle ne peut pas être quadrillé.

=== Construire un ''n'' -gone régulier ===
Le [[Polygone constructible|théorème de Gauss-Wantzel]] a montré en 1837 que la construction d'un [[Polygone régulier|''n''-gone régulier]] est impossible pour la plupart des valeurs de ''n''.

== Postulat des parallèles d'Euclide ==
{{Citation bloc|1=Richard's paradox ... is as follows. Consider all decimals that can be defined by means of a '''finite number of''' '''''words''''' <small>[“words” are symbols; boldface added for emphasis]</small>; let ''E'' be the class of such decimals. Then ''E'' has <math>\aleph_0</math> <small>[an infinite number of]</small> terms; hence its members can be ordered as the 1st, 2nd, 3rd, ... Let ''X'' be a number defined as follows <small>[Whitehead & Russell now employ the Cantor diagonal method]</small>.
<br/>If the ''n''-th figure in the ''n''-th decimal is ''p'', let the ''n''-th figure in ''X'' be ''p'' + 1 (or 0, if ''p'' = 9). Then ''X'' is different from all the members of ''E'', since, whatever finite value ''n'' may have, the ''n''-th figure in ''X'' is different from the ''n''-th figure in the ''n''-th of the decimals composing ''E'', and therefore ''X'' is different from the ''n''-th decimal. Nevertheless we have defined ''X'' in a finite number of words <small>[i.e. this very definition of “word” above.]</small> and therefore ''X'' ought to be a member of ''E''. Thus ''X'' both is and is not a member of E.}}
Le [[Axiome des parallèles|postulat des parallèles]] des ''[[Éléments (Euclide)|Éléments]]'' d'Euclide équivaut à l'affirmation selon laquelle, étant donné une droite et un point qui ne se trouve pas sur cette droite, une seule parallèle à la droite peut être tracée par ce point. Contrairement aux autres postulats, celui-ci était considéré comme moins évident. Nagel et Newman soutiennent que cela peut être dû au fait que le postulat concerne des régions de l'espace « infiniment éloignées » ; en particulier, les lignes parallèles sont définies comme ne se rencontrant même pas « à l'infini », contrairement aux [[Asymptote|asymptotes]]<ref name=":1">Nagel and Newman, p. 9</ref>. Ce manque perçu de preuves a conduit à se demander si cela pouvait être prouvé à partir des autres axiomes et postulats euclidiens. Ce n'est qu'au {{s-|XIX}} que l'impossibilité de déduire le postulat parallèle des autres a été démontrée dans les travaux de [[Carl Friedrich Gauss|Gauss]], [[János Bolyai|Bolyai]], [[Nikolaï Ivanovitch Lobatchevski|Lobatchevski]] et [[Bernhard Riemann|Riemann]]. Ces travaux ont montré que l'axiome des parallèles peut par ailleurs être remplacé par des alternatives, permettant la construction de [[Géométrie non euclidienne|géométries non euclidiennes]].

Nagel et Newman considèrent la question soulevée par le postulat parallèle comme «... peut-être le développement le plus significatif dans ses effets à long terme sur l'histoire mathématique ultérieure»<ref name=":1" />. En particulier, ils considèrent que son résultat est « de la plus haute importance intellectuelle », car il montre qu'« on peut ''prouver'' l' ''impossibilité de prouver'' certaines propositions [dans ce cas, le postulat des parallèles] au sein d'un système donné [dans ce cas, les quatre premiers postulats d'Euclide]." <ref>Nagel and Newman, p. 10</ref>

== Grand théorème de Fermat ==
Le [[dernier théorème de Fermat]] a été conjecturé par [[Pierre de Fermat]] dans les années 1600 et énonce l'impossibilité de trouver des solutions en nombres entiers positifs pour l'équation : <math>x^n+y^n=z^n</math> avec <math>n>2</math>. [[Pierre de Fermat|Fermat]] lui-même a donné une preuve pour le ''n'' = 4 cas utilisant sa technique de [[Méthode de descente infinie|descente infinie]], et d'autres cas particuliers ont été prouvés par la suite, mais le cas général n'a été prouvé qu'en 1994 par [[Andrew Wiles]].

== Paradoxe de Richard ==
Ce paradoxe profond présenté par [[Jules Richard (mathématicien)|Jules Richard]] en 1905 a inspiré les travaux de [[Kurt Gödel]] <ref>{{Ouvrage|prénom1=Ernest|nom1=Nagel|prénom2=James R.|nom2=Newman|titre=Gödel's proof|année=1958|pages totales=60 ff|isbn=0-359-07926-1|oclc=1057623639|lire en ligne=http://worldcat.org/oclc/1057623639}}</ref> et d'Alan Turing. Une définition succincte se trouve dans ''[[Principia Mathematica]]'' <ref>[http://quod.lib.umich.edu/u/umhistmath/AAT3201.0001.001/86?rgn=full+text;view=pdf ''Principia Mathematica'', 2nd edition 1927, p. 61, 64] in [http://quod.lib.umich.edu/cgi/t/text/text-idx?c=umhistmath;idno=AAT3201.0001.001 ''Principia Mathematica online'', Vol.1] at University of Michigan Historical Math Collection</ref>:

Kurt Gödel considérait sa preuve comme « une analogie » du paradoxe de Richard, qu'il appelait « ''l'antinomie de Richard'' » <ref name=":0">Gödel in ''Undecidable'', p. 9</ref> .

[[Alan Turing]] a construit ce paradoxe avec une machine et a prouvé que cette machine ne pouvait pas répondre à une question simple : cette machine sera-t-elle capable de déterminer si une machine (y compris elle-même) se retrouvera piégée dans une « [[boucle infinie]] » improductive (c'est-à-dire qu'elle ne parvient pas à continuer son activité du nombre diagonal) ?

== Incomplétude des systèmes axiomatiques : la preuve de Gödel ==
Pour citer Nagel et Newman (p. 68), "L'article de Gödel est difficile. Quarante-six définitions préliminaires, ainsi que plusieurs théorèmes préliminaires importants, doivent être maîtrisés avant d'arriver aux principaux résultats". En fait, Nagel et Newman avaient besoin d’une introduction de 67 pages pour leur exposé de la preuve. Mais si le lecteur se sent assez fort pour s'attaquer à l'article, Martin Davis observe que « cet article remarquable n'est pas seulement un jalon intellectuel mais il est écrit avec une clarté et une vigueur qui en font un plaisir à lire » (Davis dans ''Undecidable'', p. 4). Il est recommandé{{Par qui|date=August 2010}} que la plupart des lecteurs voient Nagel et Newman en premier.

Gödel a prouvé, dans ses propres mots :

: "Il est raisonnable... de faire la conjecture que... [les] axiomes [des [[Principia Mathematica]] et [[Giuseppe Peano|Peano]] ] sont... suffisants pour trancher toutes les questions mathématiques qui peuvent être formellement exprimées dans les systèmes donnés. Dans ce qui suit on montrera que ce n'est pas le cas, mais plutôt que... il existe des problèmes relativement simples de la [[théorie des nombres]] entiers ordinaires qui ne peuvent être résolus sur la base des axiomes" (Gödel dans ''Undecidable'', p. 4).

Gödel a comparé sa preuve à l'« [[Paradoxe de Richard|antinomie de Richard]] » (une « [[antinomie]] » est une contradiction ou un paradoxe) :

: « L'analogie de ce résultat avec l'antinomie de Richard est immédiatement évidente ; il existe également une relation étroite [14] avec le [[paradoxe du menteur]] (note de bas de page 14 de Gödel : toute antinomie [[Épistémologie|épistémologique]] peut être utilisée pour une preuve similaire d'indécidabilité)... Ainsi, nous avons devant nous une proposition qui affirme sa propre non-démontrabilité [15] (note de bas de page 15 : Contrairement aux apparences, une telle proposition n'est pas circulaire, car, pour commencer, elle affirme la non-démontrabilité d'une formule bien définie)"<ref name=":0" />.

== Problème d'arrêt : la première preuve de Turing ==

* L' ''[[Problème de la décision|Entscheidungsproblem]]'', le [[problème de décision]], fut résolu pour la première fois par Church en avril 1935 et précéda Turing de plus d'un an, l'article de Turing étant reçu pour publication en mai 1936<ref>Also received for publication in 1936 (in October, later than Turing) was a short paper by Emil Post that discussed the reduction of an algorithm to a simple machine-like "method" very similar to Turing's computing machine model (see [[Post–Turing machine]] for details).</ref>.
* La [[Machine de Turing|preuve de Turing]] est rendue difficile par le nombre de définitions requises et sa nature subtile.
* La première preuve de Turing (sur trois) suit le schéma du paradoxe de Richard : la machine informatique de Turing est un algorithme représenté par une chaîne de sept lettres dans une « machine informatique ». Son « calcul » consiste à tester ''toutes'' les machines informatiques (y compris elle-même) pour les « cercles » et à former un nombre diagonal à partir des calculs des machines informatiques non circulaires ou « réussies ». Il le fait, en commençant dans l'ordre à partir de 1, en convertissant les nombres (base 8) en chaînes de sept lettres à tester. Lorsqu'il arrive à son propre numéro, il crée ''sa propre'' chaîne de lettres. Il décide qu'il s'agit de la chaîne de lettres d'une machine performante, mais lorsqu'il essaie d'effectuer le calcul de cette machine ( ''le sien'' ), il se verrouille dans un cercle et ne peut pas continuer. On arrive ainsi au paradoxe de Richard.

Un certain nombre de preuves d'indécidabilité similaires sont apparues peu avant et après la preuve de Turing :

# Avril 1935 : Preuve d'[[Alonzo Church]] (« Un problème insoluble de la théorie élémentaire des nombres »). Sa preuve consistait à "... proposer une définition de la calculabilité effective... et à montrer, au moyen d'un exemple, que tous les problèmes de cette classe ne sont pas résolubles" (Indécidable p. 90))
# 1946 : [[Problème de correspondance de Post]] (cf Hopcroft et Ullman <ref name="Hopcroft.Ullman.1979">{{Ouvrage|nom1=[[John E. Hopcroft]], [[Jeffrey D. Ullman]]|titre=Introduction to Automata Theory, Languages, and Computation|éditeur=Addison-Wesley|année=1979|isbn=0-201-02988-X|lire en ligne=https://archive.org/details/introductiontoau00hopc|accès url=inscription}}</ref> p. 193 et suiv., p. 407 pour la référence)
# Avril 1947 : Preuve d'[[Emil Post]] ( ''Insolvabilité récursive d'un problème de Thue'' ) (Indécidable p. 293). Ceci est depuis devenu connu sous le nom de "Le problème des mots de Thue" ou "Le problème des mots de Thue" ([[Axel Thue]] a proposé ce problème dans un article de 1914 (cf. Références à l'article de Post dans Undecidable, p. 303)).
# [[Théorème de Rice]] : une formulation généralisée du deuxième théorème de Turing (cf Hopcroft et Ullman <ref name="Hopcroft.Ullman.1979" /> p. 185 et suivants) <ref>"...there can be no machine E which ... will determine whether M [an arbitrary machine] ever prints a given symbol (0 say)" (Undecidable p. 134). Turing makes an odd assertion at the end of this proof that sounds remarkably like Rice's Theorem:
</ref>
# Théorème de Greibach : indécidabilité en théorie du langage (cf Hopcroft et Ullman <ref name="Hopcroft.Ullman.1979" /> p. 205ff et référence à la p. 401 ibid : [[Sheila A. Greibach|Greibach]] [1963] « L'indécidabilité du problème d'ambiguïté pour les grammaires linéaires minimales », ''Information and Control'' 6 : 2, 117-125, également référence à la p. 402 ibid : Greibach [1968] « Une note sur les propriétés indécidables des langages formels », Math Systems Theory 2 :1, 1–6).
# Questions du [[pavage de Penrose]].
# Question des solutions pour les [[Équation diophantienne|équations diophantiennes]] et la réponse qui en résulte dans le théorème MRDP ; voir infra

== Compressibilité des chaînes : la preuve de Chaitin ==
Pour une exposition adaptée aux non-spécialistes, voir Beltrami p. 108 et suiv. Voir également Franzen chapitre 8 pp. 137-148, et Davis p. 263-266. La discussion de Franzén est nettement plus compliquée que celle de Beltrami et se penche sur Ω — la soi-disant « probabilité d'arrêt » de [[Gregory Chaitin]]. L'ancienne approche de Davis aborde la question du point de vue d'une [[machine de Turing]]. Chaitin a écrit un certain nombre de livres sur ses efforts et leurs retombées philosophiques et mathématiques.

Une chaîne est [[Complexité de Kolmogorov|appelée]] ''(algorithmiquement) aléatoire'' si elle ne peut être produite à partir d’un programme informatique plus court. Bien que le [[Complexité de Kolmogorov|plupart des chaînes soient aléatoires]], aucune chaîne en particulier ne peut être prouvée ainsi, à l'exception d'un nombre fini de chaînes courtes :

: "Une paraphrase du résultat de Chaitin est qu'il ne peut y avoir aucune preuve formelle qu'une chaîne suffisamment longue est aléatoire..." <ref>Beltrami p. 109</ref>

Beltrami observe que « la preuve de Chaitin est liée à un paradoxe posé par le bibliothécaire d'Oxford G. Berry au début du XXe siècle qui demandait « le plus petit entier positif qui ne puisse être défini par une phrase anglaise de moins de 1 000 caractères ». Évidemment, la définition la plus courte de ce numéro doit comporter au moins 1000 caractères. Cependant, la phrase entre guillemets, qui est elle-même une définition du numéro allégué, fait moins de 1000 caractères!"<ref>Beltrami, p. 108</ref>.

== Solutions entières des équations diophantiennes : dixième problème de Hilbert ==
La question « Une équation diophantienne arbitraire a-t-elle une solution entière ? » est indécidable. Autrement dit, il est impossible de répondre à la question dans tous les cas.

Franzén introduit le [[dixième problème de Hilbert]] et le théorème MRDP (théorème de Matiyasevich-Robinson-Davis-Putnam) qui déclare qu '«il n'existe aucun algorithme capable de décider si une équation diophantienne a ou non ''une'' solution». Le théorème MRDP utilise la preuve d'indécidabilité de Turing : "... l'ensemble des équations diophantiennes résolubles est un exemple d'un ensemble dénombrable par calcul mais non décidable, et l'ensemble des équations diophantiennes insolubles n'est pas dénombrable par calcul"<ref>Franzén p.71</ref>.

== En sciences sociales ==
En [[Science politique|sciences politiques]], le [[théorème d'impossibilité d'Arrow]] énonce qu'il est impossible de concevoir un [[Système électoral|système de vote]] satisfaisant un ensemble de cinq axiomes spécifiques. Ce théorème est prouvé en montrant que quatre des axiomes impliquent ensemble l’opposé du cinquième.

De même, le [[théorème de Gibbard-Satterthwaite]] établit qu'aucun système électoral ne peut avoir plus de deux alternatives, être robuste au [[Vote utile|vote stratégique]] et empêcher un seul électeur de décider du résultat.

En [[Économie (discipline)|économie]], le [[théorème de Holmström]] est un théorème d'impossibilité prouvant qu'aucun système d'incitation pour une équipe d'agents ne peut satisfaire les trois critères souhaitables.

En [[Science de la nature|sciences naturelles]], les affirmations d'impossibilité (comme d'autres affirmations) en viennent à être largement acceptées comme extrêmement probables plutôt que considérées comme prouvées au point d'être incontestables. La base de cette forte acceptation est une combinaison de nombreuses preuves que quelque chose ne se produit pas, combinées à une théorie sous-jacente, très efficace pour faire des prédictions, dont les hypothèses conduisent logiquement à la conclusion que quelque chose est impossible.

Deux exemples d'impossibilités largement acceptées en [[physique]] sont les [[Mouvement perpétuel|machines à mouvement perpétuel]], qui violent la loi de [[conservation de l'énergie]], et le dépassement de la [[vitesse de la lumière]], qui viole les implications de la [[relativité restreinte]]. Un autre est le [[principe d'incertitude]] de la [[mécanique quantique]], qui affirme l'impossibilité de connaître simultanément la position et l'impulsion d'une particule. Il y a aussi le [[Inégalités de Bell|théorème de Bell]] : aucune théorie physique des variables locales cachées ne pourra jamais reproduire toutes les prédictions de la mécanique quantique.

Même si une affirmation d'impossibilité en sciences naturelles ne peut jamais être absolument prouvée, elle pourrait être réfutée par l'observation d'un seul [[contre-exemple]]. Un tel contre-exemple nécessiterait que les hypothèses sous-jacentes à la théorie qui impliquait l’impossibilité soient réexaminées.

== Voir également ==

* [[Problèmes non résolus en mathématiques]]{{Spaced ndash}}Des solutions à ces problèmes sont encore recherchées. En revanche, on ''sait'' que les problèmes ci-dessus n’ont pas de solution.
* [[Paradoxes de la théorie des ensembles]]

== Notes et références ==
{{Traduction/Référence|en|Proof of impossibility|1151270199}}
{{Références}}

== Bibliographie ==
{{refbegin|30em}}
* {{ouvrage |lang=en |auteur1=[[G. H. Hardy]] |auteur2=[[E. M. Wright]] |titre=An Introduction to the Theory of Numbers |édition=5 |éditeur=Clarendon Press |lieu=Oxford England |année=1979 }}
* {{en}} [[Alfred North Whitehead]] and [[Bertrand Russell]], ''Principia Mathematica'' to *56, Cambridge at the University Press, 1962, reprint of 2nd edition 1927, first edition 1913. Chap. 2.I. "The Vicious-Circle Principle" p. 37ff, and Chap. 2.VIII. "The Contradictions" p. 60ff.
*  {{ article |lang=en | auteur1= Alan Turing | année=1936 | titre = On Computable Numbers, with an Application to the Entscheidungsproblem | périodique = Proceedings of the London Mathematical Society | série = 2 | volume = 42 | numéro= 1 | pages = 230–65 | doi= 10.1112/plms/s2-42.1.230 | s2cid= 73712 }} (et {{ article |lang=en | auteur1= Alan Turing | année=1938 | titre = On Computable Numbers, with an Application to the Entscheidungsproblem: A correction | périodique = Proceedings of the London Mathematical Society | série= 2 | volume = 43 | numéro= 6 | pages = 544–6 | doi = 10.1112/plms/s2-43.6.544 |lire en ligne=12}}).
* {{en}} [[Martin Davis (mathématicien)|Martin Davis]], ''The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions'', Raven Press, New York, 1965. Turing's paper is #3 in this volume. Papers include those by Godel, Church, Rosser, Kleene, and Post.
* {{en}} Martin Davis's chapter "What is a Computation" in Lynn Arthur Steen's ''Mathematics Today'', 1978, Vintage Books Edition, New York, 1980.
* {{ouvrage |lang=en |auteur1=[[Andrew Hodges]] |titre=Alan Turing: The Enigma |éditeur=Simon and Schuster |lieu=New York |titre chapitre=The Spirit of Truth}}.
* {{en}} [[Hans Reichenbach]], ''Elements of Symbolic Logic'', Dover Publications Inc., New York, 1947.
* {{en}} [[Ernest Nagel]] and [[James R. Newman|James Newman]], [https://archive.org/details/gdelsproof00nage ''Gödel's Proof''], New York University Press, 1958.
* {{en}} [[Edward Beltrami]], ''What is Random? Chance and Order in Mathematics and Life'', Springer-Verlag New York, Inc., 1999.
* {{en}} [[Torkel Franzén]], ''Godel's Theorem, An Incomplete Guide to Its Use and Abuse'', A.K. Peters, Wellesley Mass, 2005.
* {{en}} Pavel Pudlák, ''[https://books.google.com/books?id=obxDAAAAQBAJ&q=impossibility+proof Logical Foundations of Mathematics and Computational Complexity. A Gentle Introduction]'', Springer 2013. (See Chapter 4 "Proofs of impossibility".)
{{refend}}

{{Portail|mathématiques}}

[[Catégorie:Logique mathématique]]
[[Catégorie:Pages avec des traductions non relues]]