CONCEPTOS FUNDAMENTALES DE TEORÍA DE LA COMPUTACIÓN

NATURALEZA Y VALOR DE LA TEORÍA COMPUTACIONAL

La teoría, actuando como un sistema de advertencia temprana, provee una ciencia de lo imposible –lo que no debe ser intentado porque no puede ser realizado–. Sin embargo, una buena teoría debe también proveer líneas directivas para lo posible: ... una guía debe no solo prevenirnos sobre las zonas peligrosas, sino también señalarnos las rutas simples, las rutas difíciles y las rutas extenuantes, por ejemplo. Encontramos que la teoría de la computación hace precisamente esto en niveles muy distintos. En el nivel más burdo, secciona los problemas en tres clases: (i) los problemas imposibles; (ii) los problemas posibles con recursos ilimitados pero imposibles con recursos limitados; y (iii) los problemas posibles con recursos limitados. En el caso de que el recurso sea el tiempo, se conocen comúnmente como los problemas indecidibles, los impracticables y los solucionables. En un nivel más fino la teoría también considera problemas que requieren, por ejemplo, tiempo linealmente proporcional a sus tamaños.... ( Wood 87, p. 53)

Para hacer un estudio teórico es necesario eliminar por abstracción muchos detalles y notas realistas de los sistemas mecánicos. Casi siempre nuestra abstracción es tan ruda que deja dentro de la máquina solamente una representación esquelética de la estructura de la secuencia de sucesos –una suerte de estructura "simbólica" o "informática"–. Pasamos por alto en nuestras abstracciones la composición geométrica o física de las partes mecánicas. Pasamos por alto cuestiones de energía. Incluso desmenuzamos el tiempo en una secuencia de momentos separados y desconectados, e ignoramos totalmente el mismo espacio. ¿Puede una teoría así ser una teoría de alguna "cosa" en absoluto? Increíblemente, sí puede serlo. Al eliminar por abstracción todo aquello que no tiene que ver con las consecuencias lógicas de ciertas clases de relaciones de causa-efecto, podemos concentrar nuestra atención aguda y claramente en unas pocas materias fundamentales. Una vez que hemos captado estas, podemos traer de nuevo al mundo práctico este entendimiento, que no podríamos haber nunca adquirido si hubiéramos permanecido inmersos en detalles y distracciones no esenciales. ( Minsky 67, pp. 2-3)

Existe un contraste curioso entre la idea de una máquina y la idea de una "teoría". Considérese una "teoría" de física, por ejemplo la mecánica de Newton. Esta teoría es supuestamente una generalización sobre algún aspecto del comportamiento de los objetos en el mundo físico. Si las predicciones que vienen de la teoría no se confirman, entonces (suponiendo que el experimento es impecable) la teoría debe ser criticada y modificada, como le pasó a la teoría de Newton cuando la evidencia de los fenómenos relativísticos y cuánticos llegó a ser conclusiva. Después de todo, no hay más que un universo y no es responsabilidad del físico censurarlo, aunque le gustara hacerlo. Para las máquinas, la situación se invierte. La idea abstracta de una máquina, por ejemplo la de sumar, es una especificación sobre cómo un objeto físico debe funcionar. Si la máquina que construyo se gasta, la censuro y quizá la arreglo. Al igual que en física, las partes y los estados del objeto físico se suponen corresponder a los del concepto abstracto. Pero en contraste con la situación de la física, criticamos la parte material del sistema cuando la correspondencia se pierde. ( Minsky 67, pp. 5-6)

COMPUTACIÓN Y ALGORITMO

La computación discreta consiste en la evaluación de funciones de un conjunto contable a otro, mientras que la computación analógica consiste en la evaluación de funciones de un conjunto incontable a otro....

Una función es simplemente una relación entre los miembros de un conjunto y aquellos de otro. Un algoritmo, por otra parte, es un procedimiento para evaluar una función.... Una función es y un algoritmo hace, o dice cómo hacer. Nótese que la relación entre funciones y algoritmos no es uno-a-uno. Muchos algoritmos diferentes pueden usarse para evaluar la misma función, y ... hay un sentido práctico en el cual algunas funciones no pueden ser evaluadas por ningún algoritmo.... ( Hennie 77, p. 1)

