Python es una máquina de Turing

La máquina de Turing, inventada por Alan Turing en 1937², es un modelo matemático sencillo que pretende representar la noción de algoritmo, y del que hablaremos en detalle en la Sección 2.2. Esta máquina es una de las herramientas más relevantes en las ciencias de la computación, pues su simplicidad permite demostrar resultados importantes, como la indecidibilidad del problema de parada (Proposición 3.24), a partir del cual podremos adentrarnos en la cuestión principal de nuestro trabajo: la incompletitud de las matemáticas. Sin embargo, esta potencia formal tiene una desventaja, que comprobaremos a partir de un simple ejemplo (Ejemplo 2.11): definir programas sencillos en este modelo es complejo y tedioso.

Este inconveniente es el que motiva este capítulo: en la Sección 2.3 probaremos la equivalencia entre los programas de ordenador (en nuestro caso, los programas en Python, que exploraremos en la Sección 2.1) y las máquinas de Turing. Esto nos permitirá ver un programa en Python como una representación de una máquina de Turing, eliminando el principal inconveniente y quedándonos con la potencia matemática ya comentada.

Es importante resaltar que los resultados que aquí aparecen son perfectamente generalizables a cualquier lenguaje de programación Turing-completo. Sin embargo, decidimos usar este lenguaje por su facilidad de comprensión y de uso.

Tanto el resultado de equivalencia que probamos en este capítulo como la observación anterior son especialmente interesantes, ya que guardan una fuerte relación con la tesis de Church–Turing, de la que hablaremos brevemente en la Sección 2.4.

2.1 #Programas en Python

Python³ es un lenguaje de programación de alto nivel, interpretado, orientado a objetos y open source, ampliamente usado en la actualidad para una gran variedad de aplicaciones. Una de sus principales características es su legibilidad y facilidad de uso: cualquier persona experimentada en otros lenguajes podrá comprender y redactar programas en Python con mucha sencillez.

Usando Python, podemos escribir una gran variedad de programas. Para el propósito de nuestro estudio, nos centraremos en una clase de programas específica: aquella que tiene únicamente una cadena de caracteres como entrada y una cadena de caracteres como salida. Los llamaremos programas SISO (del inglés, Single Input–Single Output; véase Definición 2.2)⁴. En breve, comprobaremos cómo esta clase no es restrictiva: estos tipos de programas son tan expresivos como cualquier otro programa. De hecho, en este trabajo usaremos los términos «programa» y «programa SISO» indistintamente, y en ambas ocasiones nos referiremos a un programa en Python de tipo SISO.

Observemos que en la definición anterior se especifica un sistema informático $C$, pero no se define de forma explícita. Podemos pensar en $C$ como cualquier sistema informático, con cualquier configuración de software y hardware, y con tanta memoria como sea necesaria.

También podemos preguntarnos qué queremos decir cuando nos referimos a un programa como «sintácticamente correcto», dado que esto dependerá de varios factores, como la versión de Python instalada en $C$, así como el sistema operativo, arquitectura, etc. Es posible que un programa se ejecute en un sistema $C$ y falle o incluso dé una salida diferente en otro sistema $C'$. Sin embargo, y como veremos más adelante, usaremos estos programas como representaciones de máquinas de Turing. Los programas que presentamos aquí son independientes de arquitectura y de memoria, y las demostraciones que figuran en este trabajo son independientes de todas estas características.

También necesitaremos definir cuál es la salida de un programa en Python.

En otras palabras, la salida de un programa es la cadena de caracteres devuelta por su función main en caso de que lo haga, y no estará definida en caso contrario.

Al definir los programas en Python que usaremos en este trabajo, nos centramos en el uso de cadenas de caracteres (también llamadas strings) como entrada y salida, y evitamos el uso de otros objetos de Python que no sean strings. Inicialmente, podemos pensar que esto impone una limitación sobre los programas en Python que podemos escribir, pero esto realmente no es así. Para ello, basta observar que cualquier objeto en Python puede codificarse debidamente mediante una cadena de caracteres. Existen librerías nativas que permiten hacer esto, como pickle.⁶ Un ejemplo de esto se muestra en el Programa 2.1. La función function_with_encoded_object es una función main.

