Y a-t-il un résultat dans la théorie de la calculabilité qui ne se relativise pas?

Je lisais le document d'Andrej Bauer Premiers pas dans la théorie de la calculabilité synthétique . Dans la conclusion, il note que

Notre axiomatisation a sa limite: elle ne peut prouver aucun résultat dans la théorie de la calculabilité qui ne parvienne pas à se relativiser aux calculs oracle. En effet, la théorie peut être interprétée dans une variante des topos efficaces construits à partir de fonctions récursives partielles avec accès à un oracle.

Cela m'a amené à m'interroger sur les résultats non relativisants de la calculabilité. Tous les résultats que je connais de la théorie de la calculabilité se rapportent au calcul avec des oracles.

Y a-t-il des résultats dans la théorie de la calculabilité qui ne relativisent pas? C'est-à-dire des résultats qui valent pour la calculabilité mais ne sont pas valables pour la calculabilité par rapport à un oracle?

Par résultat, je veux dire un théorème connu dans la théorie de la calculabilité, pas une déclaration concoctée. Si la notion de relativisation n'a pas de sens pour le résultat alors ce n'est pas ce que je recherche.

Il est également intéressant de savoir si le résultat peut être énoncé dans le langage de la théorie de la calculabilité synthétique ou non.

computability relativization Anonyme
la source

Tout le monde connaît les résultats non relativisants de la théorie de la complexité comme IP = PSPACE. Je pose des questions sur les résumés de la théorie de la calculabilité non relativisants , pas sur les résultats de la théorie de la complexité .

anonyme

@Erfan: Vos commentaires ne sont pas pertinents pour la question. Ma question concerne la théorie de la calculabilité, vous parlez de la théorie de la complexité. Je recherche des résultats non relivivants, le théorème de la hiérarchie temporelle se relativise. Si vous avez une question sur le théorème de la hiérarchie temporelle et la relativisation, vous pouvez poster une question distincte.

Anonyme

Choses pertinentes: la conjecture d'homogénéité formulée par H. Rogers a été réfutée dans Richard A. Shore; La conjecture d'homogénéité (1979): il existe un degré de Turing

tel que

n'est pas isomorphe à

(la structure des degrés de Turing d'ordre partiel

). Voir une question similaire sur lo.logic

a

$\mathbf{a}$

D (\geq a)

$\mathcal{D}(\geq \mathbf{a})$

D

$\mathcal{D}$

\leq_{T}

$\leq_{T}$

Marzio De Biasi

Bonne question :-)

Andrej Bauer

@Marzio: Intéressant. " Cela signifie donc qu'il existe une phrase de premier ordre dans la langue contenant uniquement ce qui est vrai pour les degrés de Turing, mais ce qui est faux si vous relativisez la phrase aux degrés de Turing pour certains (et bien sûr , travailler dans les degrés de Turing équivaut à donner à toutes les machines de Turing l'accès à comme un oracle). Par conséquent, la preuve que est vrai ne peut pas être relativisée en . $\varphi$ $\leq_T$ $\geq_Tx$ $x$ $\geq_Tx$ $x$ $\varphi$ $x$ "Mais

n'est pas vraiment un résultat dans la calculabilité théorie, il est concocté pour un méta-théorème.

φ

$\varphi$

Anonyme

Réponses:

Théorème d'incorporation de Higman: Les groupes présentés de façon calculable finement générés sont précisément les sous-groupes générés de manière finie de groupes finis présentés. En outre, chaque groupe présenté de façon calculable (même ceux générés de façon dénombrable) est un sous-groupe d'un groupe présenté de manière finie.

Notez que cette déclaration pourrait se relativiser comme suit : "Les groupes présentés de manière calculable (avec un certain oracle ) sont précisément les sous-groupes générés de manière finie de groupes présentés de manière finie", mais ce n'est pas le cas, car on peut prouver que pour certains calculables, il y a -des groupes présentés de manière calculable qui ne sont pas présentés de façon calculable. $O$ $O$ $O$ $O$

En effet, je pense que tout résultat non relativisation de la théorie de la calculabilité doit avoir quelque chose de ce goût, comme une partie du résultat ou la preuve doit en quelque sorte « clouer » vrai calculabilité de calculabilité avec un oracle . Dans ce cas, c'est la finitude qui cloue la «calculabilité réelle». Notez que, comme Scott Aaronson l'a demandé, ce résultat est invariant à tous les modèles de calcul habituels (machine de Turing, RAM, etc.), mais ne se relativise pas (encore une fois, car tous les modèles habituels de calcul "réel" partagent certains "propriété de finitude commune"). $O$

D'un autre côté, on pourrait faire valoir que cela "ne compte pas" pour cette question, car il s'apparente davantage à une définition de la calculabilité utilisant des groupes qu'à un "résultat de la théorie de la calculabilité". D'un autre côté, c'est une définition de la calculabilité qui est robuste à modéliser mais qui ne relativise pas . (Contrairement à, disons, la caractérisation par Kleene des fonctions calculables qui se relativise facilement, en ajoutant simplement la fonction caractéristique de votre oracle au groupe de fonctions générant. Il ne semble pas y avoir d'opération analogue pour les groupes dans le contexte de l'incorporation de Higman.)

Joshua Grochow
la source

Est-ce la finitude (vs l'infini) qui distingue votre exemple, ou la dénombrabilité (vs uncountability)?

András Salamon

Excusez mon ignorance, mais le théorème de Higman est-il uniforme? C'est-à-dire, étant donné un groupe présenté de façon calculable, pouvons-nous calculer uniformément un groupe généré de manière finie qui le contient?

Andrej Bauer

Oups, veuillez remplacer "généré de manière définitive" par "présenté de manière définitive" dans ma question. C'était une erreur banale. Ce que je me demande, c'est si nous pouvons remplacer «finement présenté» par quelque chose d'un peu plus général.

Andrej Bauer

@AndrewMorgan: Je suis d'accord avec le début de votre argument mais en désaccord avec votre conclusion. Il est souvent très utile que

est

-complete. Je ne pense pas que la relativisation de Cook-Levin ne soit pas du tout naturelle ... J'aime beaucoup la suggestion d'Andrej et nous y réfléchirons ...

S A T^{O}

$SAT^O$

N P^{O}

$NP^O$

Joshua Grochow

@AndrewMorgan: D'accord. Je pense que le genre de nœud serait un bon candidat :).

Joshua Grochow

C'est aussi quelque chose que je me suis souvent demandé!

Si par «résultats dans la théorie de la calculabilité», vous voulez dire des résultats invariants par rapport au choix du modèle de machine (machines de Turing, machines RAM, etc.), alors je ne connais pas un seul exemple d'un tel résultat, et je se serait certainement souvenu si j'en avais vu un.

Le plus proche que je puisse suggérer à une réponse est: je pense qu'il existe de nombreuses questions intéressantes dans la théorie de la calculabilité qui pourraient dépendre du modèle de la machine. Par exemple: la fonction Busy Beaver, avec sa définition habituelle en termes de machines de Turing, est-elle infiniment souvent étrange? La valeur de BB (20) est-elle indépendante de ZFC? Quelles que soient les réponses à ces questions, elles pourraient sûrement être différentes pour les analogues relativisés de la fonction BB.

Scott Aaronson
la source

Voici un exemple plus ou moins trivial: Considérons le problème d'arrêt pour les machines Turing qui sont spécifiquement interdites (par la définition du modèle de calcul) d'accéder à un oracle. Il est indécidable par rapport à aucun oracle et à un oracle trivial, et pourtant il est décidable par rapport à un oracle pour le problème d'arrêt. (Le problème lui-même ne change pas par rapport à un oracle car il ne peut pas accéder à l'oracle, mais la MT (sans restriction) qui décide du problème devient plus puissante compte tenu de l'oracle.)

Il existe également de nombreux autres exemples. Jouez un peu avec le modèle de calcul et vous pouvez trouver d'autres résultats similaires.

Philip White
la source

Juste curieux: qu'est-ce qui ne va pas exactement avec cette réponse? Peut-être que les downvoters ne croient pas qu'il soit possible d'interdire à une machine de Turing d'accéder à un oracle et ont besoin d'explications supplémentaires à ce sujet?

Philip White

Cela ne semble pas être une définition très juste de la relativisation pour permettre à la machine d'avoir un oracle mais ne pas lui permettre d'utiliser l'oracle.

David Eppstein

Intéressant mais pas ce que je recherche. Je cherche un résultat connu dans la théorie de la calculabilité qui ne relativise pas, pas un argument pour préparer un tel résultat.

Anonyme

Considérez la déclaration suivante: H (problème d'arrêt pour les machines Turing sans oracles) n'est pas calculable. D'autre part, H est calculable par rapport à un problème d'arrêt d'Oracle. Même si nous considérons cela comme un moyen de relativiser l'énoncé, ce n'est pas intéressant. Il existe probablement une manière similaire de relativiser toute déclaration qui la rend fausse. Une relativisation ne consiste pas simplement à attacher un oracle quelque part. Une relativisation est intéressante lorsqu'elle préserve une classe intéressante d'arguments, donc si une déclaration ne relativise pas, nous savons que cette classe d'arguments ne peut pas prouver la déclaration.

Kaveh

Prenons par exemple la méthode de relativisation dans BGS. Il est intéressant car il conserve des arguments de diagonalisation simples afin qu'ils ne puissent pas régler P vs NP. Si une relativisation ne préserve pas de tels arguments, ce n'est probablement pas une manière intéressante de relativiser des déclarations. Une bonne relativisation doit persister autant d'arguments connus et de résultats prouvés que possible, moins elle préserve, moins elle devient intéressante.

Kaveh