Decibilidad

DECIBILIDAD

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 distinguirproblemas decidibles e indecidibles. |

Resultado del aprendizaje | Actividad Educativa | Evaluación | Tiempo |
Comprensión y capacidad de utilizar en un contexto adecuado conceptos de decibilidad, lenguajes recursivamente e numerables y recursivos | * 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 |
Capacidad para demostrar que el problema de parada en un problema indecidible | * Búsqueda de conceptos por equipos en los que podrá leer, descubrir, cuestionar, preguntar indagar sobre elproblema de parada * Discusión en clase para expresarse, comunicar ideas, etc. | * Informes por equipo y conclusiones grupales. * Técnicas de observación(registros, listas de control) | 1 hora |
Capacidad para demostrar que las teorías lógicas aplicadas a la teoría de la computación es un problema decidible | * Búsqueda de conceptos por equipos en los que podrá leer, descubrir,cuestionar, preguntar indagar. * Clase teórica sobre Inducción Matemática * Realizar ejercicios sobre inducción matemática | * Realizar ejercicios sobre inducción matemática * Prueba de respuesta con desarrollo. | 2 horas |

5. DECIBILIDAD
5.1 LENGUAJES DECIDIBLES
Un problema de decisión es aquel formulado por una pregunta (referida a alguna propiedad) que requiere una respuesta de tipo“si/no”.
 Un problema de decisión es:
* Soluble si existe un algoritmo total para determinar si la propiedad es verdadera (Existe una MT que siempre para al resolver el problema).
* Parcialmente soluble si existe un algoritmo parcial para determinar si la propiedad es verdadera (existe una MT que resuelve el problema, pero puede no parar).
* Insoluble si no existe un procedimientoefectivo para determinar si la propiedad es verdadera (no existe una MT),
 
Ejemplos de problemas de decisión:
 ¿Existe un algoritmo para decidir si un número natural cualquiera es par?
 Si es soluble.
 ¿Existe un algoritmo para decidir si dos autómatas finitos cualesquiera son equivalentes?
 Si es un problema soluble.
¿Es un número entero dado primo? Una instancia de este problema sería:¿Es 17 primo?
Si es un problema soluble
 ¿Existe un algoritmo para determinar si una gramática es ambigua o no?
 Es insoluble.
 Muchos problemas insolubles son paradójicos en su naturaleza. Ejemplo: la paradoja de Russell.
 Un peluquero afeita a todas las personas que no se afectan a sí mismas. El peluquero: ¿se afeita así mismo? (insoluble).
En teoría de la computación, un problema esun conjunto de frases de longitud finita que tienen asociadas frases resultantes también de longitud finita. Un problema de decisión es un problema en donde las respuestas posibles son SI o NO.
Un problema de decisión también se puede formalizar como el problema de decidir si una cierta frase pertenece a un conjunto dado de frases, también llamado lenguaje formal. El conjunto contieneexactamente las frases para las cuales la respuesta a la pregunta es positiva.
Si existe un algoritmo que pueda decidir para cada posible frase de entrada si esa frase pertenece al lenguaje, entonces se dice que el problema es decidible, de otra forma se dice que es un problema indecidible. Cuando existe un algoritmo que puede responder positivamente cuando la frase está en el lenguaje, pero que corre...