Mis autores favoritos (David Deutsch, Roger Penrose y Douglas Hofstadter) profundizan en la Tesis de Teoría Computacional de Church-Turing y, lo que es más importante, en su interpretación más fuerte: El Principio de Turing. En este post, primero explicaré la Tesis de Church-Turing en términos laicos.
Cuando estaba trabajando en mi licenciatura en ciencias de la computación, estudié máquinas de Turing y la Tesis de Church-Turing en mi clase de Introducción a la Teoría Computacional. En ese entonces pensé que era una gran pérdida de tiempo. Solo quería programar computadoras y no podía importarme menos este tipo de Turing muerto hace mucho tiempo (ni este tipo de la Iglesia) ni sus estúpidas máquinas teóricas.
Ahora que entiendo las ramificaciones filosóficas de la Tesis de Church-Turing, ¡Desearía haber prestado atención en clase! Porque la Tesis de la Iglesia-Turing, si es cierta, tiene algunas ramificaciones filosóficas profundas y también podría decirnos algo sobre la naturaleza profunda y especial de la realidad.
Autómatas Finitos
Todos los textos y clases de Teoría de la Computación comienzan con algo llamado «Autómatas Finitos».»La idea básica detrás de ellos es bastante fácil. Solo imaginas una «máquina» simple que es capaz de tomar decisiones y moverse entre estados. Aquí hay un ejemplo de uno muy simple que representa la «lógica» de un torniquete que funciona con monedas.
En inglés sencillo, esto dice que si intentas empujar a través de un torniquete que está bloqueado, no puedes si no has puesto primero una moneda. Si has puesto una moneda pero aún no la has empujado, las monedas adicionales simplemente déjala en un estado desbloqueado. Si usted ha puesto una moneda, entonces usted puede empujar a través. Luego se bloquea de nuevo para la siguiente persona.
Probablemente era más fácil de entender del diagrama que de la descripción.
Los autómatas finitos son capaces de realizar una lógica mucho más complicada que esta. Pero esto debería darte una idea básica de cómo funcionan los autómatas finitos.
Una cosa a tener en cuenta es que un autómata finito, como el de arriba, es puramente teórico porque solo existe como un montón de burbujas y líneas en un pedazo de papel. No es como si hubiera una pequeña «máquina autómata finita» dentro del torniquete que toma estas decisiones. O tal vez debería decir que el torniquete en sí es la máquina autómata finita.
Si realmente quisiéramos, probablemente podríamos construir una máquina en la vida real que sería un Autómata finito.No hay nada que impida a alguien construirla como una máquina real en la vida real y luego instalarla en el torniquete. Esa no es la forma más barata de hacerlo.
Así que cualquier ‘programa’ que hagas como un dibujo de un autómata finito se puede convertir en una «computación» de la vida real que realmente funciona. La importancia de la diferencia entre una máquina computacional que realmente puede existir (como un Autómata finito) y una que es solo hipotética y viola las leyes de la física se vuelve importante en un momento.
Máquinas más Potentes
A medida que avanza una clase de teoría computacional, los estudiantes se introducen en «máquinas» cada vez más complejas que son más poderosas que los Autómatas Finitos. Como muestra la figura de la derecha, el siguiente más poderoso es el Autómata de empuje (PDA). Un PDA es realmente solo un DFA con la adición de una especie de «memoria». Esta memoria permite que un PDA cree y ejecute cálculos (o programas) que un DFA no puede.
El punto clave es solo que hay ciertos tipos de programas que se pueden escribir para un PDA que no se pueden escribir en un Autómata Finito Determinista (DFA). En otras palabras, los PDA son ‘más poderosos’ que los DFA porque pueden expresar clases de «programas» que los DFA no pueden.
Así que hay una relación entre los DFA y los PDA en términos de «potencia computacional».»Es decir, es posible probar que cualquier programa escrito en un DFA también se puede escribir en un PDA, pero que lo contrario no es cierto.
La prueba se encuentra en la Prueba
La prueba de que un PDA puede ejecutar cualquier cosa que un DFA pueda se realiza creando un esquema mediante el cual la lógica de un DFA se puede asignar a un PDA. Dado que un PDA es solo un DFA con memoria, esto no es difícil de hacer, simplemente no use la «función de memoria».
Pero, ¿qué hay de lo contrario? ¿Podemos probar que es imposible tomar ciertos tipos de» programas » escritos para un PDA y traducirlos a un DFA? Es decir, ¿hay alguna prueba de que los Autómatas de Empuje no se pueden asignar a Autómatas Finitos? ¿O simplemente asumimos que un Autómata Finito es menos poderoso que un Autómata de empuje porque actualmente no conocemos una forma de asignar un PDA a una FDA? Tal vez haya una manera de mapear PDAs a FDAs y tal vez nadie haya descubierto cómo hacerlo todavía. ¿No es al menos una posibilidad?
Resulta que es posible probar que un PDA puede ejecutar ciertos tipos de programas que un DFA no puede. La forma en que lo harías es encontrar un cálculo (i. e. un programa) que puede probar que un DFA no puede computar y luego demostrar que un PDA puede computarlo.
Potencia computacional de una máquina
Este hecho — que hay máquinas lógicas más potentes (PDA) y menos potentes (DFA) — es interesante en sí mismo.
Pero lleva a una pregunta filosófica: ¿existe tal cosa como una «máquina de computación más poderosa»?»
Si hubiera una «máquina más poderosa», ¿cómo sabríamos que cualquier máquina propuesta específica es «la más poderosa»?»¿O simplemente hay diferentes tipos de máquinas informáticas disponibles y tienes que elegir la adecuada para el trabajo?
Máquinas de turing
¿Qué máquina es más potente que una PDA?
Según la historia, casi al mismo tiempo se propusieron dos tipos muy diferentes de «máquinas» que eran probablemente más poderosas que las PDA.
Una era la máquina de Turing de Alan Turing. La otra no era tanto una máquina como un conjunto inteligente de anotaciones desarrolladas por Alonzo Church que servían para el mismo propósito que desarrollar una máquina. De estas dos «máquinas», la máquina de Turing es conceptualmente más fácil de enseñar, por lo que generalmente es la máquina que se enseña en un curso de Teoría Computacional.
Las máquinas de Turing son pequeñas máquinas teóricas divertidas que tienen un cabezal de lectura / escritura y una cinta de papel (hipotética) de la que puede leer o escribir. Basado en lo que la Máquina de Turing lee, pone a la Máquina de Turing en un estado de acción que realiza algún tipo de combinación de tareas que consiste en mover el cabezal de lectura/escritura hacia adelante o hacia atrás, leer desde una nueva posición en la cinta, o escribir una nueva posición en la cinta. Una máquina de Turing se parece a esto:
Máquinas de Turing y Computadoras modernas
Una cosa de interés es que una máquina de Turing es, a pesar de las apariencias de la superficie, en realidad bastante similar a una computadora moderna. En una computadora moderna, la Unidad Central de Procesamiento (CPU) es equivalente a la cabeza de lectura/escritura de una Máquina de Turing. Los chips de memoria (RAM o ROM) son muy similares a las celdas de la cinta de papel larga de la que la máquina de torneado puede leer o escribir. Así que las computadoras modernas parecen ser aproximadamente equivalentes a una máquina de Turing.
Una computadora moderna tiene una ventaja sobre la máquina de Turing. Una computadora moderna no tiene que moverse de una celda de su «memoria» en orden secuencial como lo hace una máquina de Turing.
El hecho de que una máquina de Turing solo pueda mover una celda a la vez parece una limitación significativa, ¿no? Acabamos de ver cómo algunas máquinas son lógicamente «más poderosas» que otras: una PDA puede realizar tareas computacionales que una FDA no puede. Entonces, ¿tal vez hay máquinas que son más poderosas que las máquinas de Turing que pueden realizar tareas que las máquinas de Turing no pueden? Y tal vez la computadora moderna, debido a su capacidad de saltar por la memoria en lugar de tener que moverse de una celda a otra secuencialmente, puede ejecutar algunos programas que una máquina de Turing no puede.
De hecho, la computadora moderna en realidad tiene menos poder expresivo que una máquina de Turing en virtud del hecho de que las Máquinas de Turing fueron concebidas como una cinta de papel infinitamente larga (es decir, memoria infinita) donde, como una computadora de la vida real, siempre tendrá memoria finita. Sin embargo, en general, esto hace muy poca diferencia en qué tipos de cálculos uno puede realizar, ya que los seres humanos generalmente no están interesados en cálculos infinitamente largos que dan resultados infinitamente largos. Es por eso que digo que las computadoras modernas y las Máquinas de Turing son «aproximadamente» equivalentes. De hecho, siempre y cuando asumas cualquier tamaño arbitrario pero finito de memoria, son exactamente equivalentes en términos de qué tipos de programas pueden ejecutar.
La Tesis de Turing de la Iglesia: Máquina de Turing = Potencia Lógica máxima
Pero ¿Qué pasa con la pobre Iglesia de Alonzo? Su pobre» máquina » olvidada porque las máquinas de Turing son más fáciles de enseñar. ¿Es su máquina tal vez capaz de expresar algunos cálculos /programas que una máquina de Turing no puede, o viceversa?
¿No sería una coincidencia estelar que Alan Turing y Alonzo Church crearan dos tipos completamente diferentes de máquinas de computación teórica y que fueran exactamente idénticas en términos de qué tipos de computación podían realizar?
Así que imagina la sorpresa de todos cuando Alan Turing fue capaz de producir una prueba de que cualquier programa escrito para una Máquina de Turing también podría escribirse para una máquina de Iglesia y también una prueba de que cualquier programa escrito para una máquina de Iglesia también podría escribirse para una máquina de Turing.
De hecho, hay una serie de tipos propuestos de máquinas computacionales teóricas. Por ejemplo, los teóricos intentaron permitir que una máquina de Turing tuviera varias cintas para leer / escribir. Incluso intentaron permitir que una máquina de Turing tuviera una «hoja» de 2 dimensiones para leer y escribir. Los teóricos intentaron todo tipo de mejoras en las máquinas de Turing (y las máquinas de Iglesia).
Y hasta ahora ha sido posible producir una prueba para cada uno de ellos de que son equivalentes a una simple máquina de Turing.
Eso parece una coincidencia salvaje, ¿no? Y sería una coincidencia salvaje a menos que haya un límite superior a qué tipos de computación se pueden realizar.
Si existe tal límite superior, entonces no sería coincidencia en absoluto que la Máquina de Turing y la Máquina de Church y todas las demás máquinas computacionales propuestas tengan la misma potencia computacional, ya que de hecho la razón por la que todas son equivalentes es porque hemos alcanzado el límite superior de potencia computacional.
Pero, ¿podemos probar que no hay ninguna máquina computacional por ahí, una que aún no hemos descubierto, que tenga la capacidad de realizar cálculos que una máquina de Turing no puede?
¿Cómo, exactamente, produciríamos tal prueba? El hecho es que no podemos probar que no hay nada más poderoso que una máquina de Turing. Así que, quién sabe, tal vez la haya.
Pero el hecho es que no podemos encontrar (o inventar) ninguna de estas máquinas.
Así que después de un esfuerzo considerable intentando y fallando, para encontrar una manera de mejorar el poder de las Máquinas de Turing, finalmente la Tesis de Turing de la Iglesia fue aceptada a pesar de que no se demostró que fuera cierta. La tesis de Church-Turing esencialmente dice algo como esto:
No es posible idear ningún tipo de máquina computacional que pueda realizar un programa lógico que una máquina de Turing simple y antigua no pueda.
O en otras palabras:
Las máquinas de Turing y sus equivalentes son los tipos de máquinas computacionales más potentes posibles y no hay más poderosas que no conozcamos todavía.
Después de años y años de investigación en esta Tesis, esta Tesis sigue siendo básicamente sostiene. Veremos más adelante que ha habido alguna modificación en la Tesis con la introducción de computadoras cuánticas teóricas. Pero, básicamente, la tesis sigue siendo válida hoy en día. Nadie ha encontrado una manera de superar a las máquinas de Turing cuando se trata de expresividad lógica. Las máquinas de Turing siguen siendo el campeón reinante.
Así que ahora entiendes la Tesis de Church-Turing. Sin embargo, la Tesis de la Iglesia-Turing no es realmente equivalente al Principio de Turing. Así que en un futuro post desarrollaré cuál es la diferencia y cuáles son sus ramificaciones filosóficas.
Notas
El Principio De Turing. Llamado así por Roger Penrose, que no cree en él (al menos no en la forma actual). Fue desarrollado en el principio Turing-Deutsch por David Deutsch, que cree en él, al menos en su forma de él.) (Ver artículo en Wikipedia para más detalles)