El programa que no puede existir

En el capítulo anterior, mencionamos que las máquinas de Turing y los programas en Python son equivalentes en términos de los «problemas» que pueden resolver. En este capítulo, definiremos formalmente la noción de problema y nos adentraremos en uno de los ejes centrales de la teoría de la computación: la decidibilidad (Sección 3.1).

A continuación, procederemos a introducir la máquina universal (Sección 3.2), un concepto que introdujo Turing al presentar su modelo de computación². Esta máquina nos servirá para encontrar problemas no decidibles (Sección 3.3). Finalmente, introduciremos el concepto de reducción (Sección 3.5), que nos permitirá encontrar aun más problemas no decidibles.

Haremos todo esto para deducir el resultado principal de este capítulo: la no decidibilidad del problema de la parada (Sección 3.6). Este problema es extremadamente relevante, no solo a nivel histórico, sino porque será uno de los pilares de la demostración principal de este trabajo, que haremos en el Capítulo 5.

3.1 #Problemas decidibles

Comenzamos, como anticipamos, definiendo de forma precisa qué es un problema.³⁴

Un problema no es más que una función que mapea entradas a salidas, a las que llamamos soluciones. Cualquier problema puede reducirse a esta terminología, por muy complejo que sea. Veamos la primera descripción de un problema.

Vamos a definir los conjuntos de entrada y salida del Problema 3.2. La entrada a nuestro problema es un grafo $G$, que no es más que un conjunto de vértices $V$ y una matriz de adyacencia $A$ representando sus arcos ($G = (V, A)$). Como salida, tendremos un conjunto de $n$ caminos en $G$, $\pi_1, \pi_2, \ldots, \pi_n$ (es posible que un grafo tenga ningún, uno o varios ciclos hamiltonianos). Podemos especificar los caminos como subconjuntos ordenados de $V$.

Para probar los resultados de nuestro trabajo, utilizaremos un subconjunto de problemas: aquellos cuya salida es únicamente sí o no. Los llamaremos problemas de decisión.

Cualquier problema computacional puede «transformarse» en un problema de decisión preguntándonos por la existencia de soluciones. Un ejemplo de esto lo vemos en el Problema 3.4.

Este problema es de decisión, pues no pregunta explícitamente por cuáles son los ciclos hamiltonianos presentes en un determinado grafo, sino por si existe un ciclo hamiltoniano en él. Evidentemente, estos problemas son más restrictivos que los problemas computacionales generales, pero tienen mucho más interés a la hora de hablar de qué problemas pueden computarse, como veremos más adelante.

En el caso de los problemas de decisión, tiene sentido hablar de su complementario.

En algunas ocasiones, usaremos la notación C- para referirnos al problema complementario: dado un problema $\textsc{Problema}$, llamaremos $\textsc{C-Problema}$ a su problema contrario.

Para continuar, es necesario comentar algunas particularidades de los programas en Python para tratar con problemas. Como bien sabemos, los programas sólo aceptan strings como entrada y strings como solución. Podemos pensar en un programa en Python $P$ como en una función

donde $S$ es el conjunto de todos los strings posibles en Python. Dependiendo de la versión de Python, este conjunto será mayor o menor.⁷

Para que un ordenador pueda resolver un problema, necesitaremos codificar las entradas y las soluciones del problema mediante un formato que pueda entender: las cadenas de caracteres (strings). Tal y como se demuestra en la Proposición 3.6, para cualquier problema podremos suponer que las entradas y soluciones están codificadas mediante strings.

Esto no supone una restricción: las entradas y las soluciones pueden ser codificadas como cadenas de caracteres. Deberemos, sin embargo, tener en cuenta que es posible que haya entradas que no sean una codificación correcta de una entrada del problema original. En tal caso, asignaremos la solución no a tal entrada.

Vemos un ejemplo de esto en el Problema 3.7. Este problema tendrá asociada una cierta codificación para las entradas y las soluciones. Observa que este problema es idéntico al Problema 3.2, y que podemos traducir las entradas y las soluciones de uno y otro conociendo la codificación elegida.

En el caso de los problemas de decisión, las soluciones siempre serán sí y no. Nótese que no será solución tanto para las instancias negativas del problema como para las codificaciones incorrectas.

De aquí en adelante, todos los problemas tendrán cadenas de caracteres como entradas y soluciones.

