Se pueden establecer las codificaciones de una clase no trivial de idiomas que contiene el conjunto vacío sea recursivamente numerable?

Question

Let $ C $ sea un conjunto no trivial de lenguajes recursivamente enumerables ($ \ emptyset \ subsetneq C \ subsetneq \ mathrm {RE} $) y dejar $ L $ el conjunto de codificaciones de las máquinas de Turing que reconocen algún lenguaje en $ C $: $$ L = \ {\ langle M \ rangle \ mediados L (M) \ en C \} $$

Supongamos que $ \ langle M_ {descabellado} \ rangle \ en L $, donde $ M_ {descabellado} $ es un TM que nunca se detiene. Me pregunto si es posible que L $ \ en \ mathrm {RE} $?

El teorema de Rice sé que $ L \ notin \ mathrm {R} $ (el conjunto de lenguajes recursivos), así que o $ L \ notin \ mathrm {RE} $ o $ \ overline {L} \ notin \ mathrm {RE} $. ¿Tiene que ser la primera opción ya $ M_ {descabellado} \ in L $?

Answer 1

No, eso no es posible. Existe una versión extendida de theorem¹ de Rice para probar un conjunto de índices no es recursivamente numerable.

En su notación, las teorema que si una (no trivial) $ C $ contiene un lenguaje $ L_1 $ que tiene un superconjunto adecuada $ L_2 $ no en $ C $, entonces $ L \ notin \ mathrm {RE} $. La intuición es que ningún algoritmo puede separar codificaciones de $ L_1 $ y $ $ L_2; no pueden decidir que la máquina codificada hace no aceptar ninguna palabra de $ L_2 \ setminus L_1 $ después de una cantidad finita de tiempo, que tenían que hacerlo.

Ahora usted requiere $ \ emptyset \ en C $, pero $ C \ neq 2 ^ {\ Sigma ^ *} $, por lo tanto, el teorema se aplica y $ L $ no es recursivamente numerable.

---

1. El href="https://en.wikipedia.org/wiki/Rice%27s_theorem" rel="nofollow"> artículo es horrible, ¡cuidado!

Answer 2

para completar la respuesta de Rafael, hay una extensión del teorema de Rice, que dice lo siguiente:

Generalizado de Rice Teorema

Sea $ S \ subseteq RE $ haber alguna propiedad, y dejó $ $ L_S ser todas las medidas comerciales que satisfacen la propiedad $ S $, es decir, $$ L_S = \ {\ langle M \ rangle \ mediados L (M) \ in S \}. $$ Entonces, $ L_S \ en RE $ si y sólo si todos cumplen las siguientes condiciones:

1. $ para cualquier L_1, L_2 \ $ en RE, si $ L_1 \ en S $ y $ L_1 \ subseteq L_2 $ entonces $ L_2 \ en S $.
2. Si \ en S $ entonces existe un número finito L_1 $ $ L_2 \ subseteq L_1 $ tal que $ L_2 \ en S $.
3. El lenguaje de 'todos los idiomas finitos en $ S $' está en RE. gratis (en otras palabras, existe una TM $ $ M_S que, si $ L $ es un lenguaje finito $ L = \ {W_1, w_2, \ ldots w_k) $ y $ (W_1, w_2, \ ldots, w_k) $ se da a $ $ M_S como una entrada, $ M $ acepta sólo si $ L \ en S $.

Ahora, de vuelta a la pregunta original. Tenemos ahora que $ \ langle M_ {descabellado} \ rangle \ en L $ por lo que $ l (\ langle M_ {descabellado} \ rangle) \ en C $. Pero $ l (\ langle M_ {descabellado} \ rangle) = \ emptyset $ TM ya que este nunca se detiene. Esto significa que $ \ emptyset \ en C $.

Ahora vamos a ver en la primera condición del teorema anterior. CUALQUIER idioma $ L $ satisface $ \ emptyset \ subseteq L $. Por lo tanto, a fin de satisfacer la condición 1, debe ser que $ C = RE $. Sin embargo, los estados de interrogación que $ C \ subsetneq RE $ y por lo tanto, por el teorema, $ L \ notin RE $.

Answer 3

Es posible que $ L $ es un R. E. conjunto. Considere el caso $ = C $ RE. Entonces $ L $ es el conjunto de todos los códigos de todas las máquinas de Turing. Este es un conjunto recursivo, de hecho, dependiendo de los detalles de la codificación, podríamos tener $ L = \ mathbb {N} $. Así que en realidad es falso que $ L $ no puede ser recursivo.

Sospecho que mal formulado la pregunta.