PDF de programación - Programas Universales

Programas Universales

Dpto. Ciencias de la Computación e Inteligencia Artificial

Universidad de Sevilla

Lógica Matemática

Curso 2011–12

LM, 2011–12

Programas Universales 4.1

Codificación de programas

Nuestro siguiente objetivo es probar la existencia de

programas universales, es decir, programas GOTO capaces de
simular al ejecución de cualquier otro programa GOTO.
Para ello será necesario manejar programas de manera

efectiva, es decir, manejar los programas mediante programas.

Esto requiere la codificación de programas mediante

números.

Codificaremos las instrucciones GOTO utilizando la función

par .
G¨odel [ · ], usando la codificación de instrucciones previa.

Codificaremos los programas GOTO mediante la función de

LM, 2011–12

Programas Universales 4.2

Codificación de las Instrucciones (I)

Una instrucción consta básicamente de tres elementos:

Etiqueta,
Variable, y
Formato (o tipo) de la instrucción.

Codificación de las etiquetas:
Ordenamos las etiquetas: A1, B1, C1, D1, E1, A2, ..., E2, A3, ...E3, . . .
Asignamos un número a cada etiqueta como sigue:
#(Ak ) = 5(k − 1) + 1
#(Bk ) = 5(k − 1) + 2
#(Ck ) = 5(k − 1) + 3
#(Dk ) = 5(k − 1) + 4
#(Ek ) = 5k



(k ≥ 1) :

LM, 2011–12

Programas Universales 4.3

Codificación de las Instrucciones (II)

Codificación de las variables:
Ordenamos las variables: Y , X1, Z1, X2, Z2,··· y asignamos un
número a cada variable según este orden:

 #(Y ) = 1

(k ≥ 1)
#(Xk ) = 2k
#(Zk ) = 2k + 1 (k ≥ 1)



Codificación del Formato:

si el formato es V ←− V
si el formato es V ←− V + 1
si el formato es V ←− V − 1

0
1
2
#(L) + 2 si el formato es IF V = 0 GOTO L

LM, 2011–12

Programas Universales 4.4

Codificación de las Instrucciones (III)

Sea I una instrucción GOTO. Definimos su código #(I ) como:

#(I ) = a,b, c

siendo:

a =

#(L)

0


b = C ódigo del formato de I

si I no tiene etiqueta
si I tiene etiqueta L
si formato V ←− V
si formato V ←− V + 1
si formato V ←− V − 1

0
1
2
#(L) + 2 si formato IF V = 0 GOTO L

c = #(V ) − 1
si V es la variable de I .
Todo n ∈ N codifica una única instrucción.

LM, 2011–12

Programas Universales 4.5

Codificación de los Programas

Sea P = (I1, I2, . . . , In). Definimos:

#(P) = [#(I1), #(I2), . . . , #(In)] − 1

Si P∅ es el programa vacío, #(P∅) = [ε] − 1 = 0
Puesto que #(Y ←− Y ) = 0,0, 0 = 0 y

[a1, ..., an] = [a1, ..., an, 0, ..0], se tiene:

