Comment l'utilisation de machines Oracle Turing ne conduit-elle pas à des contradictions?

Comment pouvons-nous nous assurer que nous continuons à faire des déclarations solides et valables sur les classes de complexité lors de l'utilisation d'Oracle Turing Machines? Selon ma compréhension (sur la base des définitions données dans les manuels d'introduction sur le sujet), les machines Oracle Turing peuvent déterminer le statut d'appartenance d'une chaîne par rapport à un langage Oracle en une seule étape de calcul. Cependant, les langages oracle souvent utilisés sont impossibles à résoudre en temps constant (prenez un oracle EXPTIME complet, par exemple). Cela me semble «ouvrir la porte» aux contradictions et après tout, tout découle d'une contradiction.

Il y a plusieurs façons de voir les choses.

La première est que dans les preuves, l'implication est un peu comme une fonction, qui prend en entrée une preuve de quelque chose et produit une preuve d'autre chose.

Nous pouvons écrire des fonctions qui opèrent sur des valeurs que nous n'avons pas.

Par exemple, considérons le nombre d'arrêt , qui n'est pas calculable. Je peux écrire la fonction$h$

$haltingPlusOne : \{h \} \rightarrow \mathbb{N}$

.$haltingPlusOne(x) = x + 1$

Cette fonction prend en entrée le numéro d'arrêt et renvoie le numéro d'arrêt plus un. Il s'agit clairement d'une fonction bien définie: si nous lui donnons la bonne entrée, elle donne la bonne sortie. Le fait que nous ne puissions pas trouver la bonne entrée ne la rend pas moins valable pour une transformation.

Je vois des preuves avec des oracles comme similaires. Ce sont essentiellement des fonctions qui disent, donnez-moi une machine de Turing qui résout le problème , et je donnerai en sortie une preuve d'un théorème.$X$

Il est également important de réaliser que lorsque nous disons quelque chose comme "Il n'y a pas de machine de Turing qui peut décider du problème d'arrêt", c'est-à-dire qu'il n'y a pas de MT correspondant à la définition standard d'une MT qui décide du problème d'arrêt.

Un oracle dit essentiellement "Supposons que nous ayons une MT qui correspond à la définition normale, sauf en supposant également que nous pouvons résoudre un problème". Il n'y a donc pas de contradiction, puisque nous ne supposons pas qu'une MT normale accepte le problème, nous supposons qu'une MT spéciale accepte le problème.

Dans une analogie très informelle, pensez-y comme ça. Si je peux vous prouver qu'aucun humain sans super pouvoirs ne peut voler, il n'y a pas de contradiction en disant qu'il y a un super-héros qui peut voler.

Ces oracles sont des objets purement logiques. Nous ne savons pas comment construire des machines physiques qui les imitent, comme nous le pouvons avec les machines de Turing, mais à notre connaissance, il n'y a pas de contradiction inhérente entre leurs définitions et nos axiomes de base. En tant qu'objets logiques, ces oracles existent. Nous savons que ce ne sont pas des termes standard de Turing Machines ou Lambda-Calculus ou des fonctions récursives partielles. La thèse de Church-Turing dit qu'il n'y a pas de modèle plus puissant, mais ce n'est pas un théorème, c'est juste une conjecture, et est trop informel pour être réellement prouvé.

$A$$B$$B=B^A$

Alors à quoi bon utiliser un oracle TM alors? Je dirais que cela nous permet principalement des considérations théoriques sur le (degré de) dureté des problèmes. L'oracle peut même être indécidable. Dans ce cas, vous pouvez définir toute une hiérarchie de problèmes indécidables (degré de Turing). Bien sûr, si votre oracle est le problème d'arrêt, vous ne pouvez pas convertir votre oracle TM en une MT traditionnelle.

Le concept oracle TM est également important pour définir une forme forte de réductions (réductions de Turing).

$\sf P$$\sf NP$

$w$$|w|$