Que signifierait-il pour réfuter la thèse de Church-Turing?

Désolé pour le titre accrocheur. Je veux comprendre, que doit-on faire pour réfuter la thèse de Church-Turing? Quelque part j'ai lu c'est mathématiquement impossible de le faire! Pourquoi?

Turing, Rosser, etc. ont utilisé différents termes pour distinguer entre "ce qui peut être calculé" et "ce qui peut être calculé par une machine de Turing".

La définition de Turing en 1939 à ce sujet est la suivante: "Nous utiliserons l'expression" fonction calculable "pour désigner une fonction calculable par une machine, et nous laisserons" effectivement calculable "faire référence à l'idée intuitive sans identification particulière avec aucune de ces définitions".

Ainsi, la thèse de Church-Turing peut être énoncée comme suit: Toute fonction effectivement calculable est une fonction calculable.

Encore une fois, à quoi ressemblera la preuve si l’on réfute cette conjecture?

La thèse de Church-Turing a été prouvée à toutes fins pratiques.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.146.5402

Dershowitz et Gurevich, Bulletin de la logique symbolique, 2008.

(Cette référence traite de l'histoire des travaux de Church et de Turing, et plaide en faveur d'une séparation entre "Thèse de l'Eglise" et "Thèse de Turing" en tant que revendications logiques distinctes, puis les prouve toutes les deux, dans le cadre d'une axiomatisation intuitive de la calculabilité.)

Il y a un point subtil que je vois rarement mentionné dans ce genre de discussions et qui mérite, à mon avis, plus d'attention.

$f$$f$

$f$$f$$f$. OK, d'accord, mais supposons maintenant que nous construisions l'hypercalculateur et lui demandions si une machine de Turing cherchant une contradiction dans ZFC s'arrêterait un jour. Supposons en outre que l'hypercalculateur réponde "Non". Que concluons-nous? Est-ce que nous en concluons que l'hypercalculateur a "calculé" la cohérence de ZFC? Comment pouvons-nous exclure la possibilité que ZFC soit réellement incohérent et que nous venons de réaliser une expérience qui a falsifié notre théorie physique?

Une caractéristique cruciale de la définition de Turing est que ses hypothèses philosophiques sont très faibles. Il suppose, comme il se doit bien sûr, certaines caractéristiques simples de notre expérience quotidienne, telles que la stabilité fondamentale du monde physique et la capacité d'effectuer des opérations finies de manière fiable, répétable et vérifiable. Tout le monde accepte ces choses (en dehors d'une classe de philosophie, c'est-à-dire!). L’acceptation d’un hypercalculateur semble cependant nous obliger à accepter une extrapolation infinied'une théorie physique, et toute notre expérience en physique nous a appris à ne pas être dogmatique sur la validité d'une théorie dans un régime bien au-delà de ce que nous pouvons vérifier expérimentalement. Pour cette raison, il me semble très improbable qu'un consensus trop vaste aboutisse à l'idée qu'un hypercalculateur spécifique est un simple calcul plutôt qu'un calcul hypercalculable , c.-à-d. hypothèses physiques sur les extrapolations infinies.

Une autre façon de le dire est que pour réfuter la thèse de Church-Turing, il faudrait non seulement construire le dispositif décrit par Andrej, mais aussi prouver à la satisfaction de tous que le dispositif fonctionne comme prévu. Bien que cela ne soit pas inconcevable, ceci est un défi de taille. Pour les ordinateurs actuels, la nature finitaire du calcul signifie que si je ne crois pas au résultat du "calcul" d'un ordinateur particulier, je peux en principe effectuer une séquence finie d'étapes d'une manière totalement différente pour vérifier le résultat. Ce type de "recours" au sens commun et à la vérification finie n'est pas disponible si nous avons des doutes sur un hypercalculateur.

Bien qu'il semble assez difficile de prouver la thèse de Church-Turing en raison de la nature informelle de "fonction effectivement calculable", nous pouvons imaginer ce que cela signifierait de la réfuter. À savoir, si quelqu'un construisait un appareil qui calculait (de manière fiable) une fonction qui ne pouvait être calculée par aucune machine de Turing, cela réfuterait la thèse de Church-Turing, car il établirait l'existence d'une fonction effectivement calculable qui ne serait pas calculable par une machine de Turing.

Le fait de réfuter la thèse de Church-Turing semble en effet extrêmement improbable et conceptuellement très difficile à imaginer. Il existe divers "mondes physiques hypothétiques" qui sont en quelque sorte en contradiction avec la thèse de Church-Turing (mais leur contradiction est en soi une question philosophique intéressante). Un article de Pitowsky " La thèse de l'Église physique et sa complexité physique", Iyun 39, 81-99 (1990) traite de tels mondes physiques hypothétiques. Voir également le document d'Itamar Pitowsky et Oron Shagrir: " La thèse de l'Église de Turing et l'hyper calcul ", Minds and Machines 13, 87-101 (2003). Oron Shagrir a écrit plusieurs articles philosophiques sur la thèse de Church-Turing, voir sa page Web . (Voir aussi cet article de blog .)

La thèse efficace ou efficiente de Church-Turing est une affirmation infiniment plus forte que l'affirmation originale de Church-Turing qui affirme que tous les calculs possibles peuvent être simulés efficacement par une machine de Turing. Les ordinateurs quantiques montreront en effet que la thèse efficace de Church-Turing est invalide (modulo certaines conjectures mathématiques de complexité de calcul, et modulo "l'interprétation asymptotique"). Je pense que la conjecture efficace entre Church et Turing a été formulée pour la première fois en 1985 par Wolfram. Le document est cité dans le document de Pitowsky dont le lien est cité ci-dessus. En fait, vous n'avez même pas besoin d'ordinateurs quantiques universels pour réfuter la thèse de la tomodensitométrie efficace, et il est intéressant de noter que les recherches (qu'Aaronson entre autres) proposent de démontrer le plus simplement possible la supériorité informatique des systèmes quantiques.

C'est également un problème intéressant s'il existe des moyens plus simples de démontrer la supériorité informatique des ordinateurs quantiques en présence de bruit, plutôt que d'avoir une tolérance de panne quantique à part entière (qui permet un calcul quantique universel). (Scott A. s’intéresse également à ce problème.)

D'après ce que j'ai compris, "l'impossibilité" de prouver ou de réfuter la thèse est qu'il n'existe pas de définition formelle de "effectivement calculable". Aujourd'hui, nous le prenons pour être précisément "calculable par une machine de Turing", mais cela pose plutôt la question.

Des modèles de calcul strictement plus puissants qu'une machine de Turing ont été étudiés. Vous trouverez quelques exemples dans http://en.wikipedia.org/wiki/Hypercomputation . Ou prenez simplement une machine de Turing avec un oracle pour résoudre le problème de l’arrêt des machines de Turing. Une telle machine aura son propre problème d’arrêt, mais elle peut résoudre le problème d’arrêt initial. Bien sûr, nous n’avons pas un tel oracle, mais l’idée n’est mathématiquement pas impossible.

Les preuves de l'hypercalculement supposent généralement la validité de la borne de Bekenstein, qui impose une limite particulière à la quantité d'informations pouvant être contenues dans une quantité finie d'espace. Il y a une controverse à ce sujet, mais je pense que la plupart des physiciens l'acceptent.

Si la liaison de Bekenstein est violée, et qu’il n’ya pas de limite à la quantité d’informations contenues dans une région donnée (disons un trou noir ou une gravure infiniment fine et robuste), et qu’il existe des mécanismes pouvant être arbitrairement raffinés pour examiner le contenu de cette région. région (par exemple, en examinant avec soin le rayonnement émis lorsqu'un objet soigneusement construit tombe dans le trou noir, ou en passant un stylet sur les rainures de la gravure), on peut supposer qu’un artefact existe déjà qui code pour un oracle à l’arrêt .

Tout cela est très peu probable, mais cela montre que l'affirmation selon laquelle l'hypercalcul est impossible n'est pas une vérité mathématique, mais repose sur la physique. Cela revient à dire qu'Andrej a raison lorsqu'il dit que nous pouvons imaginer ce que signifierait réfuter [la thèse de Church-Turing]. À savoir, si quelqu'un construisait un appareil qui calculait (de manière fiable) une fonction qui ne pouvait être calculée par aucune machine de Turing .

En ce qui concerne la thèse de Church-Turing étendue («une machine de Turing probabiliste peut simuler efficacement toute fonction physiquement calculable»):

Une possibilité est la différence entre les ordinateurs classiques et quantiques. Plus précisément, la question "Existe-t-il une tâche que les ordinateurs quantiques peuvent effectuer que les ordinateurs classiques ne peuvent pas?" Un rapport récent de Scott Aaronson aux ECCC (voir la conjecture 9 à la page 5) met en lumière une conjecture qui, si elle était prouvée, fournirait une preuve solide contre la thèse de Church-Turing étendue.

Si l’on réfutait la thèse de l’église étendue-Turing, elle pourrait ressembler à cela - en particulier, en démontrant une tâche effectivement calculable qu’une machine de Turing (classique) ne peut pas calculer efficacement.

Un nouvel article présenté à DCM2011 : Une formalisation et une preuve de la thèse élargie de l'église-Turing (Nachum Dershowitz et Evgenia Falkovich)

Les articles suivants de Selim Akl peuvent présenter un intérêt et être pertinents pour la discussion:

Akl, SG, "Trois contre-exemples pour dissiper le mythe de l'ordinateur universel", Parallel Processing Letters, Vol. 16, n ° 3, septembre 2006, p. 381 - 403.

Akl, SG, "Même les machines accélératrices ne sont pas universelles", Revue internationale de l'informatique non conventionnelle, vol. 3, n ° 2, 2007, p. 105 - 121.

Nagy, M. et Akl, SG, "Le parallélisme dans le traitement de l'information quantique met en échec l'ordinateur universel", Parallel Processing Letters, Numéro spécial sur les problèmes de calcul non conventionnels, vol. 17, n ° 3, septembre 2007, p. 233 - 262.

Voici le résumé du premier:

Il est démontré que le concept d'un ordinateur universel ne peut pas être réalisé. Plus précisément, les instances d'une fonction calculable F sont exposées et ne peuvent pas être calculées sur une machine U uniquement capable d'effectuer un nombre d'opérations fini et fixe par étape. Cela reste vrai même si la machine U est dotée d'une mémoire infinie et de la capacité de communiquer avec le monde extérieur pendant qu'elle tente de calculer F. Elle reste également vraie si, en outre, U dispose d'un délai de calcul indéfini. F. Ce résultat s’applique non seulement aux modèles de calcul idéalisés, tels que la machine de Turing, etc., mais également à tous les ordinateurs polyvalents connus, y compris les ordinateurs classiques existants (à la fois séquentiels et parallèles), ainsi qu’aux ordinateurs non conventionnels tels comme ordinateurs biologiques et quantiques.

Comment cela peut-il être vrai? Un ordinateur classique ne peut pas simuler efficacement un ordinateur quantique. Il existe des algorithmes quantiques qui fournissent une vitesse exponentielle par rapport aux ordinateurs classiques exécutant des algorithmes classiques: l'algorithme de Shor en est un.