A continuación, concretaremos la relación entre programas y problemas que ya veníamos intuyendo desde el Capítulo 2.

Un problema computacional describe lo que queremos resolver. Un programa describe la forma particular de computar la solución a un problema.

Es muy importante destacar que, en la definición anterior, es necesario que $P$ pare para todas las entradas. O, lo que es lo mismo, si $P$ cicla para alguna entrada, no resuelve $F$. Esta condición puede relajarse dando lugar a problemas semidecidibles (véase la Sección 3.4).

En el caso de los problemas de decisión, esta característica de «resolver» nos conduce a la definición de computabilidad.

Veamos un problema más sencillo que el Problema 3.2. El Problema 3.10, $\textsc{MásAQueB}$, tiene como entrada una palabra del alfabeto $\{\texttt{a}, \texttt{b}\}$, y como solución sí en caso de que la palabra tenga más a que b, y no en caso contrario o en el caso de que la codificación sea incorrecta. Para este problema, la codificación es incorrecta si la entrada es una cadena de caracteres que no conforma una palabra del alfabeto $\{\texttt{a}, \texttt{b}\}$.

Evidentemente, $\textsc{MásAQueB}$ es un problema de decisión. Ahora nos queda preguntarnos si este problema es decidible. La respuesta es afirmativa, y se demuestra en detalle en la Proposición 3.11.

Si queremos saber si el problema es decidible, deberemos escribir un programa que lo resuelva y nunca cicle, y que tenga en cuenta las codificaciones incorrectas. Esto es precisamente lo que hace el programa a continuación:

import utilidades
 
def mas_a_que_b(palabra):
# comprobamos si la codificación es correcta, es decir (si es del alfabeto {'a', 'b'}), si no es correcta devolvemos 'no'
if not utilidades.en_alfabeto(palabra, {'a', 'b'}):
return 'no'
 
if palabra.count('a') > palabra.count('b'):
return 'sí'
 
return 'no'

Explicamos el programa brevemente. Vemos en la función mas_a_que_b la función main del programa, que acepta una palabra como entrada. Comprobamos que la palabra pertenezca al alfabeto $\{\texttt{a}, \texttt{b}\}$ mediante la función en_alfabeto de la librería utilidades (que importamos al comienzo del archivo). En caso de que la palabra no pertenezca al alfabeto, devolvemos no, pues la codificación es incorrecta. Si pertenece al alfabeto, comprobamos si tiene más a que b. En caso de ser así, devuelve sí y, si no, devuelve no. Vemos algunas de las salidas del programa mas_a_que_b.py en la tabla siguiente.

Dado que hemos encontrado un programa mas_a_que_b.py que decide $\textsc{MásAQueB}$, el problema $\textsc{MásAQueB}$ es decidible.

