Máquinas de post clase virtual nº 1 (iván castro)

Iván Castro Chadid

EMIL L. POST (1897-1954)

En 1936 Emil L. Post y Alan M. Turing publicaron, independientemente y por caminos distintos, sendos artículos en donde anticipándose a la aparición de las computadoras universales, presentaban en forma teórica las características fundamentales que deben tener las máquinas que estén en capacidad de Calcular.

Una función se dice CALCULABLE, si viene dada por un algoritmo cualquiera, cuyo dominio es el dominio de aplicabilidad del algoritmo y a cada elemento del dominio le hace corresponder el elemento resultante de la aplicación de este algoritmo a dicho elemento

ALAN TURING (1912-1954)

Funciones usuales de la aritmética como la función “siguiente de” que calcula el número siguiente de un número natural, la función que calcula la suma, la que calcula el producto, la que calcula el cociente, la que calcula el máximo común divisor de dos números, la que calcula del mínimo común múltiplo de dos números, la que calcula la parte entera de un número, y muchas más son calculables mientras que la función:

no es calculable, ya que no es posible encontrar un algoritmo que permita determinar en forma precisa, cual es el valor de f(n) para cualquier n que tomemos.

El aprender a construir procedimientos que permitan calcular, es de gran importancia en el proceso de enseñanza aprendizaje de la matemática, porque se pasa del adiestramiento (que es lo que usualmente se hace), al entendimiento de los procesos lógico-deductivos que hay tras dichos cálculos.

Las Máquinas de Post permiten de una manera sencilla y amena cumplir

con este objetivo, su implementación no

requiere de equipos de cómputo sino simplemente

de lápiz y papel lo cual facilita al docente el poder llevarlas al aula de clase

v

Cinta

Máquina de Post

Carro o cabezal de lectura y registro

Célula vacíaCélula marcada

¿Cómo marcar los números?

v

Número 0

vv

Número 1

v

vv

Número 2

v v

vv

Número 3

v v v

v

Número de la instrucción Salto

Instrucciones de movimiento

v

v

El carro se mueve una célula a la derecha

Instrucciones de movimiento

v

v

El carro se mueve una célula a la izquierda

Instrucción de impresión

v

En la correspondiente celda se imprime una marca

Instrucciones de vaciado

En la correspondiente celda se borra la marca

v

Instrucción de salto del control

Si la celda está vacía vaya a la instrucción j, Si está llena vaya a la instrucción s.

v

j

s

? i.

Instrucción de parada

con esta instrucción se da por terminado el programa

vvv vv v

Un programa de una Máquina de Post es una secuencia finita de instrucciones del tipo:

que cumple las siguientes condiciones:

Programas de Máquinas de Post

1. En el primer lugar está la instrucción con el número 1, en el segundo la instrucción con el número 2, en el tercero la instrucción con el número 3 y en general en el k-ésimo lugar la instrucción con el número k.

2. Cada salto de cualquiera de las instrucciones coincide con el número de cierta instrucción.

No son programas de una Máquina de Post los siguientes:

1. 2

3. 4

2. 4

4. 1

5

3?2.

1. 2

3. 4

4. 1

Posibles posiciones del carro

vvv v vv

1º) P1

vvv v vv

2º) P2

vvv v vv

3º) P3

1º programa

vvv v vv

Si el carro está en P1 construya un programa para calcular la función:

3

1?2.

1. 2

4. Stop

3. 4

Desarrollo:Desarrollo:

2º programaSi el carro está en P2 construya un programa para calcular la función:

1

3?2.

5. Stop

Desarrollo:Desarrollo:1. 2

vvv v vv

3. 4

4. 5

3º programaSi el carro está en P3 construya un programa para calcular la función:

1

3?2.

5. Stop

Desarrollo:Desarrollo:

3. 4

vvv v vv

1. 2

4. 5

4º programa¿Cómo procederíamos si no sabemos en donde está el carro?

6

2?1.

En este caso lo primero que hacemos es empezar con una instrucción del tipo:

en donde la instrucción 2 conduce a elaborar el 1º Programa.

la instrucción 6 nos dice que el carro está sobre una celda vacía, la pregunta que surge es:

¿El número está a la izquierda o a la derecha del cursor?

este problema es similar al siguiente:

?

Supongamos que un invidente es abandonado en un camino recto con dos estacas que pueden ser clavadas en el piso y se le advierte que caminando en una de las dos direcciones: norte (N) o sur (S), puede

