PAGS'' - P′′

P ′ ′ (P doble prima) es un lenguaje de programación de computadoras primitivo creado por Corrado Böhm en 1964 para describir una familia de máquinas de Turing .

Definición

${\ textstyle {\ mathcal {P}} ^ {\ prime \ prime}}$(en adelante escrito P ′ ′ ) se define formalmente como un conjunto de palabras en el alfabeto de cuatro instrucciones , de la siguiente manera: ${\ textstyle \ {R, \ lambda, (,) \}}$

Sintaxis

1. ${\ textstyle R}$y son palabras en P ′ ′.${\ textstyle \ lambda}$
2. Si y son palabras en P ′ ′, entonces es una palabra en P ′ ′.${\ textstyle q_ {1}}$${\ textstyle q_ {2}}$${\ textstyle q_ {1} q_ {2}}$
3. Si es una palabra en P ′ ′, entonces es una palabra en P ′ ′.${\ textstyle q}$${\ textstyle (q)}$
4. Solo las palabras derivables de las tres reglas anteriores son palabras en P ′ ′.

Semántica

• ${\ textstyle \ {\ Box, c_ {1}, c_ {2}, \ ldots, c_ {n} \}}$es el alfabeto de cinta de una máquina de Turing con cinta infinita a la izquierda, siendo el símbolo en blanco , equivalente a .${\ textstyle \ Box}$${\ textstyle c_ {0}}$
• Todas las instrucciones en P ′ ′ son permutaciones del conjunto de todas las configuraciones de cinta posibles; es decir, todas las configuraciones posibles tanto del contenido de la cinta como de la posición del cabezal de la cinta.${\ textstyle X}$
• ${\ textstyle \ alpha}$es un predicado que dice que el símbolo actual no lo es . No es una instrucción y no se usa en programas, sino que se usa para ayudar a definir el idioma.${\ textstyle \ Box}$
• ${\ textstyle R}$ significa mover el cabezal de la cinta hacia la derecha una celda (si es posible).
• ${\ textstyle \ lambda}$significa reemplazar el símbolo actual con , y luego mover el cabezal de la cinta hacia la izquierda una celda.${\ textstyle c_ {i}}$${\ textstyle c _ {(i + 1) {\ bmod {(}} n + 1)}}$
• ${\ textstyle q_ {1} q_ {2}}$significa la composición de la función . En otras palabras, la instrucción se realiza antes .${\ textstyle q_ {2} \ circ q_ {1}}$${\ textstyle q_ {1}}$${\ textstyle q_ {2}}$
• ${\ textstyle (q)}$significa iterar en un ciclo while , con la condición .${\ textstyle q}$${\ textstyle \ alpha}$

Relación con otros lenguajes de programación

• P ′ ′ fue el primer lenguaje de programación estructurado imperativo "sin GOTO " probado con Turing-complete
• El lenguaje Brainfuck (aparte de sus comandos de E / S) es una variación informal menor de P ′ ′. Böhm da programas P ′ ′ explícitos para cada una de un conjunto de funciones básicas suficientes para calcular cualquier función computable , usando solo , y las cuatro palabras donde con denota la ésima iteración de y . Estos son los equivalentes de los seis comandos Brainfuck respectivos [,], +, -, <,> . Tenga en cuenta que , dado que , al incrementar los tiempos del símbolo actual, el resultado será "disminuir" el símbolo en la celda actual en uno ( ).${\estilo de texto (}$${\estilo de texto )}$${\ textstyle r, r ^ {\ prime}, L, R}$${\ textstyle r \ equiv \ lambda R, r ^ {\ prime} \ equiv r ^ {n}}$${\ textstyle r ^ {n}}$${\ textstyle n}$${\ textstyle r}$${\ textstyle L \ equiv r ^ {\ prime} \ lambda}$ ${\ textstyle c_ {n + 1} \ equiv c_ {0} \ equiv \ Box}$${\ textstyle n}$${\ textstyle r ^ {\ prime}}$

Programa de ejemplo

Böhm da el siguiente programa para calcular el predecesor ( x -1) de un entero x > 0:

${\ Displaystyle R (R) L (r ^ {\ prime} (L (L)) r ^ {\ prime} L) Rr}$

que se traduce directamente al programa Brainfuck equivalente :

 >[>]<[−[<[<]]−<]>+

El programa espera que un número entero se represente en notación biyectiva base-k , con la codificación de los dígitos respectivamente, y que tenga antes y después de la cadena de dígitos. (Por ejemplo, en biyectiva base-2, el número ocho se codificaría como , porque 8 en biyectiva base-2 es 112.) Al principio y al final del cálculo, la cabeza de la cinta está en la cadena de dígitos anterior. ${\ textstyle c_ {1}, c_ {2} \ ldots, c_ {k}}$${\ textstyle 1,2, \ ldots, k}$${\ textstyle \ Box}$${\ textstyle \ Box c_ {1} c_ {1} c_ {2} \ Box}$${\ textstyle \ Box}$

Referencias

Enlaces web

• P ′ ′ Intérprete en línea : demostración de lacancióniterativa99 Bottles of Beerinterpretada en 337568instruccionesP ′ ′.