Discusión:Función computable

ernalve 13:49 30 ago 2006 (CEST)Este artículo tiene su página en español, y bastante completo parece, en la WP en inglés:

lo paso para acá antes de que allá lo borren, — El comentario anterior sin firmar es obra de Ernalve (disc. • contribs • bloq). 09:53 8 ago 2006

---

No entiendo lo que dice más arriba ¿Cómo va a ser que en la Wikipedia en inglés tengan un artículo en español? Busqué en la Wikipedia en inglés y todo lo que encontré estaba en inglés. En todo caso la versión que hay aquí tiene gramática y redacción razonables, no como la terrible traducción que había en el artículo propiamente tal.

Pablo.cl 06:07 30 ago 2006 (CEST)

es raro pero allí estaba el artículo, incluso en la WP en inglés tienen un portal para traducir los artículos que les aparecen en otros idiomas, entonces lo que hice al verlo más largo que el nuestro, lo pasé para acá. Como el contenido del artículo par mi es lo mismo que leer chino, no sé si tiene info complementaria o no. Si no sirve simplemente eliminemos lo transcripto y ya está. Saludos, ernalve 13:49 30 ago 2006 (CEST)

Introducción

En la teoría de la computabilidad, las funciones Turing-computables o funciones computables son, según la tesis de Church-Turing, aquellas funciones que se pueden calcular utilizando una máquina de calculo. Esta noción puede ser relativizada a cualquier conjunto A de números naturales, o equivalente a una función cualquiera f de los números naturales a los números naturales, por medio de máquinas de Turing extendidas. Estas funciones pueden ser llamadas A-computables o f-computables respectivamente. Antiguamente se usaba en muchas ocasiones el término efectivamente computable.

Las funciones computables se usan para discutir sobre computabilidad sin tener que referirse a ningún modelo de computación en concreto, como la máquina de Turing o la máquina de registros. En este apartado, se pueden utilizar los axiomas de Blum para definir una teoría de complejidad computacional sobre el conjunto de las funciones computables. Según la tesis Church-Turing, la clase de las funciones computables es equivalente a la clase de las funciones definidas por funciones recursivas, calculo de λ (lambda), o algoritmos de Markov.

De forma alternativa se pueden definir como los algoritmos que pueden ser calculados por máquina de Turing, sístema de Post, o máquina de registros. En teoría de la complejidad computacional, el problema de determinar la complejidad de una función computable se conoce como un problema de funciones.

Definición

Una función parcial

f:⊆ N → N

se llama computable si el gráfico de f es un conjunto recursivamente enumerable. El conjunto de funciones parcialmente computables con un parámetro normalmente se escribe P¹ o P.

Una función total

f: N → N

se llama computable si el gráfico de f es un conjunto recursivo. El conjunto de funciones totalmente computables con un parámetro se escribe normalmente R¹ o R .

Una función computable f se llama predicado computable si los valores de la función son booleanos, o sea

f: N → {0,1}

Sobre la Teoría de la Computabilidad

El objetivo era concretar la noción de función calculable, esto quiere decir, una función/expresión cuyos valores se pueden calcular de forma automática a partir de un algoritmo. Surge así una teoría que producirá resultados positivos y negativos (resultados de no computabilidad o de indecibilidad). La teoría de la computabilidad se puede caracterizarc por la búsqueda de respuestas a las siguientes cuestiones:

1) ¿Qué pueden hacer los PC´s actuales sin limitaciones de espacio,tiempo o dinero? 
2) ¿Cuales son estas limitaciones relacionadas con el cálculo?

Los comienzos de la Teoría

Para resolver las anteriores cuestiones, se realizaron los estudios de ciertos modelos de computacion, los cuales, nos darán el concepto de algoritmo. Estos estudios son a principios del siglo 20 y fueron realizados , entre otros, por Post, Church, Turing, Kleene y Gödel. Estos trabajos han influido profundamente en el desarrollo de la Computación tanto en aspectos teóricos como en aspectos prácticos, como pueden ser la posibilidad de interpretar programas, la existencia de ordenadores de propósito general, la representación de lenguajes mediante estructuras formales basados en reglas de producción y la dualidad entre hardware y software.