Una función es básicamente un conjunto de pares ordenados. Para ser más preciso, supongamos que X1, ..., Xn y Y son conjuntos específicos y que X denota el producto cartesiano X1 * X2 * ··· * Xn. Una función parcial de X a Y se define entonces como un subconjunto f de X1 * ··· * Xn tal que, por cada escogimiento de x1 en X1, ..., xn en Xn, existe a lo más un elemento y en Y para el cual ( x1, ..., xn, y) pertenece a f. Una función total de X a Y se define como un subconjunto f de X1 * ··· * Xn * Y tal que por cada escogimiento de x1 en X1, ..., xn en Xn hay exactamente un elemento y en Y para el cual ( x1, ..., xn, y) pertenece a f. En la medida que X es el producto de n conjuntos componentes, una función parcial o total de X a Y es comúnmente identificada como una función de n variables. ( Hennie 77, p. 2)

Un conjunto enumerable es aquel cuyos miembros pueden ... arreglarse en una lista única ... de tal manera que cada miembro del conjunto aparezca más tarde o más temprano en la lista....

...............

Podemos hablar de conjuntos enumerados por funciones o también por listas....

................

Decir que un conjunto A es enumerable es decir que existe una función todos cuyos argumentos son enteros positivos y todos cuyos valores son miembros de A, y que cada miembro de A es un valor de esta función....

................

Una función es una asignación de valores a argumentos. El conjunto de todos esos argumentos a los cuales la función asigna valores se llama dominio de la función. El conjunto de todos aquellos valores que la función asigna a sus argumentos se llama el rango de la función....

................

Ahora bien, un conjunto es enumerable si y solo si es el rango de una función de los enteros positivos.... ( Boolos 74, pp. 1-4)

Ciertas funciones no son computables, y ... ciertos conjuntos enumerables no son eficazmente (mecánicamente) enumerables incluso si las limitaciones físicas de tiempo, velocidad y cantidad de material pudieran de algún modo ser superada–. ( Boolos 74, pp. 19)

Una función eficazmente calculable es una noción intuitiva que identifica a aquellas funciones para las cuales existe un algoritmo que puede usarse para computar su valor. Si tal algoritmo existe, entonces podemos –por lo menos en principio– construir una máquina para realizar la tarea (computar el valor de la función). Tal mecanismo computacional debe entenderse como determinístico, en el sentido de que, una vez en operación, todo su futuro está completamente especificado por algún estado instantáneo y una entrada (este requisito elimina a los computadores analógicos o "aleatorios"). ( Davis 58, p. 3)

Un algoritmo especifica una ... manera mecanicista de evaluar una función. Esta evaluación debe llevarse a cabo por alguna suerte de agente computacional, que puede ser humano, mecánico, electrónico, o cualquier otra cosa....

Asociado con cada algoritmo existe un conjunto contable de objetos sobre los cuales el algoritmo opera de conformidad con su diseño, y entre los cuales deben estar incluidos los resultados producidos por el algoritmo..., el dominio del algoritmo en cuestión. Un dominio típico puede ser el conjunto de los números naturales ... o el conjunto de las hileras compuestas de ciertos caracteres alfanuméricos. Al comienzo de cualquier computación uno (o más) de los miembros del dominio es designado como argumento (o argumentos) al cual el algoritmo se aplica.

Un algoritmo por sí mismo consiste de una colección de instrucciones, cada una de las cuales especifica una operación básica que debe llevarse a efecto en uno o más miembros del dominio. A fin de que estas instrucciones se ejecuten apropiadamente, deben presentarse al agente computacional en una forma que pueda interpretar correctamente. Así, cada algoritmo debe estar representado por una descripción en un lenguaje adecuado.... Tanto la secuencia de operaciones para ejecutar como los objetos particulares a los cuales debe aplicarse cada operación deben estar bien definidos. Esta secuencia de operaciones y especificación de objetos debe ser determinada por el algoritmo, de conformidad con ciertas "reglas de operación" asociadas con el algoritmo y el agente computacional....

