Máquina de correos
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 30 de enero de 2019; las comprobaciones requieren 5 ediciones .La máquina de correos es una máquina informática abstracta propuesta por Emil Post en 1936 , creada independientemente de la máquina de Turing , pero la publicación sobre la máquina de correos se publicó unos meses después. Se diferencia de la máquina de Turing en una mayor sencillez, además, ambas máquinas son algorítmicamente “equivalentes” y ambas están diseñadas para formalizar el concepto de un algoritmo y resolver problemas algorítmicos de solución , es decir, para demostrar la solución algorítmica de problemas en forma de una secuencia de instrucciones para la máquina Post.
Cómo funciona
La máquina de Post consiste en un carro (o un cabezal de lectura y escritura) y una cinta, dividida en celdas, sin fin en ambos lados. Cada celda de la cinta puede estar en 2 estados: estar vacía 0o marcada con una etiqueta 1. Durante el ciclo de la máquina, el carro puede moverse una posición hacia la izquierda o hacia la derecha, contar, cambiar el carácter en su posición actual.
El funcionamiento de la máquina Post está determinado por un programa que consta de un número finito de líneas. Para que la máquina funcione, debe configurar el programa y su estado inicial (es decir, el estado de la cinta y la posición del carro). El carro está controlado por un programa que consta de líneas de comandos numeradas, no necesariamente ordenadas, si cada comando especifica una línea a la que saltar. Por lo general, se acepta que si la transición no se especifica en el comando, la transición se produce a la siguiente línea. Cada comando tiene la siguiente sintaxis:
i. K jdonde i es el número de comando, K es la acción de transporte, j es el número del próximo comando (envío).
En total, hay seis tipos de comandos para la máquina Post:
- V j - poner una etiqueta, ir a la j-ésima línea del programa;
- X j — borre la etiqueta, vaya a la j-ésima línea;
- ← j - muévase a la izquierda, vaya a la j-ésima línea;
- → j - muévase a la derecha, vaya a la j-ésima línea;
- ? j1; j2 - si no hay una etiqueta en la celda, vaya a la j1-ésima línea del programa; de lo contrario, vaya a la j2-ésima línea;
- ! - fin del programa ("stop", stop).
En el comando "stop", no se indica la transición a la siguiente línea.
Después de iniciar el programa, las opciones son:
- el trabajo puede terminar con un comando no ejecutable (borrar una etiqueta inexistente o escribir en un campo marcado);
- el trabajo puede terminar con un comando de parada;
- el trabajo nunca terminará.
Ejemplo
Para la suma y resta de números naturales (enteros no negativos) P y Q, se pueden representar en una cinta por un conjunto de P unidades y Q , separados entre sí por un cero; deje que la posición inicial del signo de intercalación esté en el "1" más a la izquierda del grupo de unidades Q (marcado con el símbolo " "): ⇓
⇓ …0010010010110… ╚═══╝ ╚═╝ P QSumar dos números es trivial: basta con poner " 1" entre los números y borrar uno de los extremos a la derecha " 1" de la representación de Q .
El programa para restar tales números consiste en cambiar secuencialmente el “ 1” más a la izquierda de la representación Q y el “ ” más a la derecha de la representación P. Al comienzo del programa, el carro se coloca en el "1" más a la izquierda en Q : 1
1. ← - paso a la izquierda 2. ? 1; 3 - si la celda está vacía, vaya a 1-paso, si no - vaya a3 3. X - quitar etiqueta 4. → - paso correcto 5. ? 4; 6 - si la celda está vacía, vaya a 4-paso, si no - vaya a6 6. X - quitar etiqueta 7. → - paso correcto 8. ? 9; 1 - si la celda está vacía, vaya al 9paso, si no - vaya a1 9. ! - el finEn la quinta línea, es posible un bucle si .
Literatura
- Uspenski Vladimir Andreevich Máquina de Correos / Cap. edición Phys.-Math. lit.. - 2nd ed., corregido.- M . : Nauka , 1988 . — 96 págs. - ( Clases populares de matemáticas ). — ISBN 5-02-013735-9 .