El primer hecho que manifiesta estos trabajos fueron las cuestiones fundamentales de David Hilbert:

1.- ¿Son consistentes las matemáticas?
2.- ¿Un método definido se puede aplicar a cualquier afirmación matemática, y que determine si dicha afirmación es cierta?
3.- ¿Son completas las matemáticas, en el sentido de que pueda probarse o no cada aseveración
matemática? 

Las formuló en 1928.

Hilbert no quería otra cosa que la de crear un sistema matemático formal "consistente" y "completo" donde todas las aseveraciones se pudieran plantear con precisión. Su objetivo era encontrar un "algoritmo" que permitiera determinar lo cierto o lo falso de una proposición cualquiera en un sistema formal. A este problema él le llamó el `Entscheidungsproblem'. Si Hilbert hubiera cumplido su objetivo, un problema cualquiera que hubiera estado bien especificado, se resolvería con la ejecución de dicho algoritmo.

En la década de los años 30 se demostró que esto era imposible tras el surgimiento en 1931 del Teorema de Incompletitud de Godel.

Biografías

Alonzo Church

Nació en Washington el año 1903. También fue profesor de Kleene y compañero docente de Von Neumann. Junto a Turing demostró que el cálculo Lambda y la máquina universal de Turing eran equipolentes. A raíz de eso demostraron que una gran variedad de procesos mecánicos de computación también tenían la misma potencia. Este resultado llevó a la tesis conocida como de Church-Turing. Murió el año 1995 en Hudson.

Alan Mathison Turing

Nació en Londres en 1912. Matemático británico, tras su graduación, se trasladó a la Universidad estadounidense de Princeton, donde trabajó con el lógico A. Church. En 1937 publicó un célebre artículo en el que definía una máquina de cálculo de capacidad infinita (máquina de Turing) que operaba utilizando un conjunto de instrucciones lógicas, ofreciendo las bases de lo que se conoce como algoritmo. De esta forma, Turing describió utilizando términos matemáticos precisos la forma en que un sistema automático, utilizando una serie de reglas simples, puede realizar toda clase de operaciones matemáticas expresandolas en un lenguaje formal.

Definió además un método teórico para decidir si una máquina era capaz de pensar como un hombre (test de Turing) y realizó contribuciones a otras ramas de la matemática aplicada, como la aplicación de métodos analíticos y mecánicos al problema biológico de la morfogénesis.

Murió el año 1054 en Wilmslow, Reino Unido.

David Hilbert

Nació en 1862 en Kalingrado, Rusia. Catedrático de matemáticas en la Universidad de Gottingen. En el año 1888 probó su famoso “Teorema da la Base”. Los trabajos posteriores de Hilbert influyeron de forma notable en la Geometría. Hilbert recibió muchos honores a lo largo de su vida profesional, por ejemplo, en 1905, la Academia de Ciencias de Hungría le rindió homenaje. El lema de Hilbert fue: “Nosotros debemos conocer, nosotros conoceremos”. En 1928 formuló las cuestiones fundamentales que supusieron el punto de partida de los primeros trabajos para la teoría computacional.

Murió el 14 de Febrero de 1943 en Gottingen, Alemania.

Kurt Gödel

Nació en Brno, Moravia, en 1906. Lógico y matemático. Con la segunda guerra mundial se marchó a EEUU donde ejerció de profesor. En 1931 publicó el artículo «Acerca de proposiciones formalmente indecidibles del Principia Mathematica y sistemas relacionados», en el cual propuso dos teoremas de la incompletitud:

Primero: establece que no hay teoría finitamente axiomatizable con capacidad de derivar los postulados de Peano (es decir, abarca un nivel de complejidad mínimo) que sea a la vez completa y consistente. De otra forma, si se elabora una teoría fundacional que establezca los axiomas y reglas de inferencia asociadas, de modo que sea posible decir con precisión qué no es y qué es un axioma, la teoría resultante no permitirá derivar los postulados de Peano (insuficiente), existirá como mínemo una proposición matemática válida que no va a ser derivable de la teoría (incompleta) o inconsistente.

Segundo: (corolario del primero) asegura que si una teoría es finitamente consistente, axiomatizable y capaz de derivar los postulados de Peano, entonces esta teoría no va a poder probar su propia consistencia.

Murió en Princeton, EE UU, 1978.

Stephen Kleene

Nació en 1909 en Estados Unidos. Stephen Kleene fue uno de los más brillantes lógicos matemáticos de este siglo. Su principal área de estudio se centró en la teoría de los algoritmos y las funciones recursivas. Fue el principal creador de la teoría de funciones recursivas. Sus aproximaciones confluyeron con otras equivalentes pertenecientes a Gödel, Post,Church, Turing y Roser. Todas pretendian fundamentar matemáticamente la idea de computabilidad. El conocimiento del universo de las funciones recursivas se debe en gran medida a los esfuerzos prolongados de Kleene. La labor más importante de Kleene, en lo que a teoria de la computabilidad ser refiere, consiste en una definición sencilla y fundamental de las funciones recursivas que ayudaron a una mejor comprensión de los sistemas axiomáticos de primer orden de Gödel. Sus resultados más notables permitieron establecer qué funciones podían ser computables y también permitieron establecer grados en las funciones no computables. Murió en 1994 en EEUU.

Evolución Histórica

Los primeros trabajos acerca de la Teoría de la Computación corrieron a cargo de David Hilbert. Hilbert pretendía hallar un algoritmo que indicara la veracidad o falsedad de una proposición cualquiera en un sistema matemático formal. Con este algoritmo podrían resolverse todos los problema bien definidos simplemente ejecutándolo. La idea de Hilbert se resumía en que una vez encontrados los axiomas adecuados, todas las verdades podrían ser deducidas a partir de ellos, mediante la lógica y la paciencia. Sin embargo, en la década de 1930 se produjeron varias investigaciones que demostraron que el entscheidungsproblem no es computable. Es decir, no existe algún algoritmo del tipo que buscaba Hilbert. El descubrimiento salió a la luz en 1931 cuando Kurt Gödel publicó su ahora famoso <<Teorema de la Incompletitud>>

Hilbert había inventado un lenguaje artificial de la lógica y comenzó a trasladar las afirmaciones de la teoría de números dentro de él. Su propósito era construir sistemas formales completos para las principales teorías de la matemática clásica. Completos en el sentido de que cualquier afirmación puede o bien ser demostrada o bien ser demostrada su negación. El programa de Hilbert también requería que se demostrara la consistencia de dichos sistemas formales.

Teorema de Incompletitud Gödel

El Teorema de Incompletitud es bastante sencillo de entender una vez hemos introducido la paradoja del mentiroso que se basa en la siguiente frase: "Esta afirmación es falsa." . Si ésta es verdadera, esto significa que la afirmación es falsa, lo cual contradice nuestra primera hipótesis. Por otra parte, si la afirmación es falsa, la afirmación debe de ser verdadera, lo cual nos lleva de nuevo a una contradicción. Gödel hizo manipulaciones para trasladar el lenguaje natural del mentiroso al lenguaje de las matemáticas. Lo que probó es comparable a la afirmación "Este teorema no tiene demostración". Lo sorprendente es que él probó el teorema. Diseñó su propio lenguaje lógico para esto. En definitiva, descubrió que existían afirmaciones verdaderas que no podían ser probadas dentro del sistema. Gödel probó que todo sistema formal que contuviera a la aritmética elemental (un ejemplo de este sistema serían las Matemáticas como un todo) es incompleto, es decir, Gödel demostró que no todas las verdades matemáticas pueden ser alcanzadas. Más sencillamente, que en cualquier sistema que contenga la aritmética, existe por lo menos una fórmula, que, aún siendo verdadera, no podrá jamás ser demostrada. No importa cuál sea el conjunto de axiomas que se use: siempre habrá algo, que, si bien es verdadero, no se puede demostrar. Es decir, en el seno mismo de las matemáticas, hay cosas no alcanzables, lugares adonde la paciente deducción no llegará jamás. Naturalmente, este curioso resultado, no afecta para nada a la utilización de las matemáticas por el resto de los científicos, ni al papel central que ésta juega en todo el sistema de las ciencias, pero de alguna manera, limita su omnipotencia.

El teorema de incompletitud de Gödel dice lo siguiente. 
"Todo sistema de primer orden consistente que contenga los teoremas de la aritmética
 y cuyo conjunto de (números de Gödel de) axiomas sea recursivo no es completo."
 
 (Este texto ha sido tomado de http://decsai.ugr.es/~castro/MCII/node3.html)

Gödel crea una expresión satisfacible pero que no puede ser comprobada en nuestro sistema. ¿Los sistemas de primer orden van dando paso a sistemas más potentes?.

Una nueva versión del teorema eliminó esta posibilidad haciendolo más general:

"Ningún sistema deductivo que contenga los teoremas de la aritmética, y con 
los axiomas recursivamente enumerables puede ser consistente y completo a la vez."

(Este texto ha sido tomado de http://decsai.ugr.es/~castro/MCII/node3.html)

El siguiente paso importante lo constituye la aparición casi simultanea en 1936 de los trabajos de Church, Kleene, Turing y Post. Éstos y muchos otros encontraron más problemas que carecían de solución algorítmica. Tal vez la característica más notable de estos primeros resultados sobre problemas que no pueden resolverse por medio de las computadoras es que se obtuvieron en la década de 1930 antes de que se hubieran construido las primeras computadoras.

Clausura de Kleene

Stephen Kleene introdujo de la Clausura de Kleene en lógica matemática y en ciencias de la computación.

En lógica matemática y en ciencias de la computación, la clausura de Kleene es una operación unaria que se aplica sobre un conjunto de cadenas de caracteres o un conjunto de símbolos o caracteres (alfabeto). La aplicación de la clausura de Kleene a un conjunto V se denota como V*. Es muy usada en expresiones regulares para caracterizar un cierto autómata.

A continuación definimos la clausula de Kleene:

Tesis de Church-Turing

Introducción a la tesis de Church-Turing

La teoría de la computabilidad se preguntaba una serie de cuestiones. Estas son:

1.¿Partiendo de la maquina de Rutin, qué problemas puede resolver? 
2.¿Que otros formalismos equivalen a las máquinas de Turing? 
3.¿Qué problemas requieren máquinas más o menos poderosas? 

Al finalizar esta tesis, todas ellas tendrán respuesta.

Procesos computacionales y recursos

Un proceso computacional, también llamado proceso algorítmico o algoritmo, es fundamental para la ciencia de la Computación, puesto que un computador no puede ejecutar un problema que no tenga una solución algorítmica. Así, cualquier limitación de las capacidades de los procesos computacionales constituye también una limitación de las capacidades de la computadora.

La Teoría de la Complejidad Computacional es la parte de la teoría de la computación que estudia los recursos requeridos durante el cálculo para resolver un problema. El estudio de los procesos computacionales, conduce a una clasificación de los problemas en dos grandes clases: los problemas con solución y los problemas sin solución. Los problemas solucionables, requieren gran cantidad de recursos como tiempo y espacio de almacenamiento.

Así, nos preguntamos si el lenguaje no permite escribir un algoritmo o es que no existe un algoritmo que pudiera calcular dicha función. Del mismo modo, podría ser que una función tuviera solución algorítmica pero debido a los recursos de la computadora no pudiera solucionarlo. Así, se va a tomar como base una computadora fija como es la Máquina de Turing.

La Tesis de Church-Turing

Sobre 1936, Church, tras varios años de investigaciones, demuestra la igualdad entre las funciones "landa definibles" y las "funciones recursivas de Herbrand-Gödel". De este modo, hace preveer que estas serían sus funciones solucionables a partir de su tesis.

Tesis de Church: "La clase de las funciones que pueden ser calculadas mediante 
un algoritmo coincide con la clase de las funciones recursivas."

(Este texto ha sido tomado de http://decsai.ugr.es/~castro/MCII/node3.html)

Además, demostró ejemplos de problemas no solucionables.

Turing dijo que el Entscheidungsproblem de Hilbert podía verse con la ayuda de una máquina (en su concepto abstracto). El objetivo de Turing era reducir el número de cálculos, mostrando de una forma sencilla una sere de procedimientos.

Turing caracterizó de un modo preciso, y a través de sus máquinas, el conjunto de funciones calculables utilizando un algoritmo, lo que se conoce como:

Tesis de Turing: 
"La clase de las funciones que pueden ser calculadas mediante un método definido 
coincide con la clase de las funciones calculables mediante una Máquina de Turing."

(Este texto ha sido tomado de http://decsai.ugr.es/~castro/MCII/node3.html)

("Consideremos una clase que contiene todas las funciones computables. Una función es computable si existe un algoritmo para ella, sin importar como pueda implantarse o expresarse ese algoritmo. Puede construirse un conjunto que contenga todas las funciones computables, para ello se utiliza un método muy usado por los matemáticos, el método recursivo generacional. Este método permite que a partir de un conjunto básico de funciones computables, consideradas como funciones iniciales, puedan construirse las demás combinándolas en forma recursiva mediante composición de funciones y así obtener el conjunto mayor de todas las funciones computables.")

Aunque no puede darse ninguna prueba formal de que una máquina pueda poseer esa propiedad, Turing ofreció una gran cantidad de argumentos a su favor y basandose en ellos presentó su tesis como un teorema demostrado.

Turing desconocía los trabajos de Church-Kleene, sin embargo durante la revisión le añadió un apéndice con el que se demostraba que los conceptos función -definible y función calculable mediante una máquina de Turing coinciden. Teniendo en cuenta ésto, la Tesis de Turing equivale a la de Church.

La Tesis de Church-Turing es aceptada como un axioma en la teoría de la computación, postulado que ha servido como punto de partida para la investigación de los problemas que se pueden resolver mediante un algoritmo.

Máquina de Turing

La noción de máquina de Turing es una idealización matemática útil para probar que ciertas tareas no son automatizables o que ciertas funciones no son computables. Una máquina de Turing es como un computador digital, pero sin limitaciones de capacidad de memoria ni de tiempo de ejecución. Una función es computable si y sólo si hay una máquina de Turing que la computa: si le damos uno o varios argumentos como input, la máquina ejecuta una serie finita de pasos programados e imprime como output el valor de la función para esos argumentos. Es decir, una máquina universal de Turing U es una máquina de Turing capaz de simular el comportamiento de cualquier otra máquina de Turing M en el sentido de que, si introducimos en U como input la tabla de M (digamos, m) y el argumento x, entonces U(m,x) = M(x) para cualquier x, es decir, U produce como output el mismo resultado que M (y eso ocurre con cualquier máquina M).

Las máquinas de Turing constituyen una herramienta de verificación. Por esa razón, las limitaciones corresponderían a los procesos computacionales y no a la tecnología

Respuestas a la teoría de la computabilidad

La técnica utilizada por Church y Turing para encontrar problemas sin solución es considerar a las entradas de los algoritmos (que eran números naturales) como algoritmos. Así, ha dado lugar a muy fructíferos resultados en cuestiones generales acerca de los algoritmos.

¿Que problemas puede resolver una máquina de Turing?

Sabemos que no todos los problemas tienen solución. Un problema no tiene solucion cuando, aún disponiendo de espacio y tiempo ilimitado,no puede ser resuelto por un algoritmoo. Actualmente se conocen muchos problemas indecidibles, como por ejemplo:

o El Entscheidungsproblem de hilbert

o El Problema de la parada. Esto es, decidir si un programa acaba o se "queda pillado" sabiendo la entrada al mismo.

o El número de Chaitin no es computable.

o 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 compuesta