El sub idioma no es reconocible por Turing, ¿o podría serlo?

10

Deje que A y B sean idiomas con A ⊆ B, y B sea reconocible por Turing. ¿Puede A no ser reconocible por Turing? Si es así, ¿hay algún ejemplo?

computability gfe
fuente

18

Esto es algo que confunde a muchos estudiantes. El punto aquí es que ser un subconjunto de otro idioma no implica mucho sobre su dificultad de cálculo. Siempre puede considerar el lenguaje trivial y y cualquier otro idioma está entre ellos. $\emptyset$ $\Sigma^*$

Por lo tanto, el simple hecho de saber que un idioma contiene o está contenido en un lenguaje fácil de calcular no dice nada acerca de la dificultad de calcularlo.

Kaveh
fuente

Pero no puedo encontrar ningún idioma de subconjunto de Σ ∗ que no sea reconocible por Turing.

gfe

3

@Wilhelm, toma cualquier idioma que no sea reconocible por Turing y funcionará.

Kaveh

Ya veo, así que puedo usar el problema de detención para demostrar que existe tal lenguaje.

gfe

@Wilhelm, sí. :)

Kaveh

1

Cuando un lenguaje reconocible por Turing no es decidible, implica que no es reconocible conjuntamente por Turing (en otras palabras: no es reconocible). Dado que es un subconjunto perfectamente válido de , esto respalda el hecho de que para un lenguaje donde es reconocible por Turing, puede no serlo. $X$ $X^c$ $X^c$ $\Sigma^*$ $A \subseteq B$ $B$ $A$

Lijadora
fuente

Creo que la respuesta de Kaveh es mejor y más precisa. Cualquier idioma es un subconjunto de y sabemos que es decidible y que existen idiomas arbitrariamente difíciles.

Σ^{*}

$\Sigma^*$

Σ^{*}

$\Sigma^*$

Pål GD

Eso es lo que intenté explicar, ya que podría ser cualquier lenguaje, porque se mantiene automáticamente. ;)

X

$X$

X \subset Σ^{*}

$X \subset \Sigma^*$

Sander

-3

Su discusión me confundió con éxito :(

"¿Puede A no ser reconocible por Turing?"

Siento que A siempre es reconocible por Turing . Aquí está mi pensamiento

Como B es Turing reconocible => Hay una TM que acepta todas las palabras del lenguaje B => Hay una TM que acepta (todas las palabras del lenguaje A + algunas otras palabras) => Hay una TM que acepta todas las palabras del lenguaje A => A es Turing reconocible.

¿Esto esta mal? ¿Puede haber algún caso en el que A no sea TRL mientras B sea TRL? Amablemente ayuda

bongubj
fuente

1

Sí, está mal: un aceptante de un idioma no debe aceptar ninguna palabra, excepto las del idioma.

reinierpost

No publique preguntas de seguimiento como respuestas. Use comentarios (después de haber demostrado al sistema que es confiable) o cree una nueva publicación si la nueva pregunta es significativamente diferente (no es el caso aquí).

Raphael

-4

En este caso, A no podría ser reconocible por Turing. Toma esto como un ejemplo:

la lengua B es la unión de una lengua tr (C) y una lengua no tr (A). puede crear una máquina de turing que reconozca B. A no es tr y A ⊆ B.

¿está bien? No sé si es ... así que ... =)

Philip A.
fuente

3

No todas las uniones de y son reconocibles. Por ejemplo, deje que y el problema de detención. Usted no puede crear una máquina de Turing que reconoce .

C \in R E

$C\in RE$

A \notin R E

$A\notin RE$

C = \emptyset

$C=\emptyset$

A

$A$

B = A \cup C

$B=A \cup C$

Ran G.

El sub idioma no es reconocible por Turing, ¿o podría serlo?

Respuestas: