Les langues en $ \ mathsf {core} \ setminus \ mathsf {r} $ ont des machines de Turing?

Question

Que pouvons-nous dire sur les langues dans $ \ mathsf {noyau} \ setminus \ mathsf {r} $ ?Y a-t-il des machines de Turing pour ces langues?

Je sais que $ \ overline {hp} \ in \ mathsf {noyau} $ n'a pas de machine de Turing, et aussi que toute la langue qui faitAvoir des machines de Turing sont dans $ \ mathsf {re} $ $ , il est donc vrai que pour toute langue dans $ \mathsf {core} \ setminus \ mathsf {r} $ Il n'y a pas de machine de Turing?Je me demande pourquoi c'est-à-dire que quelqu'un peut-il élaborer?

Answer 1

Nous pouvons associer une langue à une machine de Turing de plusieurs manières.

Si la machine de Turing s'arrête sur toutes les entrées, la langue acceptée par la machine Turing se compose de tous les mots qui provoquent la halte de la machine de Turing dans un état d'acceptation. La classe $ \ mathsf {r} $ consiste en toutes les langues acceptées par une machine de Turing.

Pour une machine de Turning arbitraire, la langue reconnue par la machine Turing se compose de tous les mots qui provoquent la halte de la machine de Turing (dans n'importe quel état). La classe $ \ mathsf {re} $ se compose de toutes les langues reconnues par une machine de Turing.

si $ l \ in \ mathsf \ mathsf \ setminus \ mathsf {r} $ , puis en particulier $ L \ notin \ mathsf {r} $ , et donc aucune machine de Turing n'accepte $ l $ . Si $ L $ a été reconnu par une machine de Turing, alors $ l \ mathsf {re} $ $ . Cependant, cela est impossible, car alors $ l \ in \ mathsf {re} \ cap \ mathsf {noyau}=mathsf {r} $

.

.

.

Answer 2

Permettez-moi de développer la première phrase de la réponse de Yuval Filmus:

Nous pouvons associer une langue à une machine de Turing de plusieurs manières.

Yuval mentionne deux: acceptation (ce qui caractérise $ \ mathsf {r} $ ) et reconnaissance ( qui caractérise $ \ mathsf {re} $ ). Il y en a d'autres, cependant. Plus évidemment, nous pourrions envisager de "co-reconnaissance" - disons qu'une machine de Turing $ M $ "co-reconnaît" une langue $ L $ si les chaînes de $ l $ sont exactement les chaînes sur lesquelles $ m $ Est-ce que pas arrête. Puis, bien sûr, la co-reconnaissance caractérise $ \ mathsf {noyau} $ .

Cependant, c'est un peu non naturel. Beaucoup plus naturel à mon avis est la notion de Compubilité limite . Phrasé en termes de nombres naturels pour la simplicité, c'est ce qui suit:

une fonction $ F: \ mathbb {n} \ mathbb \ mathbb {n} $ est limite calculable iff il y a un calculable fonction $ H: \ mathbb {n} ^ 2 \ rightarrow \ mathbb {n} $ $ tel que $$ f (x )=lim_ {s \ droite} h (x, s), $$ ou plus précisément tel que pour tous $ x $ il y a certains $ n $ tel que pour tous $ s> n $ nous avons $ h (x, s)= f (x) $ .

a jeu $ x $ est limité calculable, quant à cela, la fonction de la fonction calculable limite $ f $ tel que $ x={i: f (i)= 1 \} $ . (Il existe de nombreuses autres formulations équivalentes de cela.)

Il s'avère que la taille de la limite a une très belle caractérisation de remplacement:

(shoenfield) une fonction $ f $ est limite calculable si elle est calculable par rapport à Le problème d'arrêt $ \ videtyset '$ .

(et via POST Nous obtenons une autre caractérisalisation en termes de "complexité de la définition. ")

Bien sûr, cela inclut les deux $ \ mathsf {re} $ $ et $ \ mathsf {noyau} $ , et bien plus encore: il existe des ensembles de paramètres relatifs au problème d'arrêt qui ne contient pas d'équivalent à tout ensemble dans $ \ mathsf {re} $ . (C'est difficile à prouver!)

Et il existe encore plus de moyens d'attribuer des langues aux ensembles; Par exemple, nous pouvons parler de "Limiter la reconnaissance" (qui doit limiter la calculatrice à mesure que la reconnaissance est d'accepter), ce qui nous donne le $ \ SIGMA ^ 0_2 $ langues.