Las reglas de operación de algunos algoritmos pueden permitir la ejecución de una o más instrucciones en forma repetitiva, quizá hasta el infinito. Así, la computación prescrita por el algoritmo puede no terminar para ciertos argumentos que se escojan. Pero cuando una computación sí termina, ese hecho debe ser perfectamente obvio y el resultado de la computación debe estar bien definido. Aún más, este resultado debe depender solamente de los argumentos particulares a los cuales el algoritmo fue aplicado. En otras palabras, cada algoritmo debe determinar la computación de una función parcial en el dominio que le esté asociado....

En la computación práctica, es el agente computacional el que debe hacer la evaluación efectiva de la función en cuestión, no la persona que prepara el algoritmo. Así, debemos proscribir algoritmos que equivalgan a "consultas en tablas infinitas" en el sentido de que requieran que el programador determine e incluya en el algoritmo los valores de la función deseada para un infinito número de valores argumentales.... Debemos [también] restringir nuestra atención a los algoritmos que consistan en números finitos de instrucciones y por lo tanto sean representables por descripciones finitas, donde por una descripción finita significamos una colección finita de símbolos extraídos de un alfabeto contable.... Así, supondremos que cada uno de los algoritmos con los cuales lidiaremos puede ser descrito por una hilera finita de símbolos de un alfabeto contable. ( Hennie 77, pp. 7-10)

Se acepta de manera general que un algoritmo digno de este nombre debe satisfacer las siguientes condiciones elementales:

Estas cinco condiciones capturan la esencia de los programas y las computadoras por vía de los algoritmos y los agentes computacionales. Sin embargo ... hay un número de preguntas que todavía deben ser contestadas para poder usar esas condiciones como nuestra base para una teoría de la computación. La primera y quizá más importante es ¿debe un algoritmo parar o terminar en un número finito de pasos cada vez que lo alimentamos? Nuestra experiencia nos dice que debemos contestar esta pregunta con un sonoro sí. Sin embargo ... es esencial para la teoría de la computación permitir "algoritmos" que no terminan con todos los juegos de argumentos. Llamamos a estos algoritmos parciales.... ( Wood 87, pp. 56-57)

Mientras que la idea informal de un algoritmo es bastante vieja, las formulaciones cuidadosas de esta idea son todas relativamente recientes. No fue sino hasta los años mil novecientos treinta que el trabajo de Turing, Church y Post proveyó modelos formales satisfactorios para la noción de computación algorítmica y llevó a la definición de funciones computables. Estos modelos formales eran de naturaleza matemática, pero sirvieron para caracterizar las capacidades de las computaciones "físicas". Entonces, conforme los computadores digitales y los lenguajes de programación se desarrollaron, se hizo claro que las computaciones que pueden describirse por los lenguajes de programación de propósito general son precisamente aquellas representadas por los modelos anteriores más abstractos. Es esta relación entre programación y computabilidad lo que hace a la teoría de la computabilidad de interés directo para los informáticos.... La equivalencia entre las funciones programables y las funciones matemáticamente computables se desprende de ciertas notas comunes a todos los lenguajes de programación de propósito general.... (Hennie 77, pp. iii-iv)

¿Que significa decir que un proceso es mecánico? ¿Cuándo es un procedimiento tan completamente especificado que una máquina lo puede realizar?... ¿Existen procesos que pueden ser descritos precisamente y sin embargo no pueden realizarse a máquina?...

Cualquier cosa que puede hacerse por computadora puede ser descrita de manera precisa.... NOTA 2

Cualquier procedimiento que puede ser descrito con precisión puede ser programado para que lo realice una computadora.... NOTA 3

La primera frase es lo mismo que decir que un programa de computación puede servir como una descripción precisa del proceso que la máquina realizará. La verdad de la segunda frase depende de qué queramos decir por descripción precisa. (Minsky 67, pp. 103-104)

