Reducibilidad

Solo disponible en BuenasTareas
  • Páginas : 11 (2523 palabras )
  • Descarga(s) : 4
  • Publicado : 8 de junio de 2010
Leer documento completo
Vista previa del texto
INSTITUTO TECNOLÓGICO SUPERIOR DE ALVARADO

CARRERA:
INGENIERIA EN SISTEMAS COMPUTACIONALES
DOCENTE:
OSCAR LUIS PEÑA VALERIO
MATERIA:
TEORIA DE LA COMPUTACION
TEMA:
REDUCIBILIDAD

INTEGRANTES DEL EQUIPO:
EDGAR YAIN BARRIENTOS MARTINEZ, 086Z0083
GRUPO:
ÚNICO

H. Y G. ALVARADO VER, 03-JUNIO-2010

INTRODUCCION

En el capítulo 4 establece lamáquina de Turing como modelo de un propósito general plantean equipo. Se presentaron varios ejemplos de problemas que tienen solución en una máquina de Turing y dio un ejemplo de un problema,, computacionalmente sin solución. En este capítulo analizaremos varios adicionales sin solución problemas. De este modo se introduce el método principal para demostrar que los problemas son computacionalmenteirresolubles. Se llama reducibilidad.
Una reducción es una manera de convertir un problema a otro problema, de tal manera que una solución al segundo problema se puede utilizar para resolver el primer problema. Reducibilidades estas se encuentran a menudo en la vida cotidiana, incluso si no se refieren generalmente de esta manera.
Por ejemplo, supongamos que usted quiere encontrar su camino enuna nueva ciudad. Usted saber que al hacerlo sería fácil si hubiera un mapa. Así se puede reducir el problema de encontrar su camino alrededor de la ciudad al problema de la obtención de un mapa de la ciudad.
Reducibilidad siempre implica dos problemas, que llamamos y . Si reduce a , podemos usar una solución a para resolver . Así pues, en nuestro ejemplo, es el problema de encontrar sucamino alrededor de la ciudad y es el problema de la obtención un mapa. Tenga en cuenta que la reducibilidad no dice nada sobre la solución o , sino sólo sobre la solvencia de en la presencia de una solución a .
Los siguientes son ejemplos de reducibilidad. El problema de viajar de Boston a París reduce al problema de comprar un billete de avión entre las dos ciudades. Ese problema, a su vezreduce el problema de ganarse el dinero para el billete. Y ese problema se reduce al problema de encontrar un empleo.

5.1
PROBLEMAS DE LA TEORÍA DEL LENGUAJE INDECIDIBLE
Ya hemos establecido la indecidibilidad de , el problema de determinar si una máquina de Turing acepta una entrada determinada. Vamos a considerar una relación problema,, el problema de determinar si una máquina de Turing(aceptando o rechazando) en una entrada determinada. Usamos la indecidibilidad de para demostrar la indecidibilidad de mediante la reducción de para . Que es un y se detiene en de entrada.
TEOREMA 5.1
es indecidible.
IDEA PRUEBA Esta prueba está en una contradicción. Suponemos que es decidible y utilizar esa hipótesis a demostrar que la atmósfera es decidible, contradiciendo Teorema 4.11. La ideaclave es mostrar que es reducible a .
Supongamos que tenemos un que decide . Luego usamos para construir , un que decide . Para tener una idea de la forma de construir , imagine que está . Su tarea es decidir . Se le da una entrada de la forma .Usted debe aceptar la salida si acepta , y debe rechazar la salida si rechaza .Trate de simular en . Si la acepta o la rechaza, hacer lo mismo. Peropuede no ser capaz de determinar si rechaza, y en ese caso la simulación no terminará. Eso es malo, porque usted es un decisivo y por lo tanto no permite circular. Así que esta idea, por sí sola, no funciona.
En su lugar, utiliza el supuesto de que usted tiene que decide . Con , se puede comprobar si se detiene en . Si esta en indica que no se detiene en , rechazan debido a que no es de .Sinembargo, si indica que se detiene en , puede hacer la simulación sin ningún peligro de rechazo.
Por lo tanto, si existe , podemos decidir , pero sabemos que es indecidible. En virtud de esta contradicción podemos concluir que no existe. Por lo tanto es indecidible.
PRUEBA Vamos a asumir a efectos de obtener una contradicción que la decide . Construimos decidir , con que operan como a...
tracking img