Ejercicios para la evaluación continua

Tema 6: Màquines de Turing. Decidibilitat, semidecidibilitat, computabilitat

Leyenda

= el ejercicio ha sido asignado a un/una estudiante/a y será resuelto en clase.
Para ver la asignación (y la fecha de entrega) consulta el racó.

Ejercicio 1 Escrivid TM sencillas para los siguientes lenguajes:

  1. \{a^nb^nc^n\;|\;n\geq 0\}.
  2. \{w_1\#w_2\;|\;w_1,w_2\in\{0,1\}^*\wedge\mathtt{valor}_2(w_1)=\mathtt{valor}_2(w_2)+1\}.
  3. \{ww\;|\;w\in\{0,1\}^*\}.
  4. \{0^{2^n}\;|\;n\geq 0\}

Ejercicio 2 Escrivid 2-TM (o 3-TM o 4-TM en caso de necesidad) sencillas para los siguientes lenguajes:

  1. \{a^nb^nc^n\;|\;n\geq 0\}.
  2. \{w_1\#w_2\;|\;w_1,w_2\in\{0,1\}^*\wedge\mathtt{valor} _2(w_(a)=\mathtt{valor} _2(w_2)+1\}.
  3. \{ww\;|\;w\in\{0,1\}^*\}.
  4. \{0^{2^n}\;|\;n\geq 0\}
  5. \{0^{n^2}\;|\;n\geq 0\}

Ejercicio 3 Argumenta a grandes rasgos que las máquinas de Turing no-deterministas no son más expresivas que las máquinas de Turing deterministas.

Ejercicio 4 Considera el modelo de máquina que definimos a grandes rasgos así: una variante de los autómatas con pila donde, en vez de una pila, tenemos dos pilas, las transiciones dependen del contenido de la cima de ambas pilas, i en la acción de cada transición se puede o bien borrar el elemento de la cima o bien añadir nuevos elementos, todo ello en ambas pilas. Justifica a grandes rasgos que este modelo puede simular una máquina de Turing, i que, por tanto, es Turing-completo.

Ejercicio 5 Considera el modelo de máquina que definimos a grandes rasgos así: una variante de los autómatas con pila donde, en vez de una pila, tenemos una cola, las transiciones dependen del contenido del inicio de la cola, i en la acción de cada transición se puede borrar el elemento del inicio, i también añadir nuevos elementos al final de la cola. Justifica a grandes rasgos que este modelo puede simular una máquina de Turing, i que, por tanto, es Turing-completo.

Ejercicio 6 Demuestra que los lenguajes decidibles son cerrados por las siguientes operaciones:

  1. Intersección.
  2. Complementario.
  3. Resta (de conjuntos).
  4. Reverso.
  5. Concatenación.
  6. Estrella.
  7. Morfismo inverso.
  8. Shiftado.

Ejercicio 7 Demuestra que los lenguajes decidibles no son cerrados por morfismo directo.

Ejercicio 8 Demuestra que los lenguajes semidecidibles son cerrados por las siguientes operaciones:

  1. Intersección.
  2. Concatenación.
  3. Reverso.
  4. Estrella.
  5. Morfismo directo.
  6. Morfismo inverso.
  7. Shiftado.

Ejercicio 9 Demuestra que los siguientes conjuntos son semidecidibles:

  1. \{\langle x,y\rangle\;|\;M_x(y)\downarrow\}.
  2. \{x\;|\;\exists y:M_x(y)\downarrow\}.
  3. \{\langle u,v,R\rangle\;|\;u\to_R^*v\}.
  4. \{G\in\mathtt{CFG}\;|\;G\text{ ambigua}\}.
  5. \{\langle G_1,G_2\rangle\;|\;G_1,G_2\in \mathtt{CFG}\;\wedge\;{\mathcal L}(G_(a)\cap{\mathcal L}(G_2)\not=\emptyset\}.

Ejercicio 10 Sea B un conjunto semidecidible i sea C un conjunto que cumple C=\{x\;|\;\exists y: \langle x,y\rangle\in B\}. Demuestra que C es semidecidible.

Ejercicio 11 Sea C un conjunto infinito. Demuestra que C es decidible si i solo si existe una función computable, total, inyectiva i creciente cuya imagen es C.

Ejercicio 12 Sea C un conjunto infinito. Demuestra que C es semidecidible si i solo si existe una función computable total e inyectiva cuya imagen es C.

Ejercicio 13 Sea f una función computable e inyectiva. Es f^{-1} computable e inyectiva?

Ejercicio 14 Sea f:\mathbb{N}\to\mathbb{N} una función estríctamente decreciente. Podemos asegurar que es computable?

Ejercicio 15 Sean A i B dos conjuntos tales que (A\cup B)-(A\cap B) es decidible i A es decidible. Eso implica que B es decidible?

Ejercicio 16 Sean A i B dos conjuntos tales que (A\cup B)-(A\cap B) es decidible i A es semidecidible. Eso implica que B es semidecidible?