import pickle
from base64 import b64decode, b64encode
 
def function_with_encoded_object(encoded: str) -> str:
decoded = pickle.loads(b64decode(encoded.encode('ascii')))
return str(decoded)
 
adjacencies = {1: 2, 3: 4, 5: 3, 4: 2}
adjacencies_encoded = b64encode(pickle.dumps(adjacencies)).decode('ascii')
function_with_encoded_object(adjacencies_encoded)

pickle.dumps serializa el objeto a bytes, no a str. Usamos Base64 para representar esos bytes como una cadena ASCII y los recuperamos antes de llamar a pickle.loads. La función también devuelve una cadena, de modo que tanto la entrada como la salida cumplen la definición SISO.

En resumen, hemos visto cómo la condición de ser SISO para un programa en Python no es realmente una restricción. Sin embargo, esta clase de problemas nos resultará muy conveniente, como veremos más adelante.

2.2 #Máquinas de Turing

Las máquinas de Turing, primero descritas por Alan Turing en 1936², son dispositivos computacionales abstractos y simples creados para ayudar a investigar qué problemas pueden ser computados. Las «máquinas automáticas» —tal como Turing las llamó en 1936— fueron específicamente diseñadas para computar números reales. Estas máquinas no fueron nombradas «máquinas de Turing» hasta 1937, cuando Alonzo Church⁷ revisó la publicación original de Turing. Hoy se consideran uno de los modelos fundamentales de la teoría de la computación, pues son la representación matemática de un algoritmo⁸.

Antes de comprender cómo funcionan estas máquinas, haremos unas definiciones previas.

La primera definición presentada por Turing en 1936² dista de la que se presenta en la Definición 2.5. Sin embargo, ambas son equivalentes.

La definición anterior es un tanto abstracta, y podemos visualizarla mejor en la Figura 2.1. En ella, vemos las tres partes «físicas» de la máquina: la unidad de control, el cabezal y la cinta. La cinta contiene casillas, cada una de las cuales puede almacenar un símbolo. Inicialmente, los símbolos son los del alfabeto de entrada, pero conforme la máquina va ejecutando instrucciones se puede usar el alfabeto de trabajo. Estos símbolos incluyen un símbolo blanco, denotado $\sqcup$, y se encuentran en todas las posiciones de la cinta que no codifican la palabra de entrada. El cabezal puede moverse por la cinta a la izquierda y a la derecha (o quedarse en el sitio), informando a la unidad de control de los símbolos que ve. El símbolo al que apunta el cabezal lo llamaremos símbolo escaneado. El cabezal puede reemplazar el símbolo escaneado por cualquier otro del alfabeto de trabajo, incluyendo el símbolo blanco. La unidad de control manda transiciones al cabezal, y cambia entre los diferentes estados en función de los símbolos leídos por el cabezal.

Es importante aclarar que la máquina de Turing realmente no tiene ninguna «unidad de control» o «cabezal»: es una descripción matemática. Lo que hemos hecho es proporcionar una especificación intuitiva de cómo se ejecuta el algoritmo que representa tal máquina.

Para describir la máquina en cada momento, necesitaremos el concepto de configuración.

Lo único que nos queda es precisar la noción de «paso de cálculo» que comentamos anteriormente. En cada paso, aplicamos una transición y cambiamos la configuración de la máquina. Esto es lo que denominamos proceso de cálculo, y formalizamos a continuación.

En definitiva, vemos que la máquina, en función del estado en el que se encuentre y el símbolo escaneado, ejecutará una cierta transición, definida en $\delta$, que le dirá a qué estado pasar, por qué símbolo reemplazar el escaneado y el movimiento que tiene que realizar sobre la cinta.

Una nota importante respecto a las transiciones no definidas. A la hora de describir una función de transición, definiremos únicamente las transiciones para los estados $q \in Q$ y símbolos $b \in B$ para los que están definidas. En caso contrario, podemos asumir que $\delta(q, b) = \emptyset$. Puedes ver esto en el Ejemplo 2.11, que comentaremos en detalle más adelante.