Una nota respecto a nuestra definición de decidibilidad. Normalmente, en los cursos de teoría de la computación, esta definición se hace respecto a máquinas de Turing. Sin embargo, al haber probado la equivalencia con los programas en Python en el Capítulo 2, podemos definirlo directamente en términos de programas. Según la definición de máquinas de Turing, sin embargo, también podríamos probar que $\textsc{MásAQueB}$ es decidible: basta ver que la máquina $M_{\#a>\#b}$ del Ejemplo 2.11 decide el problema, pues nunca cicla y acepta las palabras que tienen más $a$ que $b$.

3.2 #Universalidad

En la Sección 2.3 vimos cómo podemos simular una máquina de Turing mediante un programa en Python. Pero, ¿es posible simular un programa en Python mediante un programa en Python? La respuesta es sí, y no debería resultar sorprendente, pues muchas de las operaciones que ejecutamos en el día a día en nuestros ordenadores involucran este tipo de simulaciones.

Por ejemplo, al ejecutar un programa en Python cualquiera, estamos ejecutando el intérprete de Python, que es un programa en sí mismo.

Esta idea de «programas que ejecutan programas» puede parecer obvia, pero fue realmente revolucionaria, y es el motivo por el que los ordenadores personales son hoy la norma, llegando a encontrarse hasta en nuestros bolsillos. Quizás la cosa más increíble que puede hacer un ordenador es ejecutar cualquier cosa — no simplemente un conjunto de programas fijos preinstalados por el fabricante.⁸

Para entender cómo esto puede ser posible en el caso de un programa en Python, deberemos de entender el funcionamiento de la función nativa exec⁹. Si probamos en el intérprete:

>>> exec("print('resultado:', 11+2)")
resultado: 13

Vemos cómo a exec pasamos una sentencia en Python en forma de string, y la ejecuta. De hecho, observa cómo ha ejecutado la suma $11 + 2$, y no simplemente ha imprimido 11+2.

Esto podemos llevarlo un paso más allá: dentro de exec podemos insertar varias líneas e incluso definir funciones, variables, etc.

>>> exec("def hola(nombre):\n\tprint(f'Hola, {nombre}')\nhola('TFG')")
Hola, TFG

Una vez conocemos esto, podemos crear el siguiente programa:

import utilidades
 
def maquina_universal(programa, entrada):
# esto define las funciones del programa, pero no las ejecuta
try:
exec(programa)
except Exception as excepcion:
return 'error: ' + str(excepcion)
 
# extraemos una referencia a la función main, que está definida localmente
main = utilidades.extraer_main(programa, locals())
 
# invocamos la función
return main(entrada)

Veamos qué es lo que hace el Programa 3.2. En primer lugar, vemos que la función main admite dos parámetros: un programa y una entrada, ambos string. Ejecutamos el programa definido en programa, tal y como explicamos anteriormente. Esta línea está dentro de un bloque try-except dado que es posible que el programa esté mal definido, en cuyo caso se lanza una excepción. Esta excepción la cazamos, dado que según la Definición 2.2, el programa no debe lanzar ninguna excepción. De haber una excepción, devolvemos un string con los detalles del error.

Si no hay error, exec(programa) se ejecutará satisfactoriamente, y las funciones que se definan en programa serán accesibles desde la función maquina_universal. En concreto, todas las definiciones de programa serán accesibles desde locals(). Aprovechamos esto para extraer una referencia a la función main de programa, que finalmente ejecutamos con la entrada entrada.

Hemos logrado crear un programa en Python que es capaz de ejecutar otro programa. Esto nos permitirá ejecutar cualquiera de los problemas que hemos creado, sin más que pasar el programa a un string. En la librería utilidades se encuentra la función leer, que dada una ruta a un archivo devuelve sus contenidos como un único string.

Algunos ejemplos de ejecución de maquina_universal.py se especifican en la tabla siguiente.

En la primera fila podemos ver que, al insertar un programa inválido como entrada, la salida de maquina_universal.py será de error. En la segunda fila, ejecutamos el programa mas_a_que_b.py con la entrada abaab. El resultado es exactamente el esperado (observa la primera fila de la tabla de salidas de $\textsc{MásAQueB}$ anterior).

En la tercera fila, usamos el propio código de mas_a_que_b.py como entrada para sí mismo. Esto tiene sentido, dado que un programa, como hemos comentado, no es más que un string. Recuerda que el Programa 3.1 trata entradas fuera del alfabeto $\{\texttt{a}, \texttt{b}\}$ como una entrada incorrecta, y es por ello por lo que la salida es no. Modificamos esto en el Programa 3.3, en el que aceptamos cualquier entrada y contamos su número de a y b. Vemos cómo, en la cuarta fila, la salida es sí, dado que en este caso la codificación es correcta.

def mas_a_que_b_v2(palabra):
if palabra.count('a') > palabra.count('b'):
return 'sí'
 
return 'no'

En la quinta fila, utilizamos el Programa 3.4. Este programa siempre devuelve sí, independientemente de la entrada que pasemos. Evidentemente, este programa es el que decide el Problema 3.12 (es decir, $\textsc{Sí}$ es decidible).

def si(entrada):
# siempre devuelve 'sí'
return 'sí'

En la sexta y última fila vemos cómo maquina_universal.py puede ejecutar cualquier programa en Python, incluso el Programa 2.2, que simula máquinas de Turing. Como entrada al programa pasamos la codificación de una máquina de Turing y la entrada. En este caso, la salida describe una configuración final aceptante.

Esta capacidad de los programas de ejecutarse a sí mismos es extremadamente interesante y es una característica que nos causará muchos problemas, como veremos en la Sección 3.3.

Llamamos a una máquina universal si es capaz de simular cualquier máquina de Turing, dado que este concepto lo introdujo Turing en su famosa publicación². Por el resultado de equivalencia (Teorema 2.23), vemos que el Programa 3.2 es, en efecto, una máquina universal (algo que podíamos intuir con el nombre del programa).

Como vimos al principio, el concepto de universalidad es una constante en los ordenadores que usamos: el hardware es universal, porque puede ser usado para ejecutar cualquier máquina de Turing, del mismo modo que lo es un sistema operativo, pues puede compilar programas que simulan máquinas de Turing. El intérprete de Python también es universal por este mismo motivo, así como la máquina virtual de Java. Incluso un programa en sí mismo (Programa 3.2) puede ser universal.

3.3 #Problemas no decidibles

En la Sección 3.1 mostramos cómo probar que un problema es decidible, lo cual es sencillo: basta encontrar un programa que lo decida. Sin embargo, probar que un problema no lo es es mucho más complicado. En este apartado encontraremos varios problemas no decidibles.

Comencemos por el problema $\textsc{Universal}$.¹⁰ Claramente, se trata de un problema de decisión, pues devuelve sí o no. En esta sección, probaremos que escribir un programa que decida $\textsc{Universal}$ es imposible. En caso de que fuese posible hacerlo, vemos en la tabla siguiente las posibles salidas que tendría.

En la primera fila vemos cómo, para codificaciones incorrectas, el programa devuelve no. Las filas siguientes son evidentes, y similares a las de la tabla de maquina_universal.py.

Introduciremos dos problemas más. El primero de ellos, $\textsc{Diagonal}$, podemos obtenerlo a partir de $\textsc{Universal}$ (Problema 3.13) con $I = P$.

En caso de existir un programa que decida este problema, vemos en la tabla siguiente las posibles salidas que tendría.

Las tres primeras salidas no requieren más explicación. Sin embargo, centrémonos en la última: ¿cuál sería el resultado de ejecutar diagonal.py con el código de diagonal.py?

Parece ser que tanto sí como no son ambas respuestas correctas — basta ver la definición del Problema 3.14. Tomando $I$ como diagonal.py y $P$ como el mismo programa, entonces, si $P(I)=\texttt{sí}$, el programa devolverá sí, mientras que si $P(I)=\texttt{no}$, entonces el programa devolverá no.

Llegado a este punto deberíamos sospechar que las cosas no van a ir bien. Terminemos este «circo recursivo» con un último problema, $\textsc{C-Diagonal}$.¹¹ En caso de existir un programa que lo decida, c_diagonal.py, vemos sus posibles salidas en la tabla siguiente.

Volvemos a repetir la misma pregunta que nos hicimos para el caso de $\textsc{Diagonal}$ (Problema 3.14). ¿Qué salida tendría un hipotético programa que lo resolviese, si se usa a sí mismo como entrada? En este caso, esta pregunta es justamente la que nos demuestra que escribir tal programa es imposible. Esto nos indica que el problema $\textsc{C-Diagonal}$ no es decidible. Veamos una demostración más precisa de este hecho.

Acabamos de encontrar nuestro primer problema no decidible: $\textsc{C-Diagonal}$. Este hecho es de especial relevancia pues, a partir de él, podemos probar que $\textsc{Universal}$ tampoco lo es.

from universal import universal
 
def diagonal(programa):
return universal(programa, programa)

from diagonal import diagonal
 
def c_diagonal(programa):
salida = diagonal(programa)
 
if salida == 'sí':
return 'no'
else:
return 'sí'

Podemos ver la cadena de problemas que hemos usado en la Proposición 3.17 en la figura siguiente.

Probar la no decidibilidad de $\textsc{Universal}$ ha sido un proceso largo, que ha requerido de otros problemas. Sería posible demostrar este resultado usando un único programa, pero, usando las propias palabras de Turing, «[tal] prueba, aunque perfectamente sólida, [tendría] la desventaja de que puede dejar al lector con la sensación de que ‘debe haber algo mal’»².

Ya hemos demostrado que dos de los tres problemas de la cadena anterior no son decidibles. El siguiente resultado nos permitirá probar que el último de ellos tampoco lo es.

from d import d
 
def c_d(entrada):
salida = d(entrada)
 
if salida == 'sí':
return 'no'
else:
return 'sí'

Por el Corolario 3.19, al saber que $\textsc{C-Diagonal}$ (Problema 3.15) es no decidible (Proposición 3.16), tenemos que $\textsc{Diagonal}$ (Problema 3.14) es no decidible.

Saber que estos problemas no son decidibles es muy útil, pues nos permiten probar lo que buscamos en este capítulo: que el problema de la parada, que introduciremos en la Sección 3.6, tampoco es decidible.

Para poder demostrar esto, sin embargo, deberemos usar una nueva herramienta, que desarrollaremos en la Sección 3.5. Antes, comentaremos otra clase de problemas: aquellos que «casi» son decidibles.

3.4 #Problemas semidecidibles

En la Definición 3.9, exigimos que el programa pare para cada entrada para poder decir que el problema es decidible. Si relajamos esta condición obtenemos una nueva categoría de problemas.

Es claro que todo problema decidible es semidecidible. El recíproco no es cierto. Veremos un ejemplo de esto más adelante, en el Problema 4.25.

No profundizaremos en la noción de problema semidecidible, ya que no será necesario para nuestro estudio. Cuando sea necesario, recurriremos a la definición aquí especificada.

3.5 #Reducciones

En la Sección 3.3, hemos usado unos problemas para poder resolver otros o para probar que no pueden resolverse (véase la figura de la cadena de problemas anterior). En teoría de la computación, esta intuición se formaliza en el concepto de reducción. Cuando decimos que «$F$ se reduce a $G$», nos referimos a que «$F$ se puede resolver si $G$ se puede resolver».

Al programa $P_G$ del que asumimos su existencia lo llamamos oráculo, siguiendo la terminología de las máquinas con oráculo de Turing.¹³

Intuitivamente, si podemos reducir $F$ a $G$, es porque $G$ es al menos tan «difícil» como $F$ o, recíprocamente, $F$ es al menos tan «fácil» como $G$. Esta intuición se recoge en la proposición siguiente.

Esta proposición nos permite probar que un problema es decidible (o no) a partir de otro. Esto nos permite proceder por varias vías. En primer lugar, si queremos saber que un problema $F$ es fácil, nos basta encontrar un problema decidible $G$ que reduzca a $F$, $F \leq_T G$. Entonces, $F$ será decidible.

Por otra parte, podemos probar que un problema $G$ es difícil. Basta tener un problema $F$ no decidible tal que $F \leq_T G$. Entonces, $G$ tampoco será decidible.

Veamos un primer ejemplo de reducción. En la Sección 3.3 ya vimos que $\textsc{Diagonal}$ (Problema 3.14) y $\textsc{Universal}$ (Problema 3.13) son ambos no decidibles. Supongamos que únicamente conocemos que $\textsc{Diagonal}$ es no decidible. Entonces, podremos probar la no decidibilidad de $\textsc{Universal}$ mediante una sencilla reducción.¹⁴ Observa el programa siguiente.

from universal import universal  # oráculo
 
def diagonal(programa):
salida = universal(programa, programa)
 
if salida == 'sí':
return 'sí'
else:
return 'no'

Es sencillo ver que diagonal_a_universal.py es una reducción de $\textsc{Diagonal}$ a $\textsc{Universal}$. En efecto, el programa diagonal_a_universal.py resuelve $\textsc{Diagonal}$ asumiendo la existencia de un programa universal.py que resuelva $\textsc{Universal}$.

3.6 #El problema de la parada

Dado un programa $P$ y una entrada $I$, nos hemos preguntado por cuál es la salida de tal programa. Ahora, vamos a preguntarnos por si el programa para.

Este problema, de reconocer si un programa para dada una entrada, es el conocido como problema de la parada. Los motivos por los que lo estudiamos son varios: en primer lugar, este problema tiene aplicación práctica. En caso de ser decidible, podríamos escribir un algoritmo que, para cualquier programa, nos comprobara si es capaz de terminar. Evidentemente, no todos los programas paran: algunos de ellos están diseñados para ejecutarse de forma indefinida, como es el caso de los servidores web o de un sistema operativo.

Por otra parte, este problema tiene una especial relevancia histórica. Fue uno de los primeros problemas en ser demostrados no computables, y es uno de los gérmenes de la teoría de la computación.

En nuestro caso, sin embargo, estudiar este problema nos permitirá deducir el resultado central de este trabajo.

Antes de hablar sobre este problema, debemos recordar que la noción de parada que definió Turing está relacionada con las máquinas de su mismo nombre: una máquina de Turing, dada una entrada, puede parar y aceptar, parar y rechazar, o ciclar.

En nuestro caso, diremos que un programa en Python $P$ para dada una entrada $I$ si la salida $P(I)$ está definida, de acuerdo a la Definición 2.3. Un programa podría, de este modo, no parar por muchas razones: podría entrar en un bucle infinito, lanzar una excepción o devolver un objeto que no sea un string. En los dos últimos casos, puede parecer contraintuitivo decir que el programa no ha parado: al fin y al cabo, el programa para al lanzar una excepción o devolver un objeto que no sea un string. En estos casos, es mejor pensar que el programa se ha «congelado»: no está ejecutando más código, pero no puede terminar satisfactoriamente. En este sentido, el programa «no ha parado».

Ahora estamos en condiciones de presentar la formulación del problema.

Nos preguntamos si este problema es decidible. La respuesta es negativa, y esperable teniendo en cuenta todos los problemas de este estilo que ya hemos probado no decidibles (Problema 3.13, Problema 3.14, Problema 3.15).

import utilidades
from maquina_universal import maquina_universal
 
def maquina_universal_parada(entrada_codificada):
(programa, entrada) = utilidades.UAM(entrada_codificada)
salida = maquina_universal(programa, entrada)
 
if salida == 'sí':
return 'sí'        # para
else:
utilidades.ciclar()  # cicla

import utilidades
from parada import parada  # oráculo
 
def universal_a_parada(programa, entrada):
entrada_codificada = utilidades.MAU(programa, entrada)
maquina_universal_parada = utilidades.leer('maquina_universal_parada.py')
 
return parada(maquina_universal_parada, entrada_codificada)

En la demostración anterior hemos usado una técnica nueva: crear un programa nuevo a partir de otro. En concreto, modificamos maquina_universal.py (Programa 3.2), la máquina universal en Python que introdujimos en la Sección 3.2, para crear una máquina universal que para para las salidas positivas y cicla para cualquier otra salida.

A continuación, introduciremos un nuevo problema de la parada, más sencillo que el problema $\textsc{Parada}$ ya enunciado.¹⁵

Por tratarse de un problema «más sencillo», inicialmente no tiene por qué ser no decidible. Para probarlo, deberemos realizar un «truco»: ignorar la entrada.

import utilidades
from maquina_universal import maquina_universal
 
def ignora_entrada(entrada_ignorada):
programa = utilidades.leer('disco/programa.txt')
entrada = utilidades.leer('disco/entrada.txt')
return maquina_universal(programa, entrada)

Para ello, usamos el Programa 3.11. Este programa, en lugar de ejecutar la entrada entrada_ignorada, ejecuta la máquina universal sobre un programa y una entrada almacenadas en disco. Concretamente, usa como programa el almacenado en disco/programa.txt, y como entrada la almacenada en disco/entrada.txt.

Una vez conocemos el funcionamiento de ignora_entrada.py, es sencillo encontrar una reducción de $\textsc{Parada}$ a $\textsc{ParadaEnVacío}$.

import utilidades
from parada_en_vacio import parada_en_vacio  # oráculo
 
def parada_a_parada_en_vacio(programa, entrada):
utilidades.escribir('disco/programa.txt', programa)
utilidades.escribir('disco/entrada.txt', entrada)
 
return parada_en_vacio(utilidades.leer('ignora_entrada.py'))

Para concluir, introducimos una tarea de predicción: $\textsc{AdivinaConsistente}$.¹⁶

A diferencia de un problema de decisión ordinario, esta tarea no fija una única respuesta correcta para cada entrada: en los programas que ciclan se admiten ambas. Lo que buscamos es un predictor computable total que respete los resultados de todos los programas que sí terminan. Ni siquiera con esa libertad existe tal predictor.

import utilidades
from adivina_consistente import adivina_consistente  # predictor total supuesto
 
def modifica_adivina_consistente(programa):
utilidades.escribir('disco/programa.txt', programa)
utilidades.escribir('disco/entrada.txt', programa)
 
salida = adivina_consistente(utilidades.leer('ignora_entrada.py'))
 
if salida == 'sí':
return 'no'
else:
return 'sí'

El problema $\textsc{ParadaEnVacío}$ y la tarea $\textsc{AdivinaConsistente}$ serán centrales en la demostración de dos variantes del resultado principal de este trabajo, en el Capítulo 5. A modo de resumen, se proporciona la tabla siguiente con todos los problemas presentados en este capítulo.

3.7 #Resumen