Logica Apunte Ltaravilse

Computabilidad

1

´Indice
1. Programas y funciones computables
1.1. El lenguaje S . . . . . . . . . . . . .
1.2. Programas de S . . . . . . . . . . .
1.3. Macros . . . . . . . . . . . . . . . . .
1.4. Estados y snapshots . . . . . . . . .
1.5. Funciones computables . . . . . . . .
1.6. Predicados . . . . . . . . . . . . . . .
2. Funciones primitivas recursivas
2.1. Composici´
on . . . . . . . .. . . .
2.2. Recursi´
on . . . . . . . . . . . . . .
2.3. Clases PRC . . . . . . . . . . . . .
2.4. Predicados primitivos recursivos .
2.5. Cuantificadores acotados . . . . . .
2.6. Minimalizaci´
on . . . . . . . . . . .
2.7. Codificaci´
on de pares y n´
umeros de

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

..
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

3
3
3
4
5
6
6

. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
G¨odel

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
..
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

7
7
7
8
8
8
9
9

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
..
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

10
10
10
11
12
12
12
13

.
.
.
.
.
.

3. Programas Universales
3.1.Codificaci´
on de programas . . . . . . .
3.2. El Halting Problem . . . . . . . . . . .
3.3. Teorema de Universalidad . . . . . . .
3.4. Conjuntos recursivamente enumerables
3.5. Teorema del Par´
ametro . . . . . . . .
3.6. El teorema de la recursi´
on . . . . . . .
3.7. Teorema de Rice . . . . . . . . . . . .

.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

2

1.

Programas y funciones computables1.1.

El lenguaje S

Definimos el lenguaje

S de la siguiente manera:

1. Las variables de entrada de
2. La variable de retorno de
3. Las variables locales de

S son {Xi }i∈N .

S es Y .

S son {Zi }i∈N .

4. Las variables de

S toman valores en N0 .

5. Las etiquetas de

S son A1 , B1 , C1 , D1 , E1 , A2 , B2 , C2 , D2 , E2 , A3 , . . .

6. Las instrucciones de

S son:

V ←V +1
V ←V −1
IF V = 0 GOTOL
donde V es una variable y L es una etiqueta. Las instrucciones pueden adem´as tener una etiqueta.
Veamos qu´e quiere decir cada una de estas afirmaciones y como funciona el lenguaje.
La primer afirmaci´
on dice que hay una variable de entrada por cada n´
umero natural, y que a la i-´esima
variable de entrada la llamamos Xi . Un programa de S que toma n variables de entrada comienza con
Xm = 0para todo m > n. La variable X1 es comunmente denominada X.
La segunda afirmaci´
on dice que todo programa del lenguaje S va a devolver el valor que tenga la variable
Y al finalizar la ejecuci´
on de la u
´ltima instrucci´on que ejecute el programa.
La tercer afirmaci´
on dice que cuando un programa de S use variables que no son parte de la entrada
(variables locales), estas ser´
an una por cadanatural y llamaremos Zi a la i-´esima variable local. Por
definici´
on empiezan todas con el valor 0.
La cuarta afirmaci´
on nos dice que los valores que pueden tomar las variables son los naturales y el cero (es
decir, enteros no negativos, o enteros mayores o iguales a cero). Al igual que lo que pasa con la variable
X1 , podemos llamarle Z a la variable Z1
La quinta afirmaci´
on nos dice que las...