PDF de programación - Funciones GOTO--computables

Imágen de pdf Funciones GOTO--computables

Funciones GOTO--computablesgráfica de visualizaciones

Actualizado el 26 de Julio del 2021 (Publicado el 20 de Junio del 2017)
4.849 visualizaciones desde el 20 de Junio del 2017
135,1 KB
18 paginas
Creado hace 11a (16/05/2012)
Funciones GOTO–computables

Dpto. Ciencias de la Computación e Inteligencia Artificial

Universidad de Sevilla

Lógica Matemática

Curso 2011–12

LM, 2011–12

Lenguaje GOTO 4.1

Contenido

El lenguaje GOTO

Sintaxis
Semántica

Macros

Uso de macros
Expansión de macros

LM, 2011–12

Lenguaje GOTO 4.2

El Lenguaje GOTO

Es un modelo secuencial y determinista con conjunto de datos: N.

Sintaxis:

1. Variables:

 De entrada: X1(= X ), X2, X3, ...

Y
Z1(= Z ), Z2, Z3, ...

De salida:
Auxiliares:

2. Etiquetas: A1, B1, C1, D1, E1, A2, B2, C2, D2, E2, . . .

Notación: A = A1, B = B1, C = C1, D = D1, E = E1.
3. Instrucciones: Para cada variable V y cada etiqueta L:

Incremento: V ←− V + 1
Decremento: V ←− V − 1
Condicional: IF V = 0 GOTO L
Skip: V ←− V

Estas instrucciones pueden ser etiquetadas con cualquier
etiqueta K . Por ejemplo,

[K ] V ←− V + 1
[K ] IF V = 0 GOTO L

LM, 2011–12

Lenguaje GOTO 4.3

Programas GOTO

Un programa GOTO (un G–programa) es una sucesión finita

de instrucciones del lenguaje GOTO, P = I1, I2, .., In, cuya
última instrucción NO es Y ←− Y .

Si P = I1, . . . , In es un programa GOTO el número n se

denomina longitud del programa y se denota por |P|.
Caso límite: el Programa Vacío (con 0 instrucciones).
Notación: Denotaremos por GOTOP al conjunto de

G-programas.

Ejemplo:

p

 [A] X ←− X − 1

Y ←− Y + 1
IF X = 0 GOTO A

Cada programa expresa un procedimiento para calcular una
cierta función (parcial) de Nn en N. El modo en que cada
programa lleva a cabo esto se determina mediante la
semántica del lenguaje GOTO.

LM, 2011–12

Lenguaje GOTO 4.4

Descripciones instantáneas

Sea P un programa GOTO.

Denotaremos por VAR al conjunto de las variables del

lenguaje GOTO y mediante var (P) al conjunto de variables
que aparecen en P.

Un estado de P es una aplicación σ : VAR → N.
Un estado es, esencialmente, una tabla variable–valor que

guarda el valor de las variables del programa en un momento
dado. Por ello, a veces, escribiremos V = m en lugar de
σ(V ) = m.

Una descripción instantánea, (d.i.) de P, es un par

s = (i, σ) donde 1 ≤ i ≤ |P| + 1 y σ es un estado de P.

Cuando i = |p| + 1, la d.i. se denomina terminal.
Si s = (i, σ), escribiremos s(V ) en lugar de σ(V ).

LM, 2011–12

Lenguaje GOTO 4.5

Semántica

Sea P un programa y s = (j, σ) y s = (j, σ) descripciones
instantáneas de P con j = |p| + 1.
Diremos que s es la siguiente de s en la computación de P, y
escribimos s p s, si:
Caso 1: Ij ≡ V ←− V + 1, s(V)=m. Entonces j = j + 1 y
Caso 2: Ij ≡ V ←− V − 1, s(V)=m. Entonces j = j + 1 y

σ es σ sustituyendo V = m por V = m + 1.

Si m > 0, σ es σ sustituyendo V = m por V = m − 1.
Si m = 0, σ = σ

Caso 3: Ij es de tipo SKIP. Entonces j = j + 1 y σ = σ.
Caso 4: Ij ≡ IF V = 0 GOTO L. Entonces σ = σ y

Si s(V ) = 0, entonces j = j + 1
Si s(V ) = 0

Si existe k tal que Ik es la primera instrucción etiquetada con
Si no existe tal k, j = |p| + 1