Un procedimiento eficaz es un procedimiento en que el próximo paso está siempre claramente determinado. Si un procedimiento puede llevarse a efecto por una máquina simple, entonces podemos estar seguros de que la especificación es completa y de que el procedimiento es "eficaz". Pero también podemos afirmar (aunque no probar) que cualquier procedimiento que parezca intuitivamente eficaz puede realizarse mediante una máquina simple. ( Minsky 67, p. 105)

Uno no puede siempre encontrar un equivalente formal simple y completamente satisfactorio para una noción intuitiva compleja. ( Minsky 67, p. 106)

Podemos comenzar a definir un procedimiento eficaz como un conjunto de reglas que nos dicen, de momento a momento, cómo proceder. Pero la interpretación de las reglas puede variar de un agente a otro: si su inteligencia es pequeña, puede no entender lo que queremos decir; si por el contrario su inteligencia es muy grande, puede inventar una nueva interpretación que no pretendíamos. Una formulación más conveniente sería definir un lenguaje para las reglas de comportamiento y construir una máquina para interpretar los enunciados del lenguaje. Curiosamente, ciertos lenguajes y máquinas muy simples pueden manejar los procedimientos eficaces, con tal de que haya suficiente memoria disponible. ( Minsky 67, p. 106)

COMPUTABILIDAD

En 1928 se había publicado un pequeño texto de lógica de Hilbert y Ackermann.... El libro enfatizaba la lógica de primer orden.... Los autores mostraron cómo las varias partes de las matemáticas podían ser formalizadas dentro de la lógica de primer orden y daban un conjunto sencillo de reglas de prueba para hacer las inferencias lógicas. Hacían notar que toda inferencia que podía ser realizada de acuerdo con las reglas de prueba era también válida, en el sentido de que en una estructura matemática en que todas las premisas son verdaderas, la conclusión es también verdadera.... Un problema levantado por Hilbert y Ackermann en su tratado era el problema decisorio, el problema de encontrar un algoritmo que determine si una inferencia propuesta determinada es válida.... Este problema es equivalente a buscar un algoritmo para determinar si una conclusión particular puede derivarse de ciertas premisas usando las reglas de prueba Hilbert- Ackermann. El problema decisorio fue llamado "el principal problema de la lógica matemática", porque un algoritmo para el problema decisorio podría, en principio, ser usado para contestar cualquier pregunta matemática: sería suficiente emplear una formulación en lógica de primer orden de la rama de las matemáticas pertinente a la cuestión bajo consideración. La atención de Alan Turing fue atraída hacia el problema decisorio ... y pronto vio cómo resolver el problema en la negativa. Esto es, Turing mostró que no hay algoritmo alguno para resolver el problema decisorio. Las herramientas que Turing desarrolló para este propósito han resultado ser absolutamente fundamentales para la informática.

Si una solución positiva al problema decisorio llevaría a algoritmos para resolver todas las cuestiones matemáticas, entonces se sigue que si existe incluso un solo problema que no tiene solución algorítmica, entonces el mismo problema decisorio no puede tener solución algorítmica. Ahora bien, la noción intuitiva de algoritmo sirve perfectamente bien cuando lo que necesitamos verificar es que algún procedimiento propuesto de verdad constituye una solución positiva a un problema dado. Sin embargo, si permanecemos en este nivel intuitivo, no podríamos esperar probar que algún problema no tiene solución algorítmica. Para estar seguros de que ningún algoritmo funcionará, parece necesario hacer un reconocimiento de la clase de todos los algoritmos posibles. Esa es la tarea que se impuso Turing. Comenzó con un ser humano, quien realizaría los pasos sucesivos requeridos por algún algoritmo; esto es, Turing propuso considerar el comportamiento de un "computador". Aquí la palabra computador se refiere a una persona que realiza una computación; así era como Turing (y todo el mundo) usaba la palabra en 1935. Turing procedió por una secuencia de simplificaciones, cada una de las cuales podía verse que no planteaba ninguna diferencia esencial, para obtener su caracterización de computabilidad. ( Davis 58, pp. 153-154)

