Puissance informatique humaine: Les humains peuvent-ils décider du problème qui s’arrête sur Turing Machines?

Nous savons que le problème d’arrêt (sur les machines de Turing) est indécidable pour les machines de Turing. Y a-t-il des recherches sur la capacité de l'esprit humain à gérer ce problème, éventuellement avec l' aide de Turing Machines ou d'ordinateurs à usage général?

Note : Évidemment, dans le sens le plus strict, vous pouvez toujours dire non, car il existe des machines de Turing tellement grandes qu'elles ne peuvent même pas être lues dans la vie d'un humain. Mais ceci est une restriction absurde qui ne contribue pas à la question. Donc, pour rendre les choses équitables, il faudrait assumer des êtres humains avec une durée de vie arbitraire.

Nous pourrions donc poser la question suivante: Étant donné qu'une machine de Turing T est représentée de manière appropriée, un H humain ayant une durée de vie arbitraire et une quantité arbitraire de tampon (c.-à-d. Papier + stylos), H peut-il décider si T arrête sur le mot vide?

Corollaire: Si la réponse est oui, cela ne serait-il pas également réglé si un ordinateur avait une chance de réussir le test de contrôle?

Il est très difficile de définir un esprit humain avec une rigueur mathématique telle qu'il est possible de définir une machine de Turing. Nous n'avons toujours pas de modèle fonctionnel de cerveau de souris, mais nous avons le matériel capable de le simuler. Une souris a environ 4 millions de neurones dans le cortex cérébral. Un être humain possède 80 à 120 milliards de neurones (19 à 23 milliards de néocorticaux). Ainsi, vous pouvez imaginer combien de recherches supplémentaires devront être menées afin d’obtenir un modèle fonctionnel de l’esprit humain.

Vous pourriez soutenir que nous n'avons besoin que d'une approche descendante et que nous n'avons pas besoin de comprendre le fonctionnement individuel de chaque neurone. Dans ce cas, vous pouvez étudier une logique non monotone, un raisonnement abductif, une théorie de la décision, etc. Lorsque les nouvelles théories arrivent, d'autres exceptions et paradoxes se produisent. Et il semble que nous ne soyons nulle part près d'un modèle de travail de l'esprit humain.

Après avoir pris le calcul propositionnel puis prédicat, j'ai demandé à mon professeur de logique:
"Existe-t-il une logique qui puisse définir l'ensemble du langage humain?"
Il a dit:
"Comment définiriez-vous ce qui suit?
Pour voir un monde dans un grain de sable
et un paradis dans une fleur sauvage,
maintenez l'infini dans la paume de votre main
et l'éternité en une heure.
Si vous pouvez le faire, vous devenir célèbre."

Il y a eu des débats selon lesquels un esprit humain pourrait être équivalent à une machine de Turing. Cependant, un résultat plus intéressant serait qu'un esprit humain ne soit pas l'équivalent de Turing, cela donnerait lieu à la définition d'un algorithme qui ne peut pas être calculé par une machine de Turing. Ensuite, la thèse de l'Église ne serait plus valable et il pourrait éventuellement exister un algorithme général capable de résoudre un problème critique.

Jusqu'à ce que nous en comprenions davantage, vous pourriez trouver des informations dans une branche de la philosophie. Cependant, aucune réponse à votre question n'est généralement acceptée.

http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#Minds_and_machines http://en.wikipedia.org/wiki/Mechanism_(philosophy)#G.C3.B6delian_arguments

