Haltiser le problème et le théorème automatisé prouvant?

Question

Dans la théorie du didacticiel de calcul offert par l'arbre de complexité (je viens de commencer la 2e vidéo), il parle de la manière dont le problème d'arrêt a été développé pour montrer que les mathématiques ne pouvaient pas être automatisées.Dernièrement, j'ai beaucoup entendu parler de la preuve automatisée / automatique des théorèmes - certaines personnes posent même que certains mathématiciens de jour seront remplacés par des machines.Ma question est la suivante: devons-nous trouver une faille dans le raisonnement du problème d'arrêt pour prouver que les mathématiques peuvent être automatisées?(Ou est le problème d'arrêt, à l'ère de l'apprentissage de la machine, réduit à un joli récit historique du passé ...)

Answer 1

La notion d'automatisation des mathématiques est vague, et cela comptait la divergence ici.

Une interprétation serait: pour automatiser les mathématiques serait de produire une machine $ M $ qui pourrait dire si une phrase donnée est vraie (ou plus faiblement , prouve de certains axiomes convenus d'axiomes comme $ \ mathsf {zfc} $ ). Même la version la plus faible est exclue par l'incompréabilité du problème d'arrêt.

Une autre interprétation est la suivante: automatiser la mathématique consiste à produire une machine $ M $ qui trouvera des preuves de toutes éprouvables (à nouveau, de ce type d'axiomes convenus ) Phrases. Notez que $ M $ est pas nécessaire pour déterminer si une phrase est prouvable en premier lieu, simplement pour trouver une preuve si Une telle preuve existe du tout . Ce est possible via la recherche de force brute.

Bien sûr que le second type d'automatisation est fortement infaisable - en général, Il sera ridiculement long pour trouver des preuves de théorèmes . Mais cela n'a pas d'incidence sur sa possibilité de principe. C'est vraiment le point de départ de la preuve automatisée du théorème: une recherche de manière triviale de la force brute est possible et c'est trivialement horrible en général - pouvons-nous trouver des stratégies de recherche intelligente des preuves dans certains cas de intérêt ? (Et c'est là que la théorie de la complexité entre dans la photo.)

Answer 2

Vous vous confondez deux significations possibles de la phrase "Mathematics peut être automatisé":

1. "Tout théorème peut être prouvé vrai ou faux par un algorithme"
2. "L'activité pratique des théorèmes prouvant, comme actuellement effectuée par les humains, peut plutôt être effectuée par des ordinateurs de mode économiquement viable"

En raison du trou d'arrêt, il est impossible qu'un algorithme soit capable de prouver ou de réfuter tous les théorèmes. Mais cela s'applique aussi bien aux humains que les ordinateurs!

Il n'est pas nécessaire d'être une faille dans la preuve de la non-détidabilité du problème d'arrêt (théoriquement) au travail des mathématiciens humains de devenir obsolète. Une machine ne doit pas être capable de résoudre des problèmes indéformables pour éliminer la fonction d'emploi des mathématiciens humains - il suffit de pouvoir prouver que les théorèmes d'intérêt plus efficacement que les humains ne peuvent . Ce n'est pas une question de calculabilité ni de complexité de calcul asymptotique mais d'économie.

Il n'y a aucune raison de penser que les cerveaux humains sont particulièrement supérieurs en prouvant des théorèmes mathématiques. De plus, à cause de paradoxe de Moravec , nous devrions attendre que Les ordinateurs pourraient être meilleurs pour prouver des théorèmes que les humains. Un cerveau humain est un sac de viande dont l'histoire évolutive inclut pratiquement aucune récompense de fitness pour le phénotype de "peut prouver des théorèmes difficiles". Nous nous attendions donc à ce que nous puissions voir un ordinateur surintelligent dans le domaine des théores qui prouvent plus tôt que nous ne nous attendions à voir un ordinateur surintelligent dans la région de, par exemple, la chasse Megafauna.

Answer 3

Je pense que cette question devrait vous donner le Réponse.

https:// cstheary.stackexchange.com / Questions / 2800 / IF-P-P-NP-Pouvons-nous-obtiendrons-preuves-of-Goldbachs-Conjecture-etc

En bref, si p= np puis toute conjecture avec une preuve de longueur raisonnable peut être prouvée par un ordinateur.