Computadoras

Trabajo Práctico

Cátedra: Computación II.

López Gustavo.


Profesor: Adrian Colazo.

Año: 2012.






Índice:
Unidad Nº 4:

Números de código de Gödel …………………………………………………………Pag.3
Codificación de programas mediante números……………………………………...Pag.4
El problema de la parada………………………………………………………………Pag.5
Universalidad……………………………………………………………………………Pag.6
Conjuntos recursivamenteenumerables……………………………………………Pag.6
El teorema del parámetro……………………………………………………………..Pag.7
El segundo teorema de recursión……………………………………………………Pag.7
El teorema de Rice……………………………………………………………………..Pag.8

Unidad Nº5:

Representación de cadenas usando números…………………………………….Pag.9
Un lenguaje de programación para el cálculo con cadenas…………….……….Pag.9
Programas dePost-Turing………………………………………………………….Pag.10
Tesis de Church-Turing……………………………………………………………..Pag.10







Unidad Nº 4: Codificación de Programas. Programa Universal
Números de código de Gödel - Codificación de programas mediante números - El problema de la parada – Universalidad - Conjuntos recursivamente enumerables - El teorema del parámetro - El segundo teorema de recursión - El teorema de Rice.

Números de código de GÖDEL.
Gödel es un lenguaje deprogramación declarativo, de propósito general, adherido al paradigma de la programación lógica. Se le dio ese nombre en honor al lógico Kurt Gödel.
Gödel tiene un sistema de módulos; permite enteros y racionales de precisión arbitraria y números de punto flotante. Puede resolver restricciones sobre dominios finitos de enteros así como restricciones lineales racionales. Admite procesamiento de conjuntos finitos.Tiene también una regla flexible de cómputo que admite el operador de poda, que es una generalización del operadorcommit de los lenguajes de programación concurrentes.
Las facilidades metalógicas de Gödel dan cabida a metaprogramas que realizan análisis, transformación, compilación, verificación y puesta a punto, entre muchas otras tareas.
En teoría de los números un número de Gödel es unafunción que asigna a cada símbolo y fórmula de un lenguaje formal un número único, denominado Número de Gödel (GN). La enumeración de un conjunto de funciones computables se denomina también enumeración de Gödel o enumeración efectiva. Una enumeración de Gödel se puede interpretar como un lenguaje de programación donde los números de Gödel están asignados a cada función computable igual que losprogramas que cálculos los valores para la función en este lenguaje de programación.
Dado un conjunto enumerables S, una enumeración de Gödel es una función

donde f y la inversa de f son funciones computables.
Símbolos lógicos
Números 1:12
¬
1 ("no")

2 ("para todos")

3 ("si, entonces")

4 ("o")

5 ("y")
(
6
)
7
S
8 ("es el sucesor de")
0
9
=
10
.
11
+
12
Símbolosproposicionales
Números más grandes que 12 y divisibles por 3
P
15
Q
18
R
21
S
24
Variables individuales
Números más grandes que 12 con resto 1 cuando se dividen por 3
V
13
X
16
Y
19
Símbolos de predicado
Números más grandes que 12 con resto 2 cuando se dividen por 3
E
14
F
17
G
20

Codificación de programas mediante números:
Cuando codificamos un programa mediante números, lamayoría de las veces se trabaja con números naturales, sin embargo también existen otros tipos como:
Tipo bool: Se representa utilizando los números binario; 1(verdadero) y 0(falso).
Tipo par de números naturales: la codificación y decodificación de pares son funciones primitivas recursivas.
Tipo entero: Podría ser codificada con un par.
(Bool, numero par)
Tipo secuencial finitas de númerosnaturales: la codificación y decodificación de secuencias son funciones primitivas recursivas.
La codificación de programas basados en números, se lo puede realizar utilizando 4 instrucciones.
1) V ← V + 1
2) V ← V - 1
3) IF V ≠ 0 GOTO 6 L’
4) V ← V: no hace nada
Estas instrucciones hace expresa que:
Puede o no estar etiquetada con L
EI...