encontrar un sitio en donde ampararse, ¿cómo procede para llegar a ese lugar?.

Desarrollo:Desarrollo:

Una forma de resolver el problema es la siguiente:

Empieza comprobando con las manos si ya llegó;

3

2?1.

2. Stop

En caso de que la respuesta sea negativa clava una estaca en el piso y da un paso en la dirección N

V

Nuevamente se hace la misma pregunta, si la respuesta es negativa , clava la segunda estaca gira 180º y camina en dirección S hasta encontrar la primera estaca

4. 5

3. 4

6

2?5.

6. 7

7. 87

9?8.

V

Recoge esta estaca da un paso en la dirección S y se pregunta si ya llegó, si la respuesta es negativa, clava la segunda estaca gira 180º y camina en dirección N hasta encontrar la primera estaca

V

12

2?11.

10. 11

9. 10

12. 13

13. 1413

15?14.

V

Procediendo de esta forma un número finito de veces, se llega finalmente a encontrar un sitio para guarecerse.

V

2

20?1.

6. 7

8. 9

2. 3

3. 45

15? 4.

5. 6

6

8? 7.

9. 10

11

21? 10.

11. 12

12. 13

12

14? 13.

14. 3

15. 16

15

17? 16.

17. 18

18. 19

18

20? 19.

20. Stop

21. 22

21

23? 22.

23. 24

24. 25

24

20? 25.

Programa básico en máquinas de Post

V

Si no sabemos donde está el carro y queremos encontrar un programa para calcular la función:

Primero se emplea el Programa Básico y a continuación se utiliza el 1º programa.

En general, gracias al programa básico, es posible asumir que el carro siempre va a estar en posición P1.

VVV VV

5º programa

Construya un programa para calcular la suma de dos números si el carro está en la posición que se indica en la figura.

4

2?3.

2. 3

4. 5

Desarrollo:Desarrollo:

vvv vvvv v v

1. 2

5. 6

7

10?6.

7. 8

9. 1

9

7?8.

12

10?11.

10. 11

12. 13

13. 14

14. Stop

6º programa

Construya un programa para calcular la suma de dos números si el carro está en la posición que se indica en la figura.

Desarrollo:Desarrollo:

vvv vvvv v v

1

3?2.

1. 2

3. 4

4. 5

10

6?5.

6. 7

8. 9

6

8?7.

9. 1

10. Stop

7º programa

Construya un programa para calcular la suma de dos números si el carro está en la posición que se indica en la figura.

Desarrollo:Desarrollo:

vvv v vv vv v

6

4?5.

6. 7

7. 8

9

12?8.

14

12?13.

14. 15

15. 16

16. Stop

9. 10

11. 3

12. 13

11

9?10.

4. 5

3. 4

1

3?2.

1. 2

8º programa

Construya un programa para calcular el valor absoluto de la diferencia entre dos números si el carro está señalando una célula marcada por el primer número como se indica en la figura.

Desarrollo:Desarrollo:

vvv vv vv v

8

10?9.

10. 11

11. 1213

3?12.

6. 7

17

8?7.

8. 9

5. 6

v v

3. 4

3

2?1.

2. 1

3

5?4.

16. 17

13

15?14.

13. 14

17. Stop

15. 16

8º programa

Construya un programa para calcular el valor absoluto de la diferencia entre dos números si el carro está señalando una célula limpia como se indica en la figura.

Desarrollo:Desarrollo:

vvv vv vv v

8

10?9.

10. 11

11. 1213

3?12.

6. 7

17

8?7.

8. 9

5. 6

v v

3. 4

3

2?1.

2. 1

3

5?4.

16. 17

13

15?14.

13. 14

17. Stop

15. 16

Este tema como parte del curso TIC podría motivar a los estudiantes del postgrado para que pensaran en opciones como esta en sus tesis de grado.

Los ejemplos que hemos presentado representan una pequeña muestra de la gran variedad de programas que pueden construirse.

Estamos en mora de elaborar una gran librería de máquinas de Post.

Las funciones aritméticas nos ofrecen una amplia y rica variedad de ejemplos que son de interés en Teoría de Números y que pueden llevarse a través de máquinas de Post al aula de clase.

vvvvv vv vv

vvvvv vv v v

vvvvv vv v

vvvvv vv vv

vvvvv vv vv

vvvvv vv vv