Conjecture de Goldbach et nombres de castors occupés?

Contexte: Je suis un profane complet en informatique.

Je lisais sur les chiffres de Castor occupé ici , et j'ai trouvé le passage suivant:

L'humanité peut ne jamais connaître la valeur de BB (6) avec certitude, sans parler de celle de BB (7) ou d'un nombre supérieur dans la séquence.

En effet, déjà les cinq et six meilleurs prétendants aux règles nous échappent: nous ne pouvons pas expliquer comment ils «fonctionnent» en termes humains. Si la créativité imprègne leur conception, ce n'est pas parce que les humains la mettent là. Une façon de comprendre cela est que même les petites machines de Turing peuvent coder de profonds problèmes mathématiques. Prenons la conjecture de Goldbach, selon laquelle chaque nombre pair 4 ou plus est une somme de deux nombres premiers: 10 = 7 + 3, 18 = 13 + 5. La conjecture résiste à la preuve depuis 1742. Pourtant, nous pourrions concevoir une machine de Turing avec, oh, disons 100 règles, qui teste chaque nombre pair pour voir s'il s'agit d'une somme de deux nombres premiers, et s'arrête quand et s'il trouve un contre-exemple à la conjecture. Connaissant alors BB (100), nous pourrions en principe exécuter cette machine pour les étapes BB (100), décider si elle s'arrête et ainsi résoudre la conjecture de Goldbach.

Aaronson, Scott. "Qui peut nommer le plus grand nombre?" Qui peut nommer le plus grand nombre? Np, nd Web. 25 novembre 2016.

Il me semble que l'auteur suggère que nous pouvons prouver ou réfuter la conjecture de Goldbach, une déclaration sur une infinité de nombres, dans un nombre fini de calculs. Suis-je en train de manquer quelque chose?

L'énoncé porte sur une infinité de nombres, mais sa démonstration (ou réfutation) devrait être un exercice fini. Si possible.

La surprise peut provenir de l'hypothèse (fausse) selon laquelle trouver BB (100) serait un problème "théoriquement plus facile", rendu impossible pour des raisons pratiques - car il y a tellement de machines, et elles peuvent fonctionner aussi longtemps avant de s'arrêter , si c'est le cas - après tout, ce ne sont que des machines ...

La vérité est que la découverte de BB (n), pour n assez grand, doit être une tâche insurmontable, à la fois pour des raisons théoriques et pratiques.

L'idée de l'auteur était que vous pouvez écrire un programme en 100 lignes (n'importe quel nombre fini fixe ici) qui fait ce qui suit: prend le nombre x, teste la conjecture. Si ce n'est pas vrai, alors arrêtez de continuer sur le numéro suivant.

Connaissant le nombre de castors occupés, vous pouvez simuler cette machine pour ce nombre d'étapes, puis décider si elle s'arrête ou non. D'en haut, si elle s'arrête - la conjecture n'est pas vraie, si elle ne s'arrête pas - la conjecture est vraie.

Aaronson a récemment développé en détail cette idée / réflexion ici en travaillant avec Yedidia. [1] ils trouvent une machine à états 4888 explicite pour la conjecture de Goldbach. vous pouvez lire le document pour voir comment il a été construit. Les MT sont rarement construits mais ceux qui ont tendance à ressembler à un compilateur sont basés sur des langages de haut niveau et les compilateurs ajoutent de nombreux états. une MT "fabriquée à la main" pourrait facilement utiliser un ordre de grandeur inférieur à la quantité d'états, par exemple dans les 100 ou moins de 100. en d'autres termes, il n'y a pas vraiment eu de tentative dans cet article pour essayer de minimiser vraiment le nombre d'états . l'idée générale est bonne et les informaticiens ne sont généralement pas aussi préoccupés par les constantes exactes par rapport au travail appliqué.

cette théorie générale est décrite par les Caludes (également cités par [1]) dans deux excellents articles qui exposent certains des théorèmes du long folklore dans ce domaine et qui ont été notés par d'autres auteurs (par exemple Michel). [2] [ 3] Fondamentalement, tout problème mathématique ouvert peut être converti en problèmes indécidables. c'est parce que la plupart des problèmes mathématiques impliquent la recherche d'un nombre infini de cas pour les contre-exemples et les contre-exemples sont vérifiables algorithmiquement (mais peuvent être inefficaces ou nécessiter de grandes MT, etc.).

de plus, les «très petites» MT (comptées en nombre d'états) peuvent vérifier / être des problèmes mathématiques très complexes équivalents. Par exemple, une estimation approximative d'une MT pour résoudre la conjecture de collatz serait de quelques dizaines d'états.

il existe donc une connexion / analogie intéressante entre l'indécidabilité et l'exhaustivité de NP. NP est la classe des problèmes vérifiables efficacement, c'est-à-dire que les instances peuvent être vérifiées en temps P. les problèmes indécidables sont la classe de tous les problèmes qui permettent une vérification algorithmique des contre-exemples sans limite d'efficacité.

voici un moyen simple de comprendre la connexion avec le problème du castor occupé. tous les problèmes indécidables sont équivalents en raison de la calculabilité / équivalence de Turing. tout comme tous les problèmes NP complets peuvent être convertis les uns aux autres en temps P (réductions), tous les problèmes indécidables sont équivalents en raison de l'exhaustivité de Turing et des réductions calculables (ce qui peut prendre un temps arbitraire). par conséquent, le problème du castor occupé est en ce sens équivalent au problème de l'arrêt, et si l'on pouvait résoudre le castor occupé, alors on pourrait résoudre toutes les questions mathématiques ouvertes.

[1] Une MT relativement petite dont le comportement est indépendant de la théorie des ensembles / Yedidia, Aaronson

[2] Évaluation de la complexité des problèmes mathématiques: Partie 1 / Calude

[3] Évaluation de la complexité des problèmes mathématiques: Partie 2 / Calude

1. La conjecture de Goldbach peut être falsifiée (si elle est en fait fausse) par un tel programme de MT; il ne peut pas être prouvé correct de cette manière (un mathématicien perspicace, cependant, pourrait le faire).

2. Connaître BB (27) permettrait d'arrêter la recherche de Goldbach à un moment donné; néanmoins BB (27) (ou l'Omega de Chaitin (27)) devra auparavant savoir si le Goldbach TM s'arrête ou non.

Il est donc trompeur de dire que "BB (27) inclut la réponse à Goldbach". Bien que ce soit le cas, plus précisément: "Goldbach (et bien d'autres) sont des conditions préalables au nombre BB (27)", en d'autres termes, il n'y a pas de "fonction BB" que vous contestez à 27. Nous exécutez simplement toutes les machines à 27 états, inkl. Goldbach, et seulement après coup voir BB (27). Et, d'un POV pratique, même BB (6) semble insaisissable.

Je pense que cela semble moins mystérieux si nous répétons le point d'Aaronson en termes de preuves:

$C$$C$$C$$C$

$C$$C$$n$$BB(n)$$C = O(BB(n))$