Reducción de A_LBA a E_LBA

Question

Tengo uno bastante interesante para reflexionar y me encantaría si pudiera obtener una respuesta para ello. Estábamos discutiendo el tema de la reducción de mapeo hoy en mi curso de teoría de la computación y me preguntaba por qué esta reducción no puede existir, $ A_ {LBA} LEQ_ {M} E_ {LBA} $, ya que ambos son autómatas con límite lineales. (LBA). Me doy cuenta de que $ e_ {lba} $ es indecidible, $ a_ {lba} $ es decidible, y la prueba normal usa $ a_ {tm} $, o $ e_ {tm} $, para probar la indecidibilidad de $ e_ { LBA} $. Tengo curiosidad por qué la prueba está usando un TM para probar un LBA. Pero, mi profesor no pudo encontrar una solución a mi confusión. Me preguntaba que es posible, si es así, por qué o por qué no.

Definiciones:

$ A_ {lba} = { langle m, w rangle mid text {$ m $ es un autómata con límite lineal que acepta la cadena $ w $} } $

$ E_ {lba} = { langle m rangle mid text {$ m $ es un autómata con límite lineal con $ l (m) = showyset $} } $

$ A_ {tm} $ y $ e_ {tm} $ son los problemas equivalentes para las máquinas Turing.

Answer 1

Tienes tu mapeo de la manera incorrecta. Tal como está, sería una reducción de un problema decidible a un problema indecidible. Ciertamente es posible (ver más abajo), pero no nos dice nada.

Recuerde que si $ a leq_ {m} b $, entonces un algoritmo que resuelve $ B $ (o decide la membresía en este caso) puede usarse para resolver $ A $ (decida la membresía en $ A $). Entonces, la reducción que está viendo nos diría que cualquier decisivo para $ e_ {lba} $ podría usarse para decidir $ a_ {lba} $. También sabemos que $ e_ {lba} $ es indecidible, pero esto no impide que haya algún decisivo para $ a_ {lba} $ que no decide $ e_ {lba} $.

De hecho, la reducción que no puede existir es $ e_ {lba} leq_ {m} a_ {lba} $, ya que esto implicaría que podríamos decidir $ e_ {lba} $, que sabemos que no podemos.

Para la segunda parte, la prueba (o más bien, una de las pruebas posibles) que $ E_ {LBA} $ es indecidible es mediante la construcción de la asignación $ a_ {tm} leq_ {m} e_ {lba} $, así que nuevamente a El decisor por $ e_ {lba} $ nos daría un decisivo para $ a_ {tm} $, pero ya sabemos que $ a_ {tm} $ es indecidible, por lo que $ e_ {lba} $ también debe ser indecidible.

En cuanto a por qué La prueba utiliza un lenguaje que involucra a las máquinas Turing para mostrar algo sobre los autómatas con límite lineal, es porque funciona.

Una reduccion

Como $ a_ {lba} $ es decidible, podemos tomar la entrada lba $ m $ y string $ w $, y ejecutar el decisor en $ langle m, w rangle $. Si acepta, asignamos esto a un LBA $ M_ {REJ} $ que rechaza inmediatamente. Si el decisor rechaza, lo asignamos a un LBA $ m_ {acc} $ que acepta inmediatamente. Por lo tanto, $ m_ {acc} $ acepta toda la entrada y no está en $ e_ {lba} $, y $ m_ {rej} $ rechaza toda la entrada y está en $ e_ {lba} $.

Tenga en cuenta, por supuesto, que esta reducción es en cierto sentido trivial, y el subconjunto de $ E_ {LBA} $ se mapea es finito y, por lo tanto, decidible (¡incluso regular!).

Otra perspectiva

Dados dos idiomas $ a $ y $ b $ tal que $ a leq_ {m} b $, hay dos cosas básicas (útiles) que nosotros puede que poder decir:

• Si $ B $ es decidible Entonces $ A $ también es decidible.
• Si $ A $ es indecidible Entonces $ B $ también es indecidible.

En nuestro caso, $ a $ es decidible, y $ B $ es indecidible, lo que coincide con ninguna de estas posibilidades, por lo que la reducción $ a_ {lba} leq_ {m} e_ {lba} $ no nos dice nada sobre la decidencia de cualquiera de las.