Pour toute langue

J'essaie de trouver une preuve pour les éléments suivants:

Pour toute langue $A$ , il existe un langage $B$ tel que $A \le_{\mathrm{T}} B$ , mais B $\nleq_{\mathrm{T}} A$ .

Je pensais laisser $B$ être $A_{\mathrm{TM}}$ , mais je me rends compte que toutes les langues ne sont pas Turing réductibles à $A_{\mathrm{TM}}$ , donc $A \le _T B$ ne tiendrait pas. Quel autre choix de $B$ ai-je qui me permettrait d'écrire une MT qui utilise un oracle pour que $B$ décide $A$ ?

Merci!

computability reductions undecidability user1354784
la source

Que diriez-vous de

B = N P^{A}

$B = NP^A$ ?

Eugene

Pensez au problème de l' arrêt sur les machines de Turing avec oracle

A

$A$ .

Willard Zhan

@ user1354784 Les machines de Turing avec oracle

A

$A$ peuvent être énumérées. Essayez donc d'utiliser la diagonalisation standard, où le seul changement est que pour chaque

α \in Σ^{*}

$\alpha\in\Sigma^*$ ,

M_{α}

$M_\alpha$ représente une TM oracle avec l'oracle

A

$A$ au lieu d'une TM normale.

Willard Zhan

@DavidRicherby Oui, mais B n'est pas fixe, il est construit en sachant ce qu'est A. Si on nous donne un A, nous construisons un B qui accepte chaque TM oracle avec un oracle pour ce A spécifique qui accepte les chaînes en A. Si on nous donne un A différent, la liste des TM dans B sera différente.

user1354784

@ user1354784 Exactement. Je voulais dire ce commentaire comme une autre explication de la raison pour laquelle nous ne pouvons pas prendre comme vous l'aviez suggéré (et déjà rejeté, pour une raison différente) dans votre question. J'ai oublié d'expliquer que c'était le point que je faisais - désolé pour la confusion là-bas.

B = A_{T M}

$B=A_{\mathrm{TM}}$

David Richerby

Réponses:

Soit , le saut de Turing . C'est un résultat de base dans la théorie des degrés de Turing. $B=A'$ $A$

Bjørn Kjos-Hanssen
la source

Avant de plonger dans la bonne réponse - à savoir que nous pouvons relativiser le problème d'arrêt pour attribuer à chaque langue une langue telle que (entre autres) - cela vaut la peine de voir la réponse idiote : $X$ $X'$ $X<_TX'$

Cantor a montré qu'il existe d'innombrables langues.
Mais chaque langue spécifique ne peut calculer que de nombreuses langues: une seule machine Turing ne peut générer qu'une réduction par rapport à une langue donnée , et il n'y a que de nombreuses machines Turing. $A$ $A$

Donc, en fait, nous savons, sans faire aucun travail sérieux, que:

Pour toutes les langues , la plupart (= tous mais beaucoup) dénombrable langues satisfont . $A$ $B$ $B\not\le_TA$

Maintenant , nous combinons ceci avec la Turing se joignent : langues données , la jointure se compose de « entrelacer » et . Il existe différentes façons de le définir - par exemple, en considérant et comme des ensembles de naturels, nous laissons généralement - mais la caractéristique importante est que (et en fait est leur -least borne supérieure) . $X,Y$ $X\oplus Y$ $X$ $Y$ $X$ $Y$ $X\oplus Y=\{2i: i\in X\}\cup\{2i+1: i\in Y\}$ $X\oplus Y\ge_TX,Y$ $\le_T$

Nous pouvons donc appliquer ce qui précède, pour obtenir:

Pour toutes les langues , la plupart (= tout sauf dénombrable beaucoup) langues satisfont . $A$ $B$ $A<_TA\oplus B$

Cela pose alors la question de donner une preuve non stupide , à savoir un moyen naturel de produire un langage strictement plus compliqué qu'un langage donné, et c'est à cela que sert le saut de Turing; mais cela vaut la peine de comprendre cet argument non constructif par lui-même.

Noah Schweber
la source