L, entonces j = k

LM, 2011–12

Lenguaje GOTO 4.6

Computación de un programa

Una computación de un programa P es una sucesión de d.i. de P,
s = s1, . . . , sk , . . . tal que:

s1 = (1, σ) (y se denomina d.i. inicial);
Para todo k, con sk no terminal, existe k + 1 tal que

sk p sk+1

Una computación s de p es finita si y sólo si existe k tal que sk+1
es terminal; en tal caso, escribiremos P(s) ↓ y diremos que dicha
computación para y se realiza en k pasos. En caso contrario, la
computación s es infinita; escribiremos P(s) ↑ y diremos que
no para.
Lema. Para todo P ∈ GOTOP se verifica:
Ausencia de bloqueo: Para toda d.i., s, no terminal, existe s

tal que s p s.

Determinismo: Para cada d.i. inicial existe una única

computación.

LM, 2011–12

Lenguaje GOTO 4.7

Ejemplo

[A]

[B]

IF X = 0 GOTO B
Z ←− Z + 1
IF Z = 0 GOTO E
X ←− X − 1
Y ←− Y + 1
IF X = 0 GOTO A

s1 = (1,{X = 3, Y = 0, Z = 0})
s2 = (4,{X = 3, Y = 0, Z = 0})
s3 = (5,{X = 2, Y = 0, Z = 0})
s4 = (6,{X = 2, Y = 1, Z = 0})
s5 = (1,{X = 2, Y = 1, Z = 0})
s6 = (4,{X = 2, Y = 1, Z = 0})
s7 = (5,{X = 1, Y = 1, Z = 0})
s8 = (6,{X = 1, Y = 2, Z = 0})
s9 = (1,{X = 1, Y = 2, Z = 0})
s10 = (4,{X = 1, Y = 2, Z = 0})
s11 = (5,{X = 0, Y = 2, Z = 0})
s12 = (6,{X = 0, Y = 3, Z = 0})
s13 = (7,{X = 0, Y = 3, Z = 0})

LM, 2011–12

Lenguaje GOTO 4.8

Funciones GOTO–computables

Sea P un G–programa. La función de aridad n calculada por P es
la función [[P]](n) : Nn − → N definida como sigue:
Dado a = (a1, . . . , an) ∈ Nn,
1. Sea σ el estado de P dado por:
σ(Xi ) = ai (1 ≤ i ≤ n)
σ(V ) = 0 para toda V ∈ VAR \ {X1, . . . , Xn}.

2. Sea ahora s1 = (1, σ). Entonces

 sk (Y ) si existe s1, . . . , sk finita de p

a partir de s1
e.c.o.c.

[[P]](n)(a) =



Definición. Diremos que una función f : Nn − → N es
GOTO–computable (f ∈ G –COMP), si existe un programa
GOTO, P tal que f = [[P]](n).

Designaremos por G –COMP (n) al conjunto de funciones

computables de aridad n.

LM, 2011–12

Lenguaje GOTO 4.9

Ejemplos

La función identidad IdN : N → N es GOTO–computable.

IF X = 0 GOTO B
Z ←− Z + 1
IF Z = 0 GOTO E
[B] X ←− X − 1
Y ←− Y + 1
IF X = 0 GOTO B
La función vacía f∅ es GOTO–computable:

[A] Z ←− Z + 1

IF Z = 0 GOTO A
La función nula O : N −→ N O(x) = 0 es

GOTO–computable.

La función nula es calculada por cualquier programa que pare
siempre y en el que no aparezca la variable de salida Y .

LM, 2011–12

Lenguaje GOTO 4.10

Macros

Existen bloques de instrucciones que podemos considerar como
“nuevas instrucciones” ya que podemos utilizarlos en cualquier
programa para realizar una cierta subtarea. Veamos algunos
ejemplos de esto:

El bloque de instrucciones:

Z ←− Z + 1
IF Z = 0 GOTO L

nos permite realizar un salto incondicional a la instrucción
etiquetada por L (o terminar la ejecución del programa).

Podemos poner a cero una variable V mediante el siguiente

bloque de instrucciones:

[L] V ←− V − 1

IF V = 0 GOTO L

LM, 2011–12

Lenguaje GOTO 4.11

Macros (II)

Es útil introducir abreviaturas para poder usar cómodamente