Introducimos una notación gráfica para la función de transición. La definiremos mediante un grafo dirigido: representaremos los estados como nodos (uno para cada estado) y las transiciones como arcos dirigidos.

El estado inicial se simbolizará, además de en la definición de la máquina, con una flecha apuntando al estado (no es un arco, sino que no proviene de ningún nodo):

Para cada transición $\delta(q,b)=(p,c,M)$, insertaremos un arco dirigido conectando los nodos correspondientes a los estados $q$ y $p$ como sigue:

En caso de que tengamos varias funciones de transición entre ambos estados ($\delta(q,b)=(p,c,M)$ y $\delta(q,b')=(p,c',M')$), colocaremos varias líneas en el arco para simbolizarlo:

Finalmente, también indicaremos los estados finales rodeando dos veces el nodo:

Observemos cómo una máquina de Turing, dada una entrada, puede:

• parar y aceptar,
• parar y rechazar, o
• no parar (ciclar).

La máquina para cuando llega a una configuración para la que no hay una transición definida. Cuando ocurre esto, podemos definir una salida con los símbolos que quedan en la cinta.

Al haber definido qué palabras acepta una máquina determinada, introducimos el concepto de lenguaje. Un lenguaje no es más que un conjunto de palabras.

Concretemos todos los conceptos que hemos introducido mediante un ejemplo.

Una vez que hemos descrito con precisión qué es una máquina de Turing, procederemos a probar el resultado más importante de este capítulo (Teorema 2.23), que ya anticipamos en la introducción: la equivalencia entre las máquinas de Turing recién expuestas y los programas en Python que definimos en la Sección 2.1.

2.3 #Equivalencia

Nuestro objetivo ahora es comprender por qué las máquinas de Turing tienen la misma potencia de cálculo que los programas en Python. En otras palabras, queremos demostrar que los problemas que podemos resolver en ambos son los mismos.¹²

Para probar la equivalencia entre ambos modelos de cálculo, recurriremos al concepto de simulación. Es normal para diferentes modelos computacionales simularse unos a otros. Un ejemplo de esto es la máquina virtual de Java (JVM), que es un modelo abstracto capaz de ejecutar cualquier programa en Java¹³. Otro ejemplo es el sistema operativo Linux, que es capaz de ejecutar la JVM. Por lo tanto, un ordenador Linux es capaz de ejecutar cualquier programa en Java. Esto es posible mediante la cadena de simulaciones:

Usamos la notación $A \leadsto B$ para indicar que $A$ simula a $B$. El hecho de que $A$ simule $B$ quiere decir, sencillamente, que es posible realizar el procedimiento de cálculo de $B$ usando exclusivamente el procedimiento de cálculo de $A$.

Procederemos a probar la equivalencia mostrada mediante la cadena de simulaciones que aparece en la Figura 2.6.

El trabajo que haremos en esta sección es arduo, y necesitaremos introducir diversos modelos computacionales para llegar a nuestro objetivo. Sin embargo, una vez probemos todas las simulaciones, sabremos que todas ellas son equivalentes, y podremos usar el modelo que queramos a conveniencia.

El primer modelo computacional que estudiaremos lo obtendremos añadiendo más cintas y cabezales a la máquina de Turing que definimos en la Sección 2.2¹⁴.

Esta definición es intuitiva y esperable. Simplemente incorporamos más cintas y cabezales. De ahora en adelante, también usaremos el término «máquina de Turing de una sola cinta» para referirnos a la máquina de Turing que definimos en primer lugar.

Uno puede pensar que estas máquinas tienen más poder computacional que las de una sola cinta, pero, sin embargo, son equivalentes. Es evidente que una máquina multicinta simula una máquina de una sola cinta (la Definición 2.5 es la misma que la Definición 2.12 para $k=1$). En la Proposición 2.13 vemos cómo el recíproco también es cierto.

Los detalles de esa construcción — el alfabeto de trabajo, los estados auxiliares y cada cláusula de $\widetilde{\delta}$ — son los siguientes.