Lenguaje S

Question 1

Variables Lenguaje S

Answer 1

Existen tres tipos de variables, las cuales no se declaran:

1. Variables de entrada: X1, X2, X3, . . .
2. Variables temporales: Z1, Z2, Z3, . . .
3. Variable de salida: Y

El tipo de datos es N y las variables auxiliares y la de salida comienzan
inicializadas en 0.

Question 2

Etiquetas

Answer 2

Las etiquetas se representan como:
A1, B1, C1, D1, E1, A2, . . .

Question 3

Instrucciones

Answer 3

Existen tres tipos de instrucciones:

1. Sea V una variable.
   V ← V + 1
   Si la variable V tiene el valor n ∈ N, luego de ejecutarse la instrucción va a tener el valor n + 1.
2. Sea V una variable.
   V ← V − 1
   Si la variable V tiene el valor n ∈ N≥1, luego de ejecutarse la
   instrucción va a tener el valor n−1. Si V tiene el valor 0, luego de
   ejecutarse queda con el mismo valor.
3. Sea V una variable y L una etiqueta.
   IF V ≠ 0 GOT O L
   Si la variable V tiene el valor 0, se pasa a la próxima instrucción;
   si tiene un valor distinto de cero, se pasa a la primer instrucción
   del programa a la cual la antecede la etiqueta L.

A cada instrucción la puede anteceder una etiqueta, la cual se escribe
entre corchetes:
[L] Instrucción

Question 4

Programa

Answer 4

Un programa es una lista finita de instrucciones I1, I2, . . . , In que se
escriben una debajo de la otra.

Question 5

Macros

Answer 5

Una macro es una pseudoinstrucción que representa un segmento de un
programa

Question 6

Expansión de una macro

Answer 6

Cada vez que en un programa P aparece una macro, la misma se debe
reemplazar por el segmento del programa que representa. Este proceso
de denomina expansión de la macro.

Question 7

Estado de un programa

Answer 7

El estado de un programa P es una lista finita de ecuaciones de la forma
V = m
Donde V es una variable y m ∈ N.
Hay una única ecuación para cada variable que aparece en P.

Question 8

Descripción instantánea de un programa

Answer 8

muy largo Página 123

Question 9

Cómputo

Answer 9

Un cómputo de un programa P a partir de una descripción instantánea
d1 = (i, σ) es una lista d1, d2, . . . , dk de descripciones instantáneas de P
tales que dj+1 es el sucesor de dj .
Siendo 1 ≤ j ≤ k − 1, y dk la descripción instantánea terminal.

Question 10

Estado inicial

Answer 10

Sea P un programa y sean u1, . . . , um números naturales.
El estado inical de P para u1, . . . , um es el estado σ1 definido como
j > m σ1 = (X1 = u1, X2 = u2, . . . , Xm = um, Xj = 0, Zj = 0, Y = 0)
En cuyo caso no se
escriben
Donde Xj y Zj pueden no aparecer en el programa.
Por lo tanto la descripción inicial de P para u1, . . . , um es d1 = (1, σ1).

Question 11

Cómputo a partir del estado inicial

Answer 11

Sea P un programa, sean u1, . . . , um números naturales y σ1 el estado
inicial para ellos.
Entonces existen dos posibilidades:

1. Hay un cómputo de P: d1, . . . , dk, siendo d1 = (1, σ1).
   Notación: Ψ^m_P (u1, . . . , um) es el valor de Y en la descripción instantánea dk.
2. Existe una secuencia infinita d1, d2, . . . siendo d1 = (1, σ1) y di+1 el sucesor de di.
   Notación: Ψ^m_P (u1, . . . , um) =↑ significa que Ψ^m_P (u1, . . . , um) está
   indefinido.

Question 12

Función parcialmente computable

Answer 12

Definición 93:

Question 13

Función total

Answer 13

Sea f una función.
Decimos que f es total si su dominio es N
m.

Question 14

Función total computable

Answer 14

Una función f ∶ N^k → N es total computable si es parcialmente computable y total.

Question 15

Composición de funciones computables

Answer 15

Teorema 25: y demo