¿Los idiomas en $ \ mathsf {core} \ setminus \ mathsf {r} $ tienen máquinas de Turing?

Question

¿Qué podemos decir sobre los idiomas en $ \ mathsf {núcle} \ setminus \ mathsf {r} $ ?¿Hay máquinas de Turing para estos idiomas?

Sé que $ \ overline {hp} \ in \ mathsf {núcleo} $ no tiene una máquina de Turing, y también que todo el idioma que hagatener máquinas de Turing están en $ \ mathsf {re} $ , por lo que es cierto que para cualquier idioma que esté en $ \mathsf {core} \ setminus \ mathsf {r} $ ¡No hay una máquina de Turing?Me pregunto por qué es así, ¿puede alguien elaborar?

Answer 1

Podemos asociar un idioma a una máquina de Turing de varias maneras.

Si la máquina de Turing se detiene en todas las entradas, entonces el idioma aceptado por la máquina de Turing consiste en todas las palabras que hacen que la máquina de Turing se detenga en un estado de aceptación. La clase $ \ mathsf {r} $ consiste en todos los idiomas que son aceptados por una máquina de Turing.

Para una máquina de Turing arbitraria, el idioma reconocido por la máquina de Turing consiste en todas las palabras que hacen que la máquina de Turing se detenga (en cualquier estado). La clase $ \ mathsf {re} $ consiste en todos los idiomas que son reconocidos por una máquina de turaje.

si $ l \ in \ mathsf {núcle} \ setminus \ mathsf {r} $ , luego en particular $ L \ notin \ mathsf {r} $ , por lo que no se acepta la máquina de Turing $ l $ . Si $ l $ fueron reconocidos por alguna máquina de Turing, entonces $ l \ in \ mathsf {re} $ . Sin embargo, esto es imposible, desde entonces $ l \ in \ mathsf {re} \ cap \ mathsf {núcle}=mathsf {r} $ .

Answer 2

Permítanme expandirme en la primera oración de la respuesta de Yuval Filmus:

Podemos asociar un idioma a una máquina de Turing de varias maneras.

Yuval menciona dos: Aceptación (que caracteriza $ \ mathsf {r} $ ) y reconocimiento ( que caracteriza a $ \ mathsf {re} $ ). Sin embargo, hay otros. Obviamente, podríamos considerar "co-reconocimiento": diga que una máquina de Turing $ m $ "co-reconoce" un idioma $ L $ Si las cadenas en $ l $ son exactamente las cuerdas en las cuales $ m $ no se detiene detener. Luego, por supuesto, el co-reconocimiento caracteriza a $ \ mathsf {núcleo} $ .

Sin embargo, eso es un poco antinatural. Mucho más natural en mi opinión es la noción de computabilidad de límite . Fraseados en términos de números naturales para la simplicidad, este es el siguiente:

una función $ f: \ mathbb {n} \ judowarrow \ mathbb {n} $ es Limit computable IFF Hay un computable Función $ h: \ mathbb {n} ^ 2 \ rudotrow \ mathbb {n} $ tal que $$ f (x )=lim_ {s \ rudowarrow \ infty} h (x, s), $$ o más precisamente de tal que para todos $ x $ hay Algunos $ n $ de tal que para todos $ s> n $ tenemos $ h (x, s)= f (x) $ .

A Set $ x $ es Limite computable, mientras tanto, IFF hay una función de límite computable $ f $ de modo que $ x={i: f (i)= 1 \} $ . (Hay muchas otras formulaciones equivalentes de esto.)

Resulta que la computabilidad límite tiene una caracterización alternativa muy agradable:

(shoenfield) una función $ f $ es Limite computable IFF IT es computable en relación con el problema de detención $ \ vacioset '$ .

(y a través de Post Obtendramos otra caracterización en términos de "complejidad de la definición. ")

Por supuesto, esto incluye tanto $ \ mathsf {re} $ y $ \ mathsf {núcleo} $ , y mucho más, además, hay estableces computables en relación con el problema de detención que no están de turing equivalente a ningún conjunto en $ \ mathsf {re} $ . (¡Esto es difícil de probar!)

y hay incluso más formas de asignar idiomas a los conjuntos; Por ejemplo, podemos hablar de "Limitar la Reconocimiento" (que es limitar la computabilidad como la reconocimiento es aceptar), lo que nos da la $ \ sigma ^ 0_2 $ Idiomas.