Teorema de Forma Normal (Kleene).
Existen un predicado T(e, x, y) (llamado el predicado-T Kleene) y una función U(y) que son recursivos (en efecto, recursión primitiva) tal que:
Explicación.
El predicado T es una relación que depende de la numeración de Gödel. Recordemos que dado un conjunto enumerable S, una enumeración de Gödel es una función:
donde f y su inversa (f ^(−1) ) son funciones computables.
Las funciones computables son aquellas funciones que pueden ser calculadas por una maquina de Turing.
Informalmente, el predicado T(e, x, y) afirma que y es el número código de alguna computación de Turing de acuerdo a un programa de Turing Pe con entrada x.
Un numero de código asignado a P_e esta dado por la siguiente función:
(1)
Para entender qué significa la expresión anterior, debemos remontarnos a cómo funciona una máquina de Turing la cual encontraremos clickeando en la siguiente imagen relacionada.
Sea M una máquina de Turing, suponga que esta máquina tiene una cinta de dos caminos infinitos divididas en celdas, un lector que escanea una celda de la cinta a la vez, y un conjunto finito de estados internos. Cada celda puede tener el símbolo ␣ o tener un símbolo s ∈ S. En un solo paso, la máquina puede simultáneamente:
i) cambiar de un estado a otro,
ii) cambiar el símbolo escaneado s por otro símbolo s'
teniendo en cuenta que s' ∈ S = {1, B}, y
iii) mover el lector una celda a la izquierda o derecha de
la cinta.
La operación de M es controlada por el mapeo parcial, el cual puede o no estar definido para algunos argumentos. La interpretación se puede entender pensando en que tenemos la quíntupla (q, s, q', s', X) ∈ δ, entonces la maquina M en estado q, escaneando el símbolo s cambia al estado q', reemplazando s por s' y moviendo el escaneo un cuadro a la derecha si X = R o a la izquierda si X = L.
Un programa de Turing P con entrada x es una secuencia de configuraciones, c_0, c_1, . . . , c_n tal que c_0 representa el máquina en el estado inicial q_1, leyendo el símbolo más a la izquierda de la entrada x, c_n representa a la máquina en el estado de halt q', y la transición c_i → c_{i+1} para todo i < n, viene dada por el programa de Turing P.
Cada configuración c_i se le asigna un número de cada (q_i, s_j, q'_k, s'_l, r_m), dicho número es obtenido por:
Así, obtenemos un conjunto enumerable con los números correspondientes de cada configuración c_0, c_1, . . . , c_n de P que llamaremos G, luego por enumeración de Gödel tenemos el conjunto G enumerable y por la función (1) , donde la productoria es de todos los números del conjunto G. Recordando que y es el número de código del programa P podemos concluir que también es un número de Gödel.
Volviendo al predicado T(e, x, y), T es una función total que satisface la siguiente propiedad: T(e, x, y) = 0 si y solo si e es la codificación de una máquina de Turing M tal que existe m ∈ N que es calculado por M con la entrada x en menos de q(y) pasos de cálculo, donde λyq(y) es una función recursiva primitiva fija, independiente de e, x e y.
En cierto sentido, la función T incorpora en su definición a la definición de la función q.
Ahora intentaremos definir de la forma más sencilla y compacta lo que es ser una función recursiva primitiva y una función parcial recursiva.
Partimos de que las funciones recursivas primitivas constituyen una clase muy grande de funciones computables que contienen casi todas las funciones en ω que se encuentran comúnmente en matemáticas.
Función recursiva primitiva:
La clase de funciones recursivas primitivas es la clase C más pequeña de funciones cerradas bajo los siguientes esquemas:
i. La función sucesora, λx[x + 1], está en C.
ii. Las funciones constantes, λx1 . . . xn[m], están en C, 0 ≤ n, m. iii. Las funciones de identidad (también llamadas proyecciones),
λx1 . . . xn [xi] , están en C, con 1 ≤ n y 1 ≤ i ≤ n.
iv. (Composición) Si g_1, g_2, . . . , g_m, h ∈ C, entonces:
está en C donde g_1, . . . , g_m son funciones de n variables y
h es una función de m variables.
v. (Recursión Primitiva) Si g, h ∈ C y n ≥ 1 entonces f ∈ C, donde:
Función parcial recursiva:
El conjunto de todas las funciones recursivas parciales es el conjunto más pequeño de funciones parciales, subconjunto de todas las uniones con k≥0 de N^k → N,
que incluye (1): (i) la función sucesora, (ii) las funciones cero, y (iii) las funciones de proyección y
(2) se cierra con respecto a las siguientes operaciones: (iv) composición, (v) recursividad primitiva.
Así en la expresión U(µy[T(e, x, y) = 0]) tenemos que para todo
e ≥ 0, U se define como la e-ésima función parcial recursiva de aridad 1. Cada función recursiva parcial de aridad 1 tiene infinitos índices, es decir por cada conjunto de funciones recursivas parciales sea ϕ : N → N existe un subconjunto infinito E de N tal que para todo e ∈ E tenemos que ϕ(x) = U( µy [T(e, x, y) = 0] )
Comments