6.045J/18.400J: Autmatas, computabilidad y complejidad Prof. Ron Rivest

Fotocopia 10a: prueba 2 alternativa Escriba su nombre completo en cada pgina.

1

Nombre: _______________________________________________________________________ Problema 2: (15 puntos) demuestre que existe una mquina de Turing M que acepta nicamente mquinas con menos estados que la propia M. (Consejo: teorema de recursin).

2

Nombre: _______________________________________________________________________ Problema 3: (15 puntos) Sea, { }1, 2 1 2 1 2 : y son mquinas de Turing y ( ) ( ) 0L M M M M L M L M= = / Demuestre que L es indecidible.

3

Nombre: _______________________________________________________________________ Problema 4: (15 puntos) demuestre que todo lenguaje infinito reconocible tiene un sublenguaje infinito decidible. (Un lenguaje L es un sublenguaje de un lenguaje si ). Consejo: recuerde que un lenguaje es decidible si existe un enumerador que lo enumere en orden lexicogrfico.

L L L

4

Nombre: _______________________________________________________________________ Problema 5: (15 puntos) Una mquina de colas es parecida a una mquina de Turing, excepto que la primera tiene una cola en lugar de una cinta. Tiene un alfabeto de colas y un alfabeto de entrada finito . Si es la entrada, entonces la mquina comienza a funcionar en su estado de salida con x$ en la cola (donde $ es un smbolo especial en

*x

que se encuentra al final de la cola). En cada paso, elimina un smbolo de la cabeza de la cola. Basndose en ese smbolo y en el estado actual, empuja a una cadena *z al final de la cola e introduce un nuevo estado segn su funcin de transicin. Acepta dejando la cola vaca. Demuestre que una mquina de cola es tan poderosa como una mquina de Turing.

5

Fotocopia 10a: prueba 2 alternativa