La teoría de la computabilidad y la no computabilidad es usualmente llamada la teoría de las funciones recursivas. Esta materia concierne la existencia de procedimientos puramente mecánicos para resolver varios problemas. Aunque la teoría es una rama de las matemáticas puras, es, por su pertinencia en relación con ciertas cuestiones filosóficas y la teoría de los computadores digitales, de interés potencial para los no matemáticos. La existencia de problemas absolutamente insolubles y el teorema de la incompletabilidad de Gödel están entre los resultados en teoría de la computabilidad que tienen significación filosófica. La existencia de máquinas universales de Turing, otro resultado de la teoría, confirma la creencia de aquellos que trabajan con computadoras digitales de que es posible construir un computador digital de propósito general en el cual se pueda programar (dentro de limitaciones de tiempo y memoria) cualquier problema que pudiera programarse para cualquier computador digital determinístico concebible. Este aserto se oye a veces en su forma reforzada: cualquier cosa que puede hacerse completamente precisa puede ser programada para una computadora digital de propósito general. Sin embargo, en esta forma el aserto es falso..... ( Davis 58, p. viii)

La gran importancia del concepto de recursividad general (o computabilidad de Turing) ... [es que] con este concepto se ha tenido éxito por primera vez en dar una definición absoluta de una noción epistemológica importante, a saber sin dependencia de un formalismo determinado.... ( Gödel 46, p. 84)

La creciente percepción de que una solución al problema decisorio produciría un procedimiento para solucionar muchos (si no todos) los problemas matemáticos significó que algunos matemáticos, especialmente von Neumann, se convencieran de que no podía haber tal solución; una creencia que llegó a ser casi una certidumbre cuando Gödel publicó [su famoso artículo en] 1931. Para fundar esa certidumbre, sin embargo, era esencial poner límites precisos a "eficazmente calculable". Esto (combinado con un interés natural por el cálculo mecánico) era lo que estaba en la atmósfera que Turing respiraba.... Turing mostró que el cálculo puede descomponerse en la iteración (controlada por un "programa") de operaciones concretas extremadamente simples; tan concretas que pueden fácilmente ser descritas en términos de mecanismos (físicos).... ( Gandy 88, pp. 100-101)

La computabilidad Turing fue una de tres maneras equivalentes de caracterizar exactamente las funciones para las cuales existen algoritmos que aparecieron en los años mil novecientos treinta. Los conceptos usados en las otras dos fueron la definibilidad lambda de Church-Kleene (desarrollada en la Universidad de Princeton en 1932 y 1933) y la recursividad general de Herbrand-Gödel (presentada por Gödel en sus conferencias de 1934 en el Instituto de Estudios Avanzados en Princeton). Su equivalencia la estableció Kleene en 1936....

PROCEDIMIENTO DECISORIO

En general, el problema decisorio para una propiedad es soluble si existe una prueba mecánica (= una rutina computacional, un procedimiento eficaz) que, aplicado a cualquier objeto de la suerte apropiada, eventualmente clasifica ese objeto correctamente como un caso positivo o negativo de tal propiedad ("eventualmente" significa aquí "después de un número finito de pasos"). Una prueba positiva para una propiedad es una prueba mecánica que eventualmente clasifica como positivos todos y solo sus casos positivos. Una prueba negativa es aquella que eventualmente clasifica como negativos todos y solo los casos negativos. Si ambas pruebas, positiva y negativa, para la propiedad existen, entonces y solo entonces el problema decisorio para tal propiedad es soluble; siendo así que cualquier objeto apropiado será o bien un caso positivo o un caso negativo, si uno está equipado con ambas clases de prueba, puede aplicar ambas al objeto dividiendo el tiempo de modo que se alternen los pasos de las dos pruebas y así, eventualmente, descubriremos qué clase de caso es el objeto (conversamente, cualquier prueba que clasifica eventualmente en forma correcta cualquier objeto o bien como caso positivo o bien como caso negativo cuenta como una prueba positiva y negativa). Aquí las propiedades que nos interesan son validez y satisfabilidad, y los "objetos de la suerte apropiada" son enunciados en la notación de la lógica de primer orden.... ( Boolos 74, p. 115)