los bloques anteriores en la descripción de un programa.
Dichas abreviaturas se denominan macros y para poder
usarlas debemos especificar con precisión la forma en que
dichas abreviaturas se reemplazan por verdadero código.



GOTO L

MACRO



V ←− 0
MACRO

=⇒

=⇒

Zk ←− Zk + 1
IF Zk = 0 GOTO L
EXPANSI ÓN


[K ] V ←− V − 1



IF V = 0 GOTO K



EXPANSI ÓN

En el primer caso Zk debe ser una variable que no aparece ne

el programa en que realizamos la expansión. En el segundo
caso K es una etiqueta que no aparece en dicho programa.

LM, 2011–12

Lenguaje GOTO 4.12

Macros. Asignación

La macro V ←− V asigna a V el valor de V , conservando V su
valor.

V ←− 0
IF V = 0 GOTO B
[A]
GOTO C
[B] V ←− V − 1
V ←− V + 1
Z ←− Z + 1
GOTO A
IF Z = 0 GOTO D
[C ]
GOTO L
[D] Z ←− Z − 1
V ←− V + 1
GOTO C
[L] V ←− V

y
Pone V a cero

 Copia V en V y en Z
 Copia Z en V

Pone Z a cero

LM, 2011–12

Lenguaje GOTO 4.13

Uso de las macros

Y ←− X1
Z ←− X2
IF Z = 0 GOTO A
[B]
GOTO E
[A] Z ←− Z − 1
Y ←− Y + 1
GOTO B

La función suma: Sum : N2 −→ N Sum(x, y ) = x + y



P+

LM, 2011–12

Lenguaje GOTO 4.14

Uso de macros (II)

Z2 ←− X2
IF Z2 = 0 GOTO A
[B]
GOTO E
[A] Z2 ←− Z2 − 1
Z1 ←− X1 + Y
Y ←− Z1
GOTO B

La función producto. Prod : N2 −→ N Prod(x, y ) = x·y





Nota: Z1 ←− X1 + Y es una macro ejecuta el programa Suma y
asigna el resultado a la variable Z1.

LM, 2011–12

Lenguaje GOTO 4.15

Expansión de macros (I)

Sean f ∈ GCOMP (n) y P ∈ GOTOP tales que [[P]](n) = f .
Veamos una expansión para la macro: W ←− f (V1, . . . , Vn).
1. Renombrando las etiquetas de P si fuese necesario, podemos
suponer que la única etiqueta de salida de P es E y todas las
demás etiquetas de P son A1, .., Ar .

2. Renombrando variables podemos suponer que las únicas

variables de entrada que aparecen en P son X1, . . . , Xn y las
únicas variables auxiliares Z1, . . . , Zk .

3. Podemos expresar la situación anterior escribiendo

P ≡ P(Y , X1, . . . , Xn, Z1, . . . , Zk ; E , A1, . . . , Ar )

4. Dado m ∈ N podemos obtener un nuevo programa
Qm ≡ P(Zm, , Zm+1, .., Zm+n, Zm+n+1, .., Zm+n+k ; Em, Am+1, .., Am+r )

sustituyendo en P cada variable y cada etiqueta por la
correspondiente de Qm.

LM, 2011–12

Lenguaje GOTO 4.16

Expansión de macros (II)

Para expandir la macro en un programa P, tomamos m ∈ N
suficientemente grande para que Qm y P no tengan variables ni
etiquetas comunes. Una vez determinado m reemplazamos la
macro por:

W ←− f (V1, . . . , Vn)



Zm ←− 0
Zm+1 ←− V1
...
Zm+n ←− Vn
...
Zm+n+1 ←− 0
...
Zm+n+k ←− 0
Qm

[Em] W ←− Zm

LM, 2011–12

Lenguaje GOTO 4.17

Macros condicionales

Si P(V1, . . . , Vn) es un predicado G-computable:

macroexpansión
Z ←− P(V1, . . . , Vn)
IF Z = 0 GOTO L

macro

IF P(V1, . . . , Vn) = 0 GOTO L



Ejemplo:

IF V = 0 GOTO L

V = 0 ≡ P(v ) =

1 si v = 0
IF X (cid:5
  • Links de descarga
http://lwp-l.com/pdf4512

Comentarios de: Funciones GOTO--computables (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad