Decivilidad
Páginas: 18 (4494 palabras)
Publicado: 5 de marzo de 2010
Decivilidad
Se dice que un sistema formal es decidible si existe un algoritmo que diga en tiempo finito si una cadena cualquiera es un teorema o no lo es
El identificar los problemas que son computables y los que no lo son tiene un considerable interés, pues indica el alcance y los límites de la computabilidad, y así demuestra los límites teóricos de los ordenadores. Además de lascuestiones sobre algoritmos, se han encontrado numerosos problemas menos “generales” que han resultado ser no computables. La mayoría de las demostraciones de no computabilidad se basan en el método de la diagonal.
Como ejemplos de estos problemas podemos citar:
1.- El problema de la palabra para Grupos.- Dado un subconjunto S de elementos de un grupo G, se trata de decidir si una expresión compuestapor elementos de S y con las operaciones del grupo es igual al elemento neutro del grupo. Durante muchos años se buscaron ejemplos de grupos finitamente presentados para los que este problema fuese indecidible. La existencia de uno de estos grupos fué encontrada por Novikov en 1955 y por Boone en 1957. En el algebra moderna hay abundantes ejemplos de interesantes problemas no computables; una grancantidad de ellos sobre propiedades de palabras o generadores semejantes al problema de la palabra para grupos.
2.- Décimo problema de Hilbert. Una ecuación diofántica es la ecuación de los ceros enteros de un polinomio con coeficientes enteros. El décimo problema de Hilbert, propuesto en 1900, pregunta si hay un procedimiento efectivo que determine si una ecuación diofántica tiene o nosolución. Y. Matiyasevich demostró en 1970 que este problema no tiene solución.
5.1 Lenguajes Decidibles
Los lenguajes decidibles son cadenas de palabras calculables mediante funciones recursivas por lo cual también se les llamas lenguajes recursivos.
Un posible alfabeto sería, digamos, {a, b} , y una cadena cualquiera sobre este alfabeto sería, por ejemplo, ababba .
Un lenguaje sobre estealfabeto, que incluyera esta cadena, sería: el conjunto de todas las cadenas que contienen el mismo número de símbolos que , por ejemplo
La palabra vacía (esto es, la cadena de longitud cero) se permite en este tipo de lenguajes, notándose frecuentemente A diferencia de que ocurre con el alfabeto (que es un conjunto finito) y con cada palabra (que tiene una longitud también finita), un lenguajepuede estar compuesto por un número infinito de palabras.
Esos son algunos ejemplos de problemas de decisión expresados como lenguajes:
Las frases sobre el alfabeto {a, b} que contienen alternadas las letras a y b.
Las frases sobre el alfabeto {a, b, c} que contienen igual número de letras a y b.
Las frases que describen un grafo con aristas etiquetadas con números naturales queindican su longitud, dos vértices del grafo y un camino en el grafo que es el camino más corto entre esos dos vértices.
Las frases que describen una máquina de Turing y una cinta de entrada para esta máquina tal que la máquina se para en un tiempo finito al procesar esa entrada.
Existen problemas que no pueden ser resueltos por una computadora, dado que las computadoras solamente pueden ejecutaralgoritmos, esto es secuencia de instrucciones universalmente precisas y entendibles que resuelven cualquier instancia de problemas computacionales definidos rigurosamente.
No es una sorpresa que esta idea intuitiva de algoritmo pueda ser definida formalmente. El correspondiente modelo matemático se llama máquina de Turing (Alan Turing, 1936).
La teoría de computabilidad tiene como objetivoel estudio de problemas de decisión, con el fin de determinar si los mismos son teóricamente decidibles.
Los problemas se pueden clasificar desde el punto de vista de la teoría de computabilidad en resolubles y no resolubles. Los problemas resolubles son objeto de estudio de la teoría de complejidad computacional.
En el contexto de complejidad computacional, el interés está centrado en...
Se dice que un sistema formal es decidible si existe un algoritmo que diga en tiempo finito si una cadena cualquiera es un teorema o no lo es
El identificar los problemas que son computables y los que no lo son tiene un considerable interés, pues indica el alcance y los límites de la computabilidad, y así demuestra los límites teóricos de los ordenadores. Además de lascuestiones sobre algoritmos, se han encontrado numerosos problemas menos “generales” que han resultado ser no computables. La mayoría de las demostraciones de no computabilidad se basan en el método de la diagonal.
Como ejemplos de estos problemas podemos citar:
1.- El problema de la palabra para Grupos.- Dado un subconjunto S de elementos de un grupo G, se trata de decidir si una expresión compuestapor elementos de S y con las operaciones del grupo es igual al elemento neutro del grupo. Durante muchos años se buscaron ejemplos de grupos finitamente presentados para los que este problema fuese indecidible. La existencia de uno de estos grupos fué encontrada por Novikov en 1955 y por Boone en 1957. En el algebra moderna hay abundantes ejemplos de interesantes problemas no computables; una grancantidad de ellos sobre propiedades de palabras o generadores semejantes al problema de la palabra para grupos.
2.- Décimo problema de Hilbert. Una ecuación diofántica es la ecuación de los ceros enteros de un polinomio con coeficientes enteros. El décimo problema de Hilbert, propuesto en 1900, pregunta si hay un procedimiento efectivo que determine si una ecuación diofántica tiene o nosolución. Y. Matiyasevich demostró en 1970 que este problema no tiene solución.
5.1 Lenguajes Decidibles
Los lenguajes decidibles son cadenas de palabras calculables mediante funciones recursivas por lo cual también se les llamas lenguajes recursivos.
Un posible alfabeto sería, digamos, {a, b} , y una cadena cualquiera sobre este alfabeto sería, por ejemplo, ababba .
Un lenguaje sobre estealfabeto, que incluyera esta cadena, sería: el conjunto de todas las cadenas que contienen el mismo número de símbolos que , por ejemplo
La palabra vacía (esto es, la cadena de longitud cero) se permite en este tipo de lenguajes, notándose frecuentemente A diferencia de que ocurre con el alfabeto (que es un conjunto finito) y con cada palabra (que tiene una longitud también finita), un lenguajepuede estar compuesto por un número infinito de palabras.
Esos son algunos ejemplos de problemas de decisión expresados como lenguajes:
Las frases sobre el alfabeto {a, b} que contienen alternadas las letras a y b.
Las frases sobre el alfabeto {a, b, c} que contienen igual número de letras a y b.
Las frases que describen un grafo con aristas etiquetadas con números naturales queindican su longitud, dos vértices del grafo y un camino en el grafo que es el camino más corto entre esos dos vértices.
Las frases que describen una máquina de Turing y una cinta de entrada para esta máquina tal que la máquina se para en un tiempo finito al procesar esa entrada.
Existen problemas que no pueden ser resueltos por una computadora, dado que las computadoras solamente pueden ejecutaralgoritmos, esto es secuencia de instrucciones universalmente precisas y entendibles que resuelven cualquier instancia de problemas computacionales definidos rigurosamente.
No es una sorpresa que esta idea intuitiva de algoritmo pueda ser definida formalmente. El correspondiente modelo matemático se llama máquina de Turing (Alan Turing, 1936).
La teoría de computabilidad tiene como objetivoel estudio de problemas de decisión, con el fin de determinar si los mismos son teóricamente decidibles.
Los problemas se pueden clasificar desde el punto de vista de la teoría de computabilidad en resolubles y no resolubles. Los problemas resolubles son objeto de estudio de la teoría de complejidad computacional.
En el contexto de complejidad computacional, el interés está centrado en...
Leer documento completo
Regístrate para leer el documento completo.