[#(I1), ..., #(In)] = [#(I1), ..., #(In), #(Y ←− Y ), ..., #(Y ←− Y )]

y, por tanto, la codificación no sería inyectiva si los programas
GOTO pudiesen terminar con la instrucción Y ←− Y . Por
eso no se permite que dicha instrucción sea la última.

Lema. Todo n ∈ N codifica un único programa GOTO.

LM, 2011–12

Programas Universales 4.6

Codificación de las d.i.

Para describir la computación de P sobre x codificaremos
numéricamente las descripciones instantáneas.

Codificación de descripciones instantáneas.
Estados: Dado el estado σ = {V1 = r1, V2 = r2, ..., Vn = rn},

con #(Vi ) = i, definimos el código de σ así:

#(σ) = [r1, ..., rn]

Descripciones instantáneas: Sea (i, σ) una d.i. Definimos

su código como:

#(i, σ) = i, #(σ)

LM, 2011–12

Programas Universales 4.7

Programas universales

Sean P ∈ GOTO y x ∈ Nn. ¿Es computable la función:

(x, #(P)) → [[P]](n)(x)?

Un programa que calcule esta función se denomina programa
universal. Si fijamos la aridad y designamos por Un a dicho
programa, tendremos:

[[Un]](n+1)(x, #(P)) = [[P]](n)(x)

Esencialmente, un programa universal es un intérprete de GOTO,
que simula la ejecución del programa P sobre la tupla x que recibe
como entrada.

LM, 2011–12

Programas Universales 4.8

Programas universales (II)

Teorema. Para cada n ≥ 1, existe un programa Un tal que para
todo x ∈ Nn y todo programa GOTO, P, se tiene

[[Un]](n+1)(x, #(P)) = [[P]](n)(x)

Notación: Un = [[Un]](n+1).

LM, 2011–12

Programas Universales 4.9

El programa universal Un

 (1)



(3)

[C ]

[M]

S ←−n
IF K = Long (Z ) + 1 GOTO F (2)

Z ←− Xn+1 + 1
i=1(p2i )Xi
K ←− 1
U ←− r ((Z )k )
P ←− pr (U)+1
IF l(U) = 0 GOTO N
IF l(U) = 1 GOTO A
IF P S GOTO N
IF l(U) = 2 GOTO M
K ←− µi ≤ Long (Z )[l((Z )i ) + 2 = l(U)]
GOTO C
S ←− qt(S, P)
GOTO N
S ←− S·P
[A]
K ←− K + 1
[N]
GOTO C
[F ] Y ←− (S)1

 (4)

LM, 2011–12

Programas Universales 4.10

Descripción de Un

BLOQUE 1: Iniciación del programa Un

En Z guardamos la información acerca del programa P.
En S el estado actual
En K la siguiente instrucción que debe ejecutarse.
(Si K = k y S = s, el par (k, s) almacena una d.i.)

BLOQUE 2: Test de salida.

Un para cuando lleguemos a una d.i. de P terminal. Como la
longitud de P es |P| = Long (Z ), la instrucción de salida será:

IF K = Long (Z ) + 1 GOTO F

BLOQUE 3: Obtención del tipo de instrucción que debe

ejecutarse.

BLOQUE 4: Obtención de la nueva d.i.

LM, 2011–12

Programas Universales 4.11

Ejecución en tiempo limitado

Proposición. Para cada n ≥ 1 el predicado:
STEP (n)(x1, ..., xn, y , t) ≡
“El programa y para sobre (x1, ..., xn) en, a lo sumo, t pasos”.

es GOTO–computable.
Proposición. La función di (n) : Nn+2 → N, definida por:
di (n)(x, e, t) =
la t + 1–ésima d. i. de la computación del programa e sobre x

es GOTO–computable.

Si la computación del programa e sobre x para en menos de t
pasos, entonces di (n)(x, e, t) devuelve la d.i. terminal de dicha
computación.

Podemos probar ambos resultados sin más que modificar el

programa universal Un adecuadamente.

LM, 2011–12

Programas Universales 4.12

STEP (n) es GOTO–computable

S ←−Qn

i=1(p2i )Xi

9=; (1)

9=; (2)

Z ←− Xn+1 + 1
K ←− 1
IF K = Long (Z ) + 1 GOTO F
IF Xn+2 = 0 GOTO E
Xn+2 ←− Xn+2 − 1
U ←− r ((Z )k )
P ←− pr (U)+1
IF l(U) = 0 GOTO N
IF l(U) = 1 GOTO A
IF P S GOTO N
IF l(U) = 2 GOTO M
K ←− µi ≤ Long (Z )[l((Z )i ) + 2 = l(U)]
GOTO C
S ←− qt(S, P)
GOTO N
S ←− S·P
K ←− K + 1
GOTO C
Y ←− Y + 1

9>>>=>>>; (4)

9>>>>>>>>>=>>>>>>>>>;

(3)

[C ]

[M]

[A]
[N]

[F ]

LM, 2011–12

Programas Universales 4.13

La función di (n) es GOTO–computable

ff

(2)

(3)

9>>>>>>>>>=>>>>>>>>>;

9=; (1)

S ←−Qn

i=1(p2i )Xi

Z ←− Xn+1 + 1
K ←− 1
IF K = Long (Z ) + 1 ∨ Xn+2 = 0 GOTO F
Xn+2 ←− Xn+2 − 1
U ←− r ((Z )k )
P ←− pr (U)+1
IF l(U) = 0 GOTO N
IF l(U) = 1 GOTO A
IF P S GOTO N
IF l(U) = 2 GOTO M
K ←− µi ≤ Long (Z )[l((Z )i ) + 2 = l(U)]
GOTO C
S ←− qt(S, P)
GOTO N
S ←− S·P
K ←− K + 1
GOTO C
Y ←− K , S

9>>>=>>>; (4)

[C ]

[M]

[A]
[N]

[F ]

LM, 2011–12

Programas Universales 4.14

Índices

Para n ≥ 1 y e ∈ N,

la función GOTO–computable n-aria de índice e es la función
ϕ(n)
e

: Nn− −→ N, dada por

e (x) = Un(x, e)
ϕ(n)

Obsérvese que:

ϕ(n)
#(P) = [[P]](n).

Proposición. Sea n ≥ 1. La sucesión {ϕ(n)

: e ∈ N} es una

e

enumeración efectiva de GCOMP (n), es decir:
1. Para todo e ∈ N, ϕ(n)
2. Si f ∈ GCOMP (n), entonces existe e ∈ N tal que f = ϕ(n)
3. Existe Fn ∈ GCOMP (n+1) tal que para cada x ∈ Nn, e ∈ N,

e ∈ GCOMP (n)

e (x).

Fn(x, e) = ϕ(n)

e (x)

LM, 2011–12

Programas Universales 4.15