Je pense qu'il est impossible de donner une réponse définitive à cette question, car personne ne connaît vraiment les capacités de l'esprit humain (et je doute que quiconque l'aura jamais).

Mais il existe un point de vue qui donne une solution ou une explication possible à cette question:

Lorsque nous cherchons un oracle pour résoudre le problème persistant (ou décidons de la faisabilité des formules logiques du premier ordre, etc.), nous voulons naturellement que l'oracle soit correct , il ne doit commettre aucune erreur. Mais l'esprit humain n'est pas cohérent, il fait des erreurs. Personne ne peut honnêtement dire que toutes les déclarations qu’il croit vraies sont vraiment vraies. Cette incohérence peut être considérée comme la source du pouvoir de l’esprit humain. En raison de son incohérence, il ne fait pas l’objet de limitations découlant du problème persistant, du théorème de l’inachèvement de Gödel, etc. fausses déclarations en lesquelles nous croyons). D'autre part, nous voulons que toutes les formalisations de la notion d'algorithme ou tous les calculs logiques soient cohérents, afin de pouvoir prouver une fois pour toutes qu'ils sont exempts de telles erreurs. Et cela les limite.

Juste pour que les choses soient claires: l’ hypothèse Eglise-Turing n’a rien à voir avec un dogme d’une hypothétique Eglise de Turing. Il n'y a rien de religieux à ce sujet. Au contraire, il ne s’agit que d’une hypothèse résumant le meilleur de nos connaissances. Il n'y a pas d'implication métaphysique. La question de savoir si les humains pourraient faire mieux, qu'ils pourraient réaliser plus que des machines, est une question métaphysique, car nous ne la maîtrisons absolument pas, nous n'avons aucune allusion à ce qui pourrait différencier un humain d'une machine. Donc, cette question devrait être migrée vers metaphysics.stackexchange.com.

Mais supposons que le cerveau humain puisse résoudre le problème critique de Turing Machine. Ensuite, le modèle informatique des machines de Turing devient beaucoup moins important et l'hypothèse de Church-Turing devient beaucoup moins pertinente, car nous avons un modèle plus puissant appelé modèle humain (pour éviter le mot machine ). Bien entendu, ce modèle humain (dont la durée de vie est arbitrairement longue) vient avec sa propre hypothèse sur la calculabilité.

Mais alors, bien que le problème d’arrêt pour Turing Machines ne soit plus critique, nous devons maintenant traiter le problème du modèle humain suspendu. Et la diagonalisation montrera que le problème du modèle humain Halting n’est pas décidable par un humain. Alors quoi?

Vous pouvez maintenant objecter que la diagonalisation ne serait pas applicable. Cela signifierait, je suppose, qu'associer une certaine forme de numérotation de Gödel à des dispositifs informatiques, des preuves ou tout ce que nous décrivons avec notation ne serait plus possible, bien que ce soit actuellement la base de toute science. En d’autres termes, nous devrions traiter avec des entités, des concepts qui n’ont pas de représentation écrite, qui ne peuvent pas avoir de représentation écrite, ou plus généralement des concepts sans représentation syntaxique, qu’elle soit écrite, orale ou autre.

Bien sûr, cela serait en opposition avec l' enseignement de Jean dont la toute première phrase est: " Au commencement était la Parole, et la Parole était avec Dieu, et la Parole était Dieu. " Nier l'importance fondamentale de la syntaxe, de la mot, est donc une déclaration très anti-chrétienne. Bien entendu, je ne prends pas position à ce sujet, mais comme je le sais tout d’abord, c’est une question métaphysique, et comme la question n’est pas en suspens, il semble naturel de considérer toutes les conséquences, y compris les conséquences métaphysiques.

Considérez ceci dans une perspective différente.

• La logique du premier ordre est indécidable, c'est-à-dire qu'aucune procédure de décision ne permet de déterminer si des formules arbitraires sont logiquement valides. (Mais l'ensemble des formules de premier ordre vraies est semi-décidable , c'est -à- dire que si une formule est vraie, il est possible de trouver une preuve à l'aide d'un algorithme.)
• Les assistants de preuve aident à prouver des théorèmes dans la logique du premier ordre (ou même de l'ordre supérieur). L'assistant de preuve s'assure que la preuve est faite correctement et peut même aider à résoudre certains cas. Cependant, une interaction humaine est nécessaire pour guider l'assistant de preuve vers la bonne réponse.

Des assistants de preuve pourraient être utilisés pour prouver les propriétés de machines de Turing individuelles.

Le commentaire de Carl Mummert l'a bien compris.

1. Ma compréhension (corrigez-moi si je me trompe) de la thèse de Church-Turing est l'idée que tout ce qui peut être calculé peut être calculé par une machine de Turing.

2. Et aussi, si une machine de Turing pouvait calculer si une autre machine de Turing s'arrêtait ou non sur une entrée (problème d’arrêt), vous pourriez également calculer si une autre machine de Turing ne s’arrêterait pas sur une entrée donnée (échangez simplement oui pour non, et non pour oui!) - significatif parce qu'alors vous pourriez alimenter cette machine de Turing à elle-même - ne s'arrêterait- il pas sur lui-même à l'entrée? Si oui (ne pas arrêter), alors non (est en train de s'arrêter ??). Si non, alors oui. Si oui, alors non. Si non, alors vous ... hmmm.

Donc, 2. montre qu'il est impossible pour une machine de Turing de résoudre le problème d'arrêt. Mais je ne pense pas qu'il y ait de preuves claires à contredire 1. pour le moment. Chaque modèle de calcul connu peut encore résoudre autant qu'une machine de Turing.

La charge de la preuve semble incomber à la personne qui propose un nouveau modèle de calcul qui a plus de pouvoir (c’est-à-dire peut décider plus de problèmes) que la machine de Turing classique.

À propos, on peut trouver quelques excellentes conférences sur ce sujet ici .

Rien ne prouve que le cerveau humain soit en réalité autre chose qu'une machine de Turing. En fait, il semble que tout l'univers puisse être simulé sur une machine de Turing (suffisamment grande).

Les humains sont "intelligents" en raison des algorithmes intelligents qui sont intelligemment écrits dans les neurones afin que les informaticiens ne puissent pas les voler ou les mettre en œuvre efficacement. Aussi astucieux que soient ces algorithmes, ils ne pourront probablement pas résoudre le problème d'arrêt de manière fiable .

En bref: NON

il existe des machines de Turing pour lesquelles nous ne savons pas (encore) si ces machines sont Halt ( exemple de Collatz Conjecture ).

Jusqu'à ce que nous trouvions un moyen d'énumérer toutes les machines de Turing pour lesquelles nous ne disposions pas d'une protection anti-arrêt, et jusqu'à ce que nous ne trouvions pas un moyen de prouver la suspension de ces machines, nous ne sommes pas meilleurs qu'une machine de Turing (Si Je suis correct que quelqu'un a déjà prouvé que nous ne pouvons pas tout prouver, ce qui montre que nous sommes aussi limités que Turing Machines). Oh, attendez, nous ne pouvons pas énumérer toutes ces machines car nous avons effectivement une mémoire et une durée de vie limitées.

Quelle que soit votre question, répondez vous-même:

Vous demandez si les humains sont capables de "décider", mais la décision elle-même est définie comme un algorithme. Nous utilisons donc un algorithme dans notre esprit et en arrivons à une conclusion correcte (ou à une absence de conclusion: problèmes ouverts), ou nous faisons juste une supposition.

La théorie du calcul concerne:

• Supposons qu’il existe un algorithme de boîte noire (Oracle) capable de répondre par oui ou par non à certaines questions.
• Vous pouvez ensuite l'utiliser pour répondre à des questions sans réponse en construisant un autre algorithme qui l'utilise
• En faisant cela, vous finissez par une contradiction

Cela signifie que tant que vous avez un système qui veut une réponse Noou une Yesréponse, Oracle n'est pas compatible avec ce système . Oracles peut donc exister, mais nous n'avons aucun moyen de communiquer leurs résultats , car si nous sommes en mesure de communiquer leurs résultats, alors on se retrouve avec une contradiction quelque part.

Supposons que la mécanique quantique soit composée de nombreux petits oracles. Dans ce cas, vous ne pouvez pas communiquer leurs résultats, car lorsque vous lisez le statut d'une particule, vous en changez également le statut.

J'ai eu la réponse, mais je l'ai lue ..

Enfait, nous pouvons prouver quoi que ce soit si nous partons d’une fausse hypotesis. Nous pouvons donc prouver qu’un algorithme s’arrête, mais nous pouvons aussi prouver qu’un algorithme ne s’arrête pas, cela peut être intéressant, mais il est inutile puisqu’un résultat contradictoire (vous voulez une réponse Yesou une Noréponse) n’est pas ce que vous voulez.

comme dans le cas des pays en développement qui répondent (et développent quelque peu), il existe un fort sens en ce que cette question (combinaison de l’homme et de l’ordinateur pour trouver des solutions cas par cas au problème à résoudre) est liée au domaine de l’ATP, à la démonstration automatique de théorèmes et à les épreuves assistées par ordinateur étroitement liées . On sait aussi depuis longtemps qu'il existe une forte correspondance entre les programmes et les preuves dans la correspondance de Curry-Howard . également lié / similaire à cela prouve la terminaison du programme (par exemple via des invariants de boucle ou des variantes de boucle ). en fait, il y a un sens profond dans lequel toutdes mathématiques est à propos de ce problème, car pratiquement tous les énoncés mathématiques peuvent être convertis en questions sur des programmes spécifiques sur les MT en train d’arrêter ou de ne pas s'arrêter. voir par exemple [2] pour plus d'informations et beaucoup d'autres références sur ATP, etc.

[1] est un livre semi-célèbre sur le sujet qui examine la question en détail et la relie à la possibilité d'une intelligence artificielle. En résumé, l’idée de Penrose est que la véritable intelligence artificielle doit être impossible, car les êtres humains peuvent apporter des preuves d’indécidabilité, telles que la résolution du problème par Turings ou la preuve de l’incomplétude de Godels, alors que les ordinateurs ne pourraient pas être dus aux mêmes phénomènes.

[1] Nouvel esprit des empereurs par Penrose

[2] aventures et commotions dans ATM , vzn

Les systèmes modernes de superordinateurs peuvent certainement simuler le comportement d'au moins un atome. Si des atomes individuels peuvent être simulés, il est également possible de simuler l'esprit humain en construisant un système informatique assez grand pour la simulation des atomes individuels. Cependant, je pense que cela seul ne suffirait pas. Vous auriez également besoin d'une source d'entropie afin d'obtenir de vrais nombres aléatoires pour la simulation de l'esprit humain. La meilleure source d'entropie serait probablement la désintégration radioactive ou quelque chose du genre. Qu'est-ce que ça veut dire?

Je pense que l'esprit humain est plus puissant qu'une machine de Turing, car une MT est déterministe. Vous ne pouvez pas simuler le véritable caractère aléatoire sur une machine de Turing. (Au moins, c’est l’impression que j’ai tirée de la discussion suivante

https://cstheory.stackexchange.com/questions/1263/truly-random-number-generator-turing-computable

) Cependant, je pense qu’une machine de Turing, reliée à une véritable source d’entropie, serait capable de simuler un esprit humain.

Si l’on prend également en compte le caractère aléatoire de l’environnement, qui interagit avec un esprit humain (par exemple, la nourriture, nous mangeons, la façon dont nous dormons, nous marchons, vivons fondamentalement nos vies), alors je pense certainement qu’une MT avec entropie est nécessaire. la simulation de l'esprit humain. N'oubliez pas que l'esprit humain est également constamment exposé aux rayonnements de fond, qui peuvent également interagir de manière imprévisible avec les molécules de notre cerveau. Mais je pense que même si nous considérons un environnement complètement "isolé" (Est-ce même possible? Parce que ce qui suit semble indiquer que cela pourrait ne pas être possible: http://hps.org/publicinformation/ate/faqs/faqradbods.html) - en gros, un "cerveau dans le pot" - scénario, vous obtiendrez probablement toujours des processus véritablement aléatoires, qui se produiraient parfois dans le cerveau humain. Je suis sûr qu'un biologiste pourrait régler cette partie de la question? N'oubliez pas non plus qu'un humain fait en quelque sorte partie de son environnement:

http://en.wikipedia.org/wiki/Human_Microbiome_Project

Peut-être que certaines de ces bactéries influencent également le fonctionnement interne du cerveau humain d'une manière ou d'une autre et que la composition de cette bactérie peut changer au cours de la vie humaine (même dans certaines limites, je suppose?). La question est de savoir si le comportement de ces bactéries est aléatoire dans certaines limites. Si au moins un processus dans au moins un de ces organismes est véritablement aléatoire et affecte indirectement le cerveau humain, il faut un MT avec une source d'entropie pour simuler un esprit humain.

Donc, pour répondre à la question initiale:

Un "humain" (tel que défini dans la question) peut-il résoudre le problème persistant? Oui, s’il s’agit du problème qui s’arrête pour toutes les MT déterministes et non, s’il s’agit de toutes les TM attachées à une source entropique.

Toute pensée humaine associe des problèmes uniques à une expérience personnelle. Nous pouvons nous assurer que nous avons suffisamment résolu le problème, mais nous ne savons jamais avec certitude que, dans le sens algorithmique, un ordinateur obtiendrait une solution. Soyez calme et surveillez votre propre esprit. 99,9% des messages transmis dans nos circuits neuronaux n'ont rien à voir avec une représentation logique du monde. Au lieu de cela, nous traitons avec des sentiments "instinctifs", des données sensorielles et un flot de souvenirs, d'associations et d'attitudes qui varient constamment. C'est pourquoi nous avons une méthode scientifique.