indecidivilidad

UNIVERSIDAD NACIONAL AUTONOMA DE MEXICO
FACULTAD DE ESTUDIOS SUPERIORES ARAGON
INGENIERIA EN COMPUTACION

ALUMNO:


NUMERO DE CUENTA:


MATERIA: LENGUAJES FORMALES Y AUTOMATAS


MAESTRO:JUAREZ ROBLES ELIZABETH


GRUPO: 1557


TITULO: INVESTIGACION SOBRE INDECIDIBILIDAD





La indecidibilidad es una imposibilidad de demostrar, en un sistema de una cierta complejidad y dentrodel mismo sistema, todas las proposiciones verdaderas.
En teoría de la computabilidad y en teoría de la complejidad computacional, un problema indecidible es un problema de decisión para el cuales imposible construir un único algoritmo que siempre conduzca a una respuesta de sí o no correcta.
Un problema de decisión es cualquier pregunta arbitraria de sí o no en un conjunto infinitode entradas. Por ello es tradicional definir el problema de decisión como equivalente al conjunto de entradas para las que el problema retorna sí. Estas entradas pueden ser números naturales, obien valores de otro tipo, tales como cadenas de un lenguaje formal.
Mediante alguna codificación, tal como una numeración de Gödel, las cadenas se pueden codificar como números naturales. Así,un problema de decisión informalmente expresado en términos de un lenguaje formal es también equivalente a un conjunto de números naturales. Para mantener simple la definición formal, seexpresa en términos de subconjuntos de los números naturales.
Formalmente, un problema de decisión es un subconjunto de los números naturales. El problema informal correspondiente consiste endecidir si un número dado está en el conjunto. A un problema de decisión A, si A es un conjunto recursivo, se le denomina decidible, o efectivamente solucionable. Si A es un conjunto recursivamenteenumerable, el problema es parcialmente decidible, semidecidible, solucionable, o demostrable. A problemas parcialmente decidibles y a los no decidibles se les califica de indecidibles.