Reducibilidad teoria de la computacion

6. REDUCIBILIDAD

Competencias que deberán ser adquiridas | * Capacidad de investigación * Autonomía en el aprendizaje * Creatividad * Capacidad de Análisis y síntesis * Organización y Planificación * Comunicación oral y escrita * Utilización de las tecnologías de comunicación y de información (TIC`S) * Trabajo en equipo |
Objetivo de aprendizaje | Capacidad para demostrarque un problema es issoluble. |

Resultado del aprendizaje | Actividad Educativa | Evaluación | Tiempo |
Capacidad de distinguir entre problemas solubles e insolubles | * Búsqueda de conceptos por equipos en los que podrá leer, descubrir, cuestionar, preguntar indagar. * Discusión en clase para expresarse, comunicar ideas, etc. * Creación de ideas originales obtenidas en consenso. |* Informes por equipo y conclusiones grupales. * Técnicas de observación(registros, listas de control) | 1 horas |
Aplicación de un problema simple insoluble. | * Búsqueda de problemas insolubles por equipos en los que podrá leer, descubrir, cuestionar, preguntar indagar. * Exposición en clase para expresarse, comunicar ideas, etc. | * Informes por equipo de problemas insolublesy conclusiones grupales. | 1 hora |
Funciones computables | * Búsqueda de conceptos por equipos en los que podrá leer, descubrir, cuestionar, preguntar indagar. * Realizar ejercicios sobre funciones computables | * Informes por equipo de funciones computables y conclusiones grupales. * Ejercicios sobre funciones computables. * Prueba de respuesta con desarrollo. | 2 horas |Reducibilidad de Turing | * Búsqueda de conceptos por equipos en los que podrá leer, descubrir, cuestionar, preguntar indagar. * Realizar ejercicios sobre reducibilidad de Turing | * Informes por equipo de funciones computables y conclusiones grupales. * Ejercicios sobre funciones computables. * Prueba de respuesta con desarrollo. | 2 horas |

6. REDUCIBILIDAD
6.1 PROBLEMASINSOLUBLES PARA LA TEORÍA DE LENGUAJES
Se ha visto que los algoritmos son un concepto fundamental de la ciencia de la computación y se ha desarrollado cierto conocimiento interno sobre la forma en que pueden construirse. Se sabe que existen algoritmos para tejer un suéter, construir un modelo de aeroplano, preparar un pastel y ejecutar una sonata de Beethoven. Es conocido que las computadoras puedencontrolar señales de tráfico, líneas de producción y plantas químicas. Pueden llevar las revisiones de vuelos en líneas aéreas, controlar robots y producir nominas. Existen algoritmos para preparar una taza de café, determinar cuál es el mayor de un conjunto de números, descubrir si un número es primo o no primo e imprimir el máximo común divisor de 2 números.
Desde la época escolar se recuerdaque existen algoritmos para sumar, resta, multiplicar y dividir números enteros y para calcular raíces cuadradas. Sin duda existen algoritmos para calcular logaritmos, determinar la frecuencia de las palabras en un fragmento dado de texto y controlar un submarino nuclear.
Existen trabajos que las computadoras no pueden realizar. Hay muchas cosas que una computadora no puede hacer. En realidad, elnúmero de cosas que pueden calcularse o computarse es infinitesimal en comparación con el número de cosas que a uno le gustaría calcular, las computadoras no pueden hacer muchas cosas. Algunos ejemplos que no se pueden resolver por una computadora son:
Los que ya conocemos
• El problema de parada: Dado un programa p y una entrada x, ¿p con entrada x para?
• Dados dos programas, ¿calculan lomismo?
• Los que nos da el teorema de Rice:
– Dado un programa p, ¿p calcula una función inyectiva?
– Dado un programa p, ¿p para con alguna entrada?
–Dadas 5 imágenes. ¿Cual es la más llamativa?

Algunos parecidos
El “busy beaver”:
• Dado n natural, t natural ¿Es t el tiempo máximo que tardan los programas de longitud n con entrada 0?
Es decir,
∀p con |p|=n, p(0)↑ ó (p(0)↓ y tarda...