Complejidad y Computabilidad

COMPLEJIDAD Y COMPUTABILIDAD

Cuestionario de Twitter

Test 1

1. Sea L = ε, entonces L es recursivo.

VERDADERO.

Efectivamente L = ε es recursivo. Por ejemplo, la MT dada por δ(q1,B) = (q2,B,L) lo decide.

1. Sea L = 1(0+1)*, entonces L es recursivo.

VERDADERO.

Efectivamente L = 1(0+1)* es recursivo. Por ejemplo, la MT dada por δ(q1,1) = (q2,1,R) lo decide.

1. Sea L = 0(0+1)*, entonces L es recursivo.

VERDADERO.

Efectivamente L = 0(0+1)* es recursivo. Por ejemplo, la MT dada por δ(q1,0) = (q2,0,R) lo decide.

1. Puede ocurrir que L sea recursivo y que no exista ninguna MT que decida el complementario de L.

FALSO.

Efectivamente, no puede ocurrir que L sea recursivo y que no exista ninguna MT que decida al complementario de L, ya que si L es recursivo, el complementario de L también es recursivo y esto equivale a que existe una MT que lo decide.

1. Los lenguajes recursivos son cerrados respecto de la operación complementario.

VERDADERO.

Efectivamente, los lenguajes recursivos son cerrados respecto de la operación complementario.

1. Un lenguaje es recursivo si y solo si existe una MT que lo acepta.

VERDADERO.

Efectivamente, un lenguaje es recursivo si y solo si existe una MT que lo decida.

Test 2

1. Sea wi = 1000, entonces Mi es la M1000.

FALSO.

Si wi = 1000, Mi no es válida y se le asocia la MT “vacía” (un estado y ninguna transición). De igual forma, M1000 está dada por la cadena 111101000 también no válida, por lo que se la asocia también la MT “vacía”.

1. Sea wi = 01000100100010, entonces L(Mi) verifica que L(Mi) = vacío.

FALSO.

Efectivamente, wi = 01000100100010 es un código válido, asociado a M20770, que verifica que L(Mi) = ε, distinto del vacío.

1. Sea wi = 01010010100, entonces L(Mi) verifica que L(Mi) = vacío.

FALSO.

Efectivamente, wi = 01010010100 es un código válido, asociado a M2708, que verifica que L(Mi) = 0(0+1)*, distinto del vacío.

1. Sea wi = 0101001010, entonces L(Mi) verifica que L(Mi) = vacío.

FALSO.

Efectivamente, wi = 0101001010 es un código válido, asociado a M1354, que verifica que L(Mi) = 0(0+1)*, distinto del vacío.

1. Sea wi = 01010011010, entonces L(Mi) verifica que L(Mi) = vacío.

VERDADERO.

Al ser wi = 01010011010 un código no válido, se le asocia L(Mi) vacío.

1. Las MT deterministas de una cinta pueden codificarse de forma que constituyan un conjunto infinito numerable.

VERDADERO.

Efectivamente, las MT deterministas de una cinta pueden codificarse de forma que constituyan un conjunto infinito numerable.

Test 3

1. Si wi pertenece a Lnd, entonces el vector característico de Mi está formado por todo unos.

FALSO.

Efectivamente, si wi pertenece a Lnd, entonces no se tiene forzosamente que todo el vector característico de Mi esté formado por unos.

1. Si el vector característico de Mi está formado por todo unos, entonces wi pertenece a Lnd.

VERDADERO.

Efectivamente, si el vector característico de Mi está formado por todo unos, entonces wi pertenece a Lnd.

1. Si wi pertenece a Ld, entonces el vector característico de Mi tiene un 1 en la coordenada n-ésima.

FALSO.

Efectivamente, si wi pertenece a Ld, entonces el vector característico de Mi tiene un 0 en la coordenada i-ésima.

1. L(M682) es un ejemplo de lenguaje de diagonalización.

FALSO.

L(M682) no es un ejemplo de lenguaje de diagonalización. Lo que sí es cierto es que w682 pertenece al Ld, ya que L(M682) es el conjunto vacío y w682 no pertenece, por tanto, a L(M682).

1. w2708 pertenece a Ld.

FALSO.

Efectivamente, w2708 pertenece a L(M2708) = 0(0+1)*, por lo que w2708 no pertenece a Ld.

1. El lenguaje de diagonalización es aquel que no es aceptado por ninguna máquina de Turing.

VERDADERO.

La definición de Ld no es aquel que no es aceptado por ninguna máquina de Turing, sino aquel que está formado por todas las codificaciones de MT que no forman parte del lenguaje de la MT que codifican.

Test 4

1. Lne es RE no recursivo.

VERDADERO.

El lenguaje Lne es indecidible, verificando que es RE no recursivo.

1. Le es RE no recursivo.

FALSO.

No es cierto que Le sea RE no recursivo. Le es indecidible, verificando que es no-RE.

1. Le = Ld.

FALSO.

No es cierto que Le = Ld. Aunque sí es cierto que Le está contenido en Ld, sin embargo, Ld no está contenido en Le (por ejemplo, w10532 pertenece a Ld y no pertenece a Le).

1. Le es el lenguaje vacío.

FALSO.

El lenguaje vacío no tiene cadenas, ni siquiera la cadena vacía, mientras que el lenguaje Le sí tiene cadenas.

1. w1354 pertenece a Le.

FALSO.

w1354 no pertenece a Le ya que L(M1354) no es el vacío.

1. w100 pertenece a Le.

VERDADERO.

w100 pertenece a Le ya que L(M100) es el vacío.

Test 5

1. El PCPM planteado sobre (1,11) y (01,0) tiene respuesta negativa en esta instancia.

VERDADERO.

Tiene respuesta negativa ya que habría que empezar con (1,11) y se estaría obligado a repetir ficha sin parar.

1. El complementario del PCP es recursivo.

FALSO.

Es falso que el complementario del PCP sea recursivo. Si el complementario del PCP fuera recursivo, su complementario, es decir, el PCP, sería recursivo y entraría en contradicción con el hecho de que el PCP es indecidible.

...