Lenguajes Formales, Autómatas y Computabilidad
Funciones computables
Franco Frizzo
30 de octubre de 2024
Índice
1. El lenguaje 𝒮++ ............................................................................................................... 1
1.1. Variables de un programa .......................................................................................... 2
1.2. Instrucciones .............................................................................................................. 2
1.3. Programas .................................................................................................................. 2
1.4. Función computada ................................................................................................... 2
1.5. Macros ....................................................................................................................... 3
2. Funciones y lenguajes computables ................................................................................... 5
2.1. Funciones computables y parcialmente computables ................................................. 5
2.2. Composición de funciones computables ..................................................................... 5
2.3. Funciones primitivas recursivas .................................................................................. 6
2.4. Lenguajes computables .............................................................................................. 6
3. Codificación de programas ................................................................................................ 7
4. Snap, Step y programa universal ................................................................................... 10
4.1. Configuración instantánea y la función Snap .......................................................... 10
4.2. El predicado Step ................................................................................................... 10
4.3. Programa universal .................................................................................................. 11
Referencias .......................................................................................................................... 13
1. El lenguaje 𝒮++
Intuitivamente, la noción de función computable es fácil de definir: una función 𝑓 : ℕ𝑛 → ℕ
es computable si puede darse un algoritmo que la calcule para cualquier valor de entrada. Sin
embargo, si queremos darle un poco más de precisión a esta definición, tenemos que determinar
de manera precisa qué entendemos por “algoritmo”.
Existen distintas formas de definir este concepto, de las cuales la más popular es la máquina de
Turing. Descritas por primera vez por Alan Turing en un paper fundacional publicado en 1937
[1], se trata de un autómata sofisticado, que además de tener estados (como un autómata finito
o de pila), cuenta con una cinta infinita que hace las veces de entrada y memoria de trabajo.
Una diferencia fundamental entre las máquinas de Turing y otros autómatas que vimos en
la materia es que además de aceptar o rechazar una entrada determinada, también pueden
“colgarse” sin alcanzar nunca ninguno de los dos resultados.
La tesis de Church-Turing nos dice que este formalismo captura de manera completa lo que
intuitivamente entendemos como “algoritmo”; es decir, que no existen funciones computables
para las que no sea posible dar una máquina de Turing.
Existen también muchos otros formalismos que se han demostrado equivalentes a las máquinas
de Turing (también llamados Turing-completos). En la práctica de la materia ya vimos uno
1
Lenguajes Formales, Autómatas y Computabilidad Funciones computables
de ellos (las gramáticas sin restricciones o de tipo 3). Hoy trabajaremos con otro: un lenguaje
de programación muy sencillo que llamaremos 𝒮++.¹
1.1. Variables de un programa
En un programa de 𝒮++ se pueden usar variables de tres tipos:
• Parámetros o variables de entrada: 𝑋1 , 𝑋2 , 𝑋3 , …
• Variables locales: 𝑍1 , 𝑍2 , 𝑍3 , …
• Salida: 𝑌
1.2. Instrucciones
Sean 𝑉 una variable y 𝑃 un programa. Una instrucción de 𝒮++ es una de las siguientes:
• Incremento (𝑉 ++): Incrementa el valor de 𝑉 en 1.
• Decremento (𝑉 −−): Decrementa el valor de 𝑉 en 1 (si es 0, no hace nada).
• Loop (while 𝑉 ≠ 0 do { 𝑃 }): Ejecuta 𝑃 mientras 𝑉 sea distinto de 0.
• Instrucción vacía (pass): No hace nada.
1.3. Programas
Un programa es una sucesión de instrucciones. Para hacerlos más legibles, las escribimos en
líneas separadas. Por ejemplo:
𝑃1 : 𝑍1 ++
𝑍1 ++
while 𝑍1 ≠ 0 do {
𝑌 ++
𝑍1 −−
}
1.4. Función computada
(𝑛)
Dado un programa 𝑃 , para cada 𝑛 ∈ ℕ, se define Ψ𝑃 : ℕ𝑛 → ℕ, la función computada por
𝑃 con 𝑛 entradas.
(𝑛)
Ψ𝑃 es una función parcial, es decir, puede ser que para ciertos valores de entrada no esté
definida. Dada una entrada 𝑥1 , …, 𝑥𝑛 ∈ ℕ, usamos la notación:
(𝑛)
• Ψ𝑃 (𝑥1 , …, 𝑥𝑛 ) ↓ si la función está definida.
(𝑛)
• Ψ𝑃 (𝑥1 , …, 𝑥𝑛 ) ↑ si la función no está definida.
(𝑛)
Llamamos Dom(Ψ𝑃 ) ⊆ ℕ𝑛 , el dominio de la función, al conjunto de valores para los que
está definida, y decimos que la función es total si su dominio es todo el conjunto ℕ𝑛 .
(𝑛)
Para obtener el valor de la función Ψ𝑃 para los valores de entrada 𝑥1 , …, 𝑥𝑛 ∈ ℕ, seguimos
estos pasos:
1. Inicializamos las variables 𝑋1 , …𝑋𝑛 en los valores 𝑥1 , …, 𝑥𝑛 , y las demás variables en 0.
2. Ejecutamos en orden las instrucciones de 𝑃 .
(𝑛)
3. Si la ejecución termina, entonces Ψ𝑃 (𝑥1 , …, 𝑥𝑛 ) ↓ y su valor es el de la variable 𝑌 al
(𝑛)
finalizar la ejecución. Si la ejecución no termina, entonces Ψ𝑃 (𝑥1 , …, 𝑥𝑛 ) ↑.
¹Para convencerse de que 𝒮++ es Turing-completo, consultar la clase teórica.
2
Lenguajes Formales, Autómatas y Computabilidad Funciones computables
Por ejemplo, en el caso del programa 𝑃1 definido antes (que no mira ninguna de las variables
(𝑛)
de entrada), podemos ver que para todo 𝑛 ∈ ℕ, 𝑥1 , …, 𝑥𝑛 ∈ ℕ vale que Ψ𝑃 (𝑥1 , …, 𝑥𝑛 ) = 2.
Es decir, la función computada por 𝑃1 (para cualquier cantidad de entradas) es la función
constante 2.
1.5. Macros
En 𝒮++, por simplicidad, no existe la posibilidad de definir y hacer llamados a funciones.
Sin embargo, dado lo minimal del lenguaje, muchas operaciones sencillas requieren una gran
cantidad de instrucciones para ser llevadas a cabo.
Para evitar repetir siempre lo mismo y simplificar la escritura y lectura de programas, podemos
definir macros. Una macro no es más que una sucesión de instrucciones para las cuales
definimos una notación particular.
Por ejemplo, supongamos que en un programa queremos poner una variable 𝑉 en 0. Esto
podemos hacerlo combinando un loop con un decremento: mientras el valor de 𝑉 no sea 0,
reducimos dicho valor en 1. Por lo tanto, podemos definir la siguiente macro:
𝑉 = 0: while 𝑉 ≠ 0 do {
𝑉 −−
}
Un programa definido mediante el uso de macros recibe el nombre de pseudo-programa.
Todo pseudo-programa tiene un programa equivalente, que se obtiene expandiendo todas las
macros que aparecen en el mismo, es decir, reemplazándolas por el código correspondiente.
Por ejemplo, el pseudo-programa:
𝑌 =0
𝑌 ++
que computa la función constante 1, se corresponde con el siguiente programa:
while 𝑌 ≠ 0 do {
𝑌 −−
}
𝑌 ++
En ocasiones puede ser necesario utilizar variables auxiliares dentro de una macro. En ese caso
es importante indicar que dichas variables deben ser frescas, es decir, al expandir la macro
deben ser reemplazadas por una variable del tipo 𝑍𝑖 que no haya sido usada en ningún otro
lugar del programa (esto siempre es posible, porque existen infinitas variables del tipo 𝑍𝑖 ). Al
definir una macro, usaremos la convención 𝑍𝑛 , 𝑍𝑛′ , 𝑍𝑛″ , … para indicar las variables auxiliares
que deben ser frescas.
Ejercicio 1. Dar una macro para la pseudo-instrucción
𝑉1 = 𝑉2
que copia el valor de la variable 𝑉2 a la variable 𝑉1 .
3
Lenguajes Formales, Autómatas y Computabilidad Funciones computables
Solución.
𝑉1 = 𝑉2 : // Ponemos 𝑉1 en 0
𝑉1 = 0
// Pasamos el valor de 𝑉2 a una variable auxiliar fresca
while 𝑉2 ≠ 0 do {
𝑍𝑛 ++
𝑉2 −−
}
// Pasamos el valor de la variable auxiliar a 𝑉1 y restauramos 𝑉2
while 𝑍𝑛 ≠ 0 do {
𝑉1 ++
𝑉2 ++
𝑍𝑛 −−
}
Notar que en esta macro 𝑍𝑛 es una variable auxiliar fresca, mientras que 𝑉1 y 𝑉2 son
“parámetros” de la macro que deben instanciarse en variables concretas al usarla dentro de
un pseudo-programa.
Para el resto de la clase, consideraremos como dadas también a las siguientes macros, cuya
definición se pide en el ejercicio 1 de la práctica 8:
𝑉 = 𝑉 +𝑘 Suma 𝑘 al valor de la variable 𝑉
𝑉 =𝑘 Asigna el valor 𝑘 (constante) a la variable 𝑉
𝑉1 = 𝑉1 + 𝑉2 Suma el valor de la variable 𝑉2 al valor de la variable 𝑉1
if 𝑉 ≠ 0 then { Si la variable 𝑉 es distinta de 0, ejecuta el programa 𝑃
𝑃
}
if 𝑉 ≠ 0 then { Si la variable 𝑉 es distinta de 0, ejecuta el programa 𝑃1 , y en caso
𝑃1 contrario ejecuta el programa 𝑃2
} else {
𝑃2
}
loop Entra en un ciclo infinito
(𝑛)
𝑉 = Ψ𝑃 (𝑉1 , …, 𝑉𝑛 ) Si el programa 𝑃 termina al tomar como entrada los valores de
𝑉1 , …, 𝑉𝑛 , asigna el resultado de su ejecución a la variable 𝑉 ; en
caso contrario, se cuelga
Ejercicio 2.
a. Exhibir un pseudo-programa 𝑃 en el lenguaje 𝒮++ que compute la función ∗ : ℕ2 →
ℕ definida por ∗ (𝑥, 𝑦) = 𝑥 ⋅ 𝑦.
b. Sea 𝑄 el programa en 𝒮++ obtenido a partir de 𝑃 . Caracterizar las siguientes
funciones:
(1) (2) (3)
i. Ψ𝑄 : ℕ → ℕ ii. Ψ𝑄 : ℕ2 → ℕ iii. Ψ𝑄 : ℕ3 → ℕ
4
Lenguajes Formales, Autómatas y Computabilidad Funciones computables
Solución.
a. Para resolver este ejercicio, vamos a asumir que contamos con las siguientes macros:
• 𝑉1 = 𝑉2 , que asigna el valor de 𝑉2 a la variable 𝑉1 ,
• 𝑉1 = 𝑉1 + 𝑉2 , que suma a la variable 𝑉1 el valor de la variable 𝑉2 .
La idea del programa es simplemente sumar 𝑋2 veces el valor de 𝑋1 a la variable 𝑌 :
𝑃: 𝑍1 = 𝑋2
while 𝑍1 ≠ 0 do {
𝑌 = 𝑌 + 𝑋1
𝑍1 −−
}
El programa también sería válido si en vez de copiarse el valor de 𝑋2 en la variable
𝑍1 , se lo modicara directamente. Sin embargo, escribir programas que respeten sus
entradas tiene la ventaja de que es más sencillo reutilizarlos como macros.
(1)
b. i. Ψ𝑄 (𝑥) indica el valor computado por 𝑄 cuando la variable de entrada 𝑋1 toma
el valor 𝑥, y el resto de las variables de entrada el valor 0. Siguiendo el código,
(1)
es sencillo ver que para todo 𝑥 vale que Ψ𝑄 (𝑥) = 0.
(2)
ii. Ψ𝑄 (𝑥, 𝑦) indica el valor computado por 𝑄 cuando las variables de entrada 𝑋1 y
𝑋2 toman los valores 𝑥, 𝑦 respectivamente, y el resto de las variables de entrada
(2)
el valor 0. En este caso, Ψ𝑄 (𝑥, 𝑦) = 𝑥 ⋅ 𝑦.
(3)
iii. Ψ𝑄 (𝑥, 𝑦, 𝑧) indica el valor computado por 𝑄 cuando las variables de entrada
𝑋1 , 𝑋2 y 𝑋3 toman los valores 𝑥, 𝑦, 𝑧 respectivamente, y el resto de las variables
de entrada el valor 0. Como el valor de 𝑋3 no se utiliza en el programa, el
(3)
comportamiento es similar al caso anterior, es decir, Ψ𝑄 (𝑥, 𝑦, 𝑧) = 𝑥 ⋅ 𝑦.
2. Funciones y lenguajes computables
2.1. Funciones computables y parcialmente computables
Dada una función 𝑓 : ℕ𝑛 → ℕ, diremos que:
• 𝑓 es 𝒮++-parcialmente computable, o simplemente parcialmente computable, si existe
(𝑛)
algún programa 𝑃 tal que 𝑓 = Ψ𝑃 .
• 𝑓 es 𝒮++-computable, o simplemente computable, si es parcialmente computable y
además es total, es decir, 𝑓(𝑥1 , …, 𝑥𝑛 ) ↓ para cualesquiera 𝑥1 , …, 𝑥𝑛 .
Cabe señalar (y esto al principio puede ser un poco confuso) que todas las funciones compu-
tables son parcialmente computables (pero no al revés).
2.2. Composición de funciones computables
En general, si sabemos que una función 𝑓 : ℕ𝑛 → ℕ es parcialmente computable, será aceptable
utilizar en nuestros programas la pseudo-instrucción:
𝑉 = 𝑓(𝑉1 , …, 𝑉𝑛 )
cuyo efecto es:
• si 𝑓 está definida para los valores de las variables 𝑉1 , …, 𝑉𝑛 , asigna su valor a la variable
𝑉,
• si 𝑓 no está definida para estos valores, hace entrar al programa en un ciclo infinito.
5
Lenguajes Formales, Autómatas y Computabilidad Funciones computables
Esto es posible porque, si 𝑓 es parcialmente computable, debe existir un programa 𝑃 tal que
(𝑛)
𝑓 = Ψ𝑃 , y como vimos antes, podemos definir una macro que ejecute dicho programa y asigne
el valor de su salida a la variable 𝑉 .
2.3. Funciones primitivas recursivas
Es posible demostrar que toda función primitiva recursiva es computable. Esto es un
ejercicio de la guía y los detalles de la demostración se los dejamos a ustedes, pero la idea
general es usar inducción estructural: por un lado, mostramos que las funciones iniciales son
computables (dando los programas en 𝒮++ correspondientes), y por otro lado, mostramos que
las dos formas posibles de combinar funciones primitivas recursivas (composición y recursión
primitiva) pueden llevarse a cabo también en 𝒮++ combinando programas.
Este resultado nos brinda una enorme paleta de funciones que ya sabemos computables, y que
podemos usar sin problemas a la hora de definir programas en 𝒮++.
2.4. Lenguajes computables
Consideremos un alfabeto Σ, y un lenguaje ℒ ⊆ Σ∗ . Decimos que ℒ es un lenguaje compu-
table si, considerando una codificación de cadenas Σ∗ → ℕ (por ejemplo, la función 𝜌Σ definida
en el ejercicio 13 de la práctica 7), su predicado característico
1 si la cadena codificada por 𝑥 pertenece a ℒ
𝑝ℒ (𝑥) = {
0 si no
es computable.
Ejercicio 3. Demostrar que el siguiente lenguaje es computable:
ℒ = {𝑎𝑛 𝑏2𝑛 | 𝑛 ≥ 0}.
Solución. Como vimos en la práctica 7, las funciones cabezaΣ y colaΣ , que nos permiten
separar una cadena en su primer carácter y el resto, son primitivas recursivas. Usando estas
funciones, podemos definir un programa que itere sobre los caracteres de una cadena:
𝑍1 = 𝑋1
𝑍2 = cabezaΣ (𝑍1 )
while 𝑍2 == #Σ (𝑎) do {
𝑍3 ++
𝑍1 = colaΣ (𝑍1 )
𝑍2 = cabezaΣ (𝑍1 )
}
while 𝑍2 == #Σ (𝑏) do {
𝑍4 ++
𝑍1 = colaΣ (𝑍1 )
𝑍2 = cabezaΣ (𝑍1 )
}
if 𝑍1 == 𝜌Σ (𝜆) ∧ 2 ⋅ 𝑍3 = 𝑍4 then {
𝑌 =1
}
El primer ciclo recorre la cadena mientras encuentre el carácter 𝑎, y va contando las
apariciones en la variable 𝑍3 . El segundo ciclo hace lo propio con el carácter 𝑏 en la variable
𝑍4 . Por último, se verifica que se hayan recorrido todos los caracteres de la cadena y que se
6
Lenguajes Formales, Autómatas y Computabilidad Funciones computables
cumpla la igualdad pedida, es decir, que la cantidad de apariciones de 𝑏 sea el doble que la
de apariciones de 𝑎. Solo en este caso, se almacena el valor 1 en la variable 𝑌 , convirtiéndose
en la salida del programa. En caso contrario, se devuelve el valor por defecto de la variable
𝑌 , que es 0.
Solución alternativa. Otra posibilidad para llegar a una demostración es combinar los
conceptos aprendidos en guías anteriores con los resultados teóricos que aparecen más
arriba.
Por ejemplo, en la guía 6 vimos cómo definir gramáticas libres de contexto. Para el lenguaje
de este ejercicio, podemos generarlo con la gramática 𝐺 = ⟨𝑉𝑁 , 𝑉𝑇 , 𝑃 , 𝑆⟩, donde 𝑃 :
S → 𝑎S𝑏𝑏 | 𝜆
Claramente, la gramática 𝐺 no es recursiva a izquierda, y en el ejercicio 15 de la guía 7
vimos que los lenguajes generados por gramáticas libres de contexto que no sean recursivas
a izquierda son primitivos recursivos. Como además, sabemos que todas las funciones
primitivas recursivas son computables, concluimos que necesariamente el lenguaje ℒ debe
ser computable.
3. Codificación de programas
En la clase anterior, vimos que podemos codificar distintos tipos de elementos como números
naturales, poniéndolos en biyección con el conjunto ℕ. Vimos también que nos interesa encon-
trar codificaciones tales que sus observadores básicos, y otras operaciones comunes, resulten
primitivas recursivas.
Dado que los programas de 𝒮++ son estructuras finitas, también podemos definir formas
de codificarlos como números naturales. Más aún, podemos dar una codificación canónica
utilizando las funciones codificadoras de pares y de listas que vimos en la clase anterior.
Comenzaremos por dar una forma de codificar las instrucciones. Si 𝐼 es una instrucción de
𝒮++, definimos su código #(𝐼) como:
⟨𝑎, 𝑏⟩ + 1 si 𝐼 ≠ pass
#(𝐼) = {
0 si no
donde ⟨•, •⟩ : ℕ2 → ℕ es la función codificadora de pares, y:
• 𝑎 = #(𝑉 ), siendo 𝑉 la variable mencionada en 𝐼, de forma que:
‣ #(𝑌 ) = 0
‣ #(𝑋𝑖 ) = 2𝑖 − 1
‣ #(𝑍𝑖 ) = 2𝑖
• el valor de 𝑏 es:
‣ 0 si 𝐼 es un incremento.
‣ 1 si 𝐼 es un decremento.
‣ #(𝑃 ) + 2 si 𝐼 es un loop cuyo cuerpo es 𝑃 .
Como los programas no son otra cosa que listas de instrucciones, podemos codificarlos usando
la función codificadora de listas. Dado 𝑃 , un programa de 𝒮++, definimos su número de Gödel
#(𝑃 ) de la siguiente forma:
#(𝑃 ) = [#(𝐼1 ), #(𝐼2 ), …, #(𝐼𝑘 )]
7
Lenguajes Formales, Autómatas y Computabilidad Funciones computables
donde [•, …, •] : ℕ∗ → ℕ es la función codificadora de listas, y 𝐼1 , 𝐼2 , …, 𝐼𝑘 son las instrucciones
de 𝑃 .
Dado 𝑒 ∈ ℕ, usamos la notación Φ(𝑛) 𝑛
𝑒 : ℕ → ℕ para denotar la función computada por el
programa cuyo número es 𝑒, con 𝑛 entradas. Es importante confundir las notaciones Ψ(𝑛) y
(𝑛)
Φ(𝑛) . Si 𝑒 = #(𝑃 ), entonces Φ(𝑛)
𝑒 = Ψ𝑃 .
Ejercicio 4. Decimos que un programa es peligroso cuando contiene alguna instrucción
de la forma while 𝑉 ≠ 0 do { 𝑃 } (donde 𝑉 es una variable y 𝑃 un programa) tal que el
programa 𝑃 no contiene la instrucción 𝑉 −−, ni de forma directa ni dentro del cuerpo de
un loop.
Demostrar que el siguiente predicado es primitivo recursivo:
1 si el programa cuyo número es 𝑥 es peligroso
𝑝(𝑥) = {
0 si no.
Solución. La idea del ejercicio es “decodificar” el programa cuyo número el predicado
recibe por parámetro, para así poder analizar sus instrucciones. Sabemos que si el programa
con número 𝑥 consiste en las instrucciones 𝐼1 , 𝐼2 , …, 𝐼𝑘 , entonces 𝑥 satisface
𝑥 = [#(𝐼1 ), #(𝐼2 ), …, #(𝐼𝑘 )].
Podríamos resolver el problema analizando los códigos de cada una de estas instrucciones
y verificando si alguna de ellas cumple la condición que hace peligroso al programa.
Digamos que una instrucción es peligrosa si es un loop tal que, si 𝑉 es la variable que aparece
en la condición, la instrucción 𝑉 −− no aparece en el cuerpo. Si pudiéramos demostrar que
el predicado
1 si la instrucción codificada por 𝑥 es peligrosa
𝑝̃(𝑥) = {
0 si no
es primitivo recursivo, podríamos reescribir 𝑝 como:
𝑝(𝑥) = ∃1≤𝑡≤|𝑥| (̃
𝑝(𝑥[𝑡])).
Al tratarse de la composición de un existencial acotado y funciones que ya demostramos
(en la guía anterior) que son primitivas recursivas (la función observadora de listas • [•]
y su longitud |•|), el hecho de que 𝑝̃ sea primitivo recursivo implica directamente que 𝑝
también lo es.
Analicemos, entonces, el predicado 𝑝̃ con más detalle. Sabemos que las instrucciones de un
programa se codifican de la forma
⟨𝑎, 𝑏⟩ + 1
donde 𝑎 codifica la variable mencionada en la instrucción y 𝑏 el tipo de instrucción.
Esto quiere decir que, si 𝑥 > 0 es el código de una instrucción, podemos conocer su tipo
mirando el valor de 𝑏 (mediante la función observadora 𝑟(𝑥 − 1)), y cuál es la variable
mencionada mirando el valor de 𝑎 (mediante la función observadora 𝑙(𝑥 − 1)). Para simpli-
ficar la notación, vamos a definir las funciones auxiliares (primitivas recursivas):
• tipo(𝑥) = 𝑟(𝑥 − 1), que nos da el tipo de la instrucción codificada por 𝑥,
8
Lenguajes Formales, Autómatas y Computabilidad Funciones computables
• var(𝑥) = 𝑙(𝑥 − 1), que nos da el código de la instrucción codificada por 𝑥.
Para saber si la instrucción es un loop, basta con mirar el valor de tipo(𝑥). Sabemos que
la instrucción es de la forma
while 𝑉 ≠ 0 do {
𝑃
}
si 𝑥 > 0 ∧ tipo(𝑥) ≥ 2.
Resta comprobar que la variable 𝑉 no aparezca mencionada en ninguna de las instrucciones
de 𝑃 que sea un decremento. Por un lado, podemos obtener el código de 𝑉 como en cuyo
caso #(𝑉 ) = var(𝑥). La codificación del cuerpo del loop, por su parte, es #(𝑃 ) = tipo(𝑥) −
2, lo cual motiva definir una nueva función auxiliar:
cuerpo(𝑥) = tipo(𝑥) − 2,
que nos devuelve la codificación del cuerpo de un loop.
Usando todo lo anterior podemos definir el siguiente predicado:
{ si la instrucción codificada por 𝑥 es 𝑉 −−
{
{1 o un loop cuyo cuerpo contiene la instrucción 𝑉 −−,
decrementa(𝑥, 𝑦) = {
{ siendo 𝑦 = #(𝑉 )
{0 si no
{
Este predicado es primitivo recursivo, ya que podemos escribirlo como:
decrementa(𝑥, 𝑦) = 𝑥 > 0 ∧ ((tipo(𝑥) == 1 ∧ var(𝑥) == 𝑦) ∨
(tipo(𝑥) ≥ 2 ∧ ∃1≤𝑡≤|cuerpo(𝑥)| (decrementa(cuerpo(𝑥)[𝑡], 𝑦)))).
Aquí tenemos una combinación de funciones primitivas recursivas que utiliza composi-
ción y recursión global,² ya que para definir decrementa(𝑥, 𝑦) utilizamos los valores de
decrementa(cuerpo(𝑥)[𝑡], 𝑦) para 𝑡 = 1, …, |cuerpo(𝑥)| y por cómo están definidas la codifi-
caciones de pares y de listas, sabemos que
cuerpo(𝑥)[𝑡] = (𝑟(𝑥 − 1) − 2)[𝑡] < 𝑥,
es decir, el argumento de la llamada recursiva del predicado es estrictamente menor que el
valor para el cual que se lo está queriendo definir.³
Combinando todo lo anterior, podemos escribir al predicado 𝑝̃ de la siguiente forma:
𝑝̃(𝑥) = 𝑥 > 0 ∧ tipo(𝑥) ≥ 2 ∧ ¬(∃1≤𝑡≤|cuerpo(𝑥)| (decrementa(cuerpo(𝑥)[𝑡], var(𝑥))))
donde verificamos que la instrucción codificada por 𝑥 sea un loop (𝑥 > 0 ∧ tipo(𝑥) ≥ 2)
y, usando el predicado definido antes, que no exista una instrucción en su cuerpo que
decremente (de forma directa o indirecta) la variable cuyo código es var(𝑥). Con argumentos
²Llamamos recursión global a una forma de recursión donde para definir el valor de 𝑓(𝑡, 𝑥1 , …, 𝑥𝑛 ) puede
usarse cualquiera de los valores 𝑓(0, 𝑥1 , …, 𝑥𝑛 ), 𝑓(1, 𝑥1 , …, 𝑥𝑛 ), …, 𝑓(𝑡 − 1, 𝑥1 , …, 𝑥𝑛 ). Damos aquí por demos-
trado (es un ejercicio interesante) que toda función que puede definirse utilizando recursión global puede
definirse también utilizando recursión primitiva.
³Para convencerse de esto, tener en cuenta que para todo 𝑥, 𝑡, se cumple que 𝑟(𝑥) ≤ 𝑥 y 𝑥[𝑡] ≤ 𝑥.
9
Lenguajes Formales, Autómatas y Computabilidad Funciones computables
similares a los que usamos antes, esta escritura muestra que 𝑝̃ es primitivo recursivo,
concluyendo la demostración.
4. Snap, Step y programa universal
4.1. Configuración instantánea y la función Snap
Dado un programa 𝑃 , 𝑛 ∈ ℕ, y valores 𝑥1 , …, 𝑥𝑛 ∈ ℕ para las variables de entrada, podemos
pensar en la ejecución del mismo como una serie de pasos de cómputo. En cada paso, se
ejecuta una instrucción y se modifica el estado del cómputo. Dado un momento del tiempo,
podemos representar el estado del cómputo mediante la configuración instantánea del
programa, que tiene dos componentes fundamentales:
1. La instrucción que toca ejecutar en el próximo paso. La representamos como una lista
[𝑖1 , …, 𝑖𝑘 ] donde:
• 𝑖1 es el índice de la instrucción de 𝑃 que toca ejecutar a continuación,
• si la instrucción 𝑖1 -ésima de 𝑃 es un loop, 𝑖2 es el índice de la instrucción dentro del
loop que toca ejecutar a continuación, y así sucesivamente.
Por ejemplo, en el siguiente programa
𝑍1 ++
while 𝑋1 ≠ 0 do {
𝑍1 ++
𝑋1 −−
}
si la próxima instrucción a ejecutar es 𝑋1 −− dentro del loop, esto será indicado mediante
la lista [2, 2].
Si la ejecución del programa ya terminó, entonces este valor será una lista con un único
elemento, y este elemento será la cantidad de instrucciones del programa más uno.
2. Los valores de cada una de las variables. Estos también serán representados mediante
una lista, en el orden 𝑌 , 𝑋1 , 𝑍1 , 𝑋2 , 𝑍2 , 𝑋3 , 𝑍3 , …, hasta la última variable cuyo valor sea
distinto de cero.
De esta forma, la configuración instantánea de un programa puede pensarse como un par de
números naturales ⟨𝑎, 𝑏⟩, donde 𝑎 es la lista que representa la próxima instrucción a ejecutar y
𝑏 la lista de los valores de las variables. Es decir, la configuración instantánea es representable
como un número natural mediante las funciones codificadoras que ya conocemos.
Definimos la función Snap(𝑛) : ℕ𝑛+2 → ℕ de modo que si 𝑒 = #(𝑃 ), entonces
Snap(𝑛) (𝑡, 𝑒, 𝑥1 , …, 𝑥𝑛 ) codifica la configuración instantánea del programa 𝑃 , con entradas
𝑥1 , …, 𝑥𝑛 , transcurridos 𝑡 pasos de su ejecución. Es posible demostrar (no lo haremos acá) que,
para todo 𝑛 ∈ ℕ, la función Snap(𝑛) es primitiva recursiva.
4.2. El predicado Step
Definimos el predicado Step(𝑛) : ℕ𝑛+2 → {0, 1} de forma tal que, si 𝑒 = #(𝑃 ), entonces:
{ si la ejecución de 𝑃 con entradas 𝑥1 , …, 𝑥𝑛
(𝑛)
{1
Step (𝑡, 𝑒, 𝑥1 , …, 𝑥𝑛 ) = { finaliza tras 𝑡 o menos pasos de ejecución
{0 en caso contrario.
{
10
Lenguajes Formales, Autómatas y Computabilidad Funciones computables
El valor de Step(𝑛) puede ser obtenido a partir de Snap(𝑛) de una forma bastante sencilla4 y,
por lo tanto, se puede mostrar que también es primitivo recursivo.
4.3. Programa universal
Contando con los predicados Snap(𝑛) y Step(𝑛) , podemos definir un programa en 𝒮++ que,
dado el número de otro programa, simule la ejecución del mismo para determinadas entradas.
Escrito en forma de pseudo-programa, el mismo podría ser de la pinta:
(𝑛)
Φ𝑋1 (𝑋2 , …, 𝑋𝑛+1 ): 𝑍2 = 1
while 𝑍2 ≠ 0 do {
// 𝑍2 es 0 si la ejecución ya terminó y 1 si no
𝑍2 = ¬Step(𝑛) (𝑍1 , 𝑋1 , 𝑋2 , …, 𝑋𝑛+1 )
// 𝑍1 contiene la cantidad de pasos de ejecución transcurridos
𝑍1 ++
}
𝑌 = 𝑟(Snap(𝑛) (𝑍1 , 𝑋1 , 𝑋2 , …, 𝑋𝑛+1 ))[1]
Las consecuencias de que sea posible hacer esto son sumamente interesantes y las seguiremos
explorando en profundidad en la próxima clase.
Ejercicio 5. Demostrar que la siguiente función es parcialmente computable.
{
{1 si la ejecución de Φ(1)
𝑥 (𝑧) termina estrictamente en
𝑓(𝑥, 𝑦, 𝑧) = { menos pasos que la ejecución de Φ(1)
𝑦 (𝑧)
{↑ en caso contrario.
{
Aclaración: Si para determinada entrada un programa no termina, consideramos que su
ejecución tiene infinitos pasos.
Solución. Construyamos un programa en 𝒮++ que compute 𝑓. La idea es utilizar el
predicado Step(1) para “seguir el rastro” del programa cuyo número es 𝑥, y así descubrir
cuántos pasos tarda en terminar de ejecutar, si es que en algún momento lo hace. Luego,
podemos usar nuevamente Step(1) para averiguar si el programa con número 𝑦 termina de
ejecutar en una cantidad menor o igual de pasos. Nuestro programa debe devolver 1 si esto
último resulta ser falso, y colgarse en caso contrario.
Como el predicado Step(1) es primitivo recursivo, también es computable, así que podemos
usarlo directamente dentro de nuestros programas (por supuesto, teniendo presente que en
rigor se trata de una macro que debería ser expandida para obtener un programa válido).
Un posible programa en 𝒮++ es el siguiente:
4 ¿Cómo? Pensarlo un momento.
11
Lenguajes Formales, Autómatas y Computabilidad Funciones computables
𝑃: while 𝑍1 == 0 do {
𝑍1 = Step(1) (𝑍2 , 𝑋1 , 𝑋3 )
𝑍2 ++
}
𝑍2 −−
𝑍3 = Step(1) (𝑍2 , 𝑋2 , 𝑋3 )
if 𝑍3 ≠ 0 then {
loop
} else {
𝑌 =1
}
El primer ciclo del programa va incrementando el valor de 𝑍2 hasta encontrar una cantidad
de pasos tras la cual el programa 𝑋1 termine para la entrada 𝑋3 . Si el programa 𝑋1 se
cuelga para la entrada 𝑋3 , este ciclo nunca termina, lo cual es correcto. En cambio, si
el ciclo termina, el valor final de 𝑍2 es la cantidad de pasos tras los cuales el programa
termina más uno. Por eso, acto seguido, decrementamos 𝑍2 para obtener la cantidad de
pasos exacta.
Acto seguido, usamos nuevamente Step(1) para verificar si tras esta cantidad de pasos,
el programa 𝑋2 también terminó para la entrada 𝑋3 . En caso afirmativo, el valor de 𝑍3
pasará a ser 1, con lo cual nuestro programa entrará en un loop infinito; de lo contrario,
finalizaremos la ejecución devolviendo el valor 1.
Solución alternativa. Otra posibilidad, en vez de dar explícitamente un programa en
𝒮++, es demostrar primero un resultado un poco más general, que nos será útil en otros
ejercicios de este tipo. Se trata de la siguiente afirmación: si 𝑝 : ℕ𝑛 → {0, 1} es un predicado
computable, entonces el existencial no acotado sobre este predicado:
1 si existe 𝑡 tal que 𝑝(𝑡, 𝑥1 , …, 𝑥𝑛 ) = 1
∃𝑡 (𝑝(𝑡, 𝑥1 , …, 𝑥𝑛 )) = {
↑ en caso contrario.
es una función parcialmente computable.
Podemos demostrar esta afirmación escribiendo un sencillo programa en 𝒮++ que vaya
recorriendo los valores posibles de 𝑡 y evaluando para cada uno de ellos el predicado.
while 𝑍1 == 0 do {
𝑍1 = 𝑝(𝑋1 , …, 𝑋𝑛 , 𝑍2 )
𝑍2 ++
}
𝑌 =1
Es importante tener en cuenta que, para que este programa sea válido, el predicado 𝑝 debe
ser total. En caso contrario, la ejecución podría quedar atrapada en el cómputo de 𝑝 para
algún valor de 𝑡 e indenir el existencial, incluso aunque 𝑝 sea verdadero para otro valor de
𝑡 que no todavía no hayamos vericado.
Una vez que contamos con el existencial, si encontramos un predicado apropiado, podemos
usarlo para reescribir 𝑓. Al igual que en la solución anterior, intentemos aprovechar el
predicado Step(1) , que ya sabemos primitivo recursivo. Las siguientes son dos condiciones
necesarias para que 𝑓(𝑥, 𝑦, 𝑧) = 1:
12
Lenguajes Formales, Autómatas y Computabilidad Funciones computables
(i) El programa con número 𝑥 termina para la entrada 𝑧. Es decir, debe existir algún
𝑡 ∈ ℕ tal que Step(1) (𝑡, 𝑥, 𝑧) sea verdadero.
(ii) El programa con número 𝑦, para la entrada 𝑧, no termina antes ni al mismo tiempo que
el programa 𝑥 para la misma entrada. Equivalentemente, debe existir algún tiempo
𝑡 para el cual el programa 𝑥 ya haya terminado, pero el programa 𝑧 todavía no; o,
más formalmente, existe algún 𝑡 ∈ ℕ que cumple Step(1) (𝑡, 𝑥, 𝑧) ∧ ¬Step(1) (𝑡, 𝑦, 𝑧).
Dado que (ii) implica (i), solo tendremos en cuenta la última condición.
Es sencillo advertir que (ii) también es condición suciente para que 𝑓(𝑥, 𝑦, 𝑧) = 1. En caso
contrario, o bien la ejecución de Φ(1)
𝑥 (𝑧) no termina o, para todo 𝑡 tal que la ejecución de
Φ(1)
𝑥 (𝑧) termina en 𝑡 o menos pasos, la ejecución de Φ(1)
𝑦 (𝑧) también termina en 𝑡 o menos
pasos. En cualquiera de estas dos situaciones, 𝑓(𝑥, 𝑦, 𝑧) ↑.
Por lo tanto, podemos reescribir
𝑓(𝑥, 𝑦, 𝑧) = ∃𝑡 (Step(1) (𝑡, 𝑥, 𝑧) ∧ Step(1) (𝑡, 𝑦, 𝑧))
donde el predicado al que hace referencia el existencial es primitivo recursivo y, por lo tanto,
computable (total), de donde se sigue que 𝑓 es parcialmente computable.
Referencias
[1] A. Turing, «On Computable Numbers, with an Application to the Entscheidungsproblem»,
Proceedings of the London Mathematical Society, n.º 1, pp. 230-265, 1937, [En línea].
Disponible en: https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
[2] J. E. Hopcroft, R. Motwani, y J. D. Ullman, «Chapter 8: Introduction to Turing Machines»,
en Introduction to Automata Theory, Languages, and Computation, 3.ª ed., Addison-
Wesley, 2006, pp. 315-376.
[3] M. Davis, R. Sigal, y E. J. Weyuker, «Chapter 2: Programs and Computable Functions»,
en Computability, Complexity, and Languages: Fundamentals of Theoretical Computer
Science, 2.ª ed., Academic Press, 1994, pp. 17-38.
[4] M. Davis, R. Sigal, y E. J. Weyuker, «Chapter 4: A Universal Program», en Computability,
Complexity, and Languages: Fundamentals of Theoretical Computer Science, 2.ª ed.,
Academic Press, 1994, pp. 65-112.
13