El problema del procedimiento decisorio ... fue propuesto en los años veinte como el de encontrar un procedimiento algorítmico general para resolver todas las cuestiones matemáticas, y por ese medio declarar el concepto de verdad matemática como idéntico al de prueba o axiomaticidad. Este programa de investigación sufrió un golpe fatal tan temprano como 1931, cuando Kurt Gödel probó su célebre teorema sobre la incompletabilidad de la aritmética.

En este contexto, los algoritmos son concebidos como procedimientos computacionales eficaces para resolver problemas, a saber, conjuntos de instrucciones que proveen vías mecánicas por medio de las cuales contestar cualquiera de una clase de preguntas. Tales instrucciones son concebidas como que no requieren pensamiento "creativo" en su ejecución, puesto que, en principio, es siempre posible construir una máquina para llevar a efecto un conjunto de instrucciones o preparar un programa por medio del cual alguna computadora digital del tamaño adecuado pueda llevarlas a cabo. ( Davis 58, p. xv)

En el teorema de la incompletitud de Gödel, se asocian números a los enunciados y los enunciados sobre otros enunciados se traducen a enunciados sobre números. Se pueden decir cosas como esta: "el enunciado del sistema S cuyo número es n no puede probarse en el sistema S", lo cual es un enunciado sobre el número n. Ahora bien, puede mostrarse que existe un número k tal que el significado del enunciado cuyo número es k resulta ser "el enunciado cuyo número es k carece de prueba en el sistema S". Así pues, hemos obtenido un enunciado verdadero pero que no puede probarse.... ( Cohen 87, p. 18)

Podemos dar una caracterización matemática de una clase de objetos como "máquinas Turing". Podemos también caracterizar matemáticamente una clase de funciones numéricas, las funciones computadas por las máquinas Turing: son las llamadas funciones computables, y se propone que se identifican con el concepto intuitivo de funciones efi- cazmente calculables que en esta forma adquiere una definición precisa. ( Davis 58, p. 3)

Una función parcialmente computable puede ser pensada como la que posee un algoritmo que nos permite computar su valor para elementos de su dominio, pero que nos tendrá computando eternamente si intentamos obtener un valor funcional para un elemento que no está en su dominio, sin asegurarnos nunca que no obtendremos un valor. En otras palabras, cuando es posible una respuesta, el algoritmo la provee; cuando no es posible, el algoritmo nos mantiene buscando la respuesta en vano por un tiempo infinito.... ( Davis 58, p. 10)

La situación [de la identificación de calculabilidad eficaz con computabilidad] es análoga a la de sustituir un concepto vago, con potente atractivo intuitivo, por un concepto matemático exacto.... En tal caso no tiene sentido, por supuesto, pedir una prueba matemática de la equivalencia de los dos conceptos; la misma vaguedad del concepto intuitivo lo impide. Sin embargo, es posible presentar argumentos con poderoso atractivo intuitivo, que tienden a hacer la identificación sumamente razonable. (Davis 58, p. 10)

Diferentes personas hicieron propuestas más o menos al mismo tiempo (1936), independientemente unas de otras, para identificar el concepto de función eficazmente calculable con varios conceptos precisos. En esta conexión vale la pena mencionar la noción de definibilidad lambda de Church, la noción de recursividad general de Herbrand-Gödel-Kleene, la noción de computabilidad de Turing..., la noción de definibilidad-1 de Post.... Se demostró que todas estas nociones son equivalentes.... (Davis 58, p. 10)

Esto agregó mucha fuerza al punto de vista, que llegó a conocerse como la Tesis Church-Turing, de que la máquina Turing (o su equivalente) de hecho define lo que, matemáticamente, entendemos por un procedimiento algorítmico (o eficaz o recursivo o mecánico).... (Penrose 89, p. 49)

NOTA 1 Esta selección contiene párrafos escogidos de varios autores, ordenados de manera que su lectura resulte lo más comprensible posible. Las referencias indican el nombre del autor, año de publicación de su obra y el número de la(s) página(s) de donde el párrafo se ha tomado. La referencia completa debe consultarse en la bibliografía . Nota del editor.

NOTA 2 Esto es un teorema, demostrado por Turing. Nota del editor.

NOTA 3 Esto es una conjetura, llamada Tesis de Church/Turing. Nota del editor.