PAG''

Lenguaje de programación primitivo creado en 1964.

P′′ (P doble primo ^[1] ) es un lenguaje de programación informático primitivo creado por Corrado Böhm ^{[2] [3]} en 1964 para describir una familia de máquinas de Turing .

Definición

${\textstyle {\mathcal {P}}^{\prime \prime }}$(en adelante P′′ ) se define formalmente como un conjunto de palabras del 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. Sólo 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-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 lenguaje. ${\textstyle \Box }$
• ${\textstyle R}$significa mover el cabezal de la cinta una celda hacia la derecha (si es posible).
• ${\textstyle \lambda }$significa reemplazar el símbolo actual con y luego mover el cabezal de la cinta una celda hacia la izquierda. ${\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 bucle 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 " que se demostró que era completo en Turing ^{[2] [3]}
• El lenguaje Brainfuck (aparte de sus comandos de E/S) es una variación informal menor de P′′. Böhm proporciona programas P′′ explícitos para cada uno de un conjunto de funciones básicas suficientes para calcular cualquier función computable , utilizando únicamente , y las cuatro palabras donde con denota la iteración de , y . Estos son los equivalentes de los seis comandos Brainfuck respectivos [ , ] , + , - , < , > . Tenga en cuenta que desde , incrementar los tiempos del símbolo actual se ajustará de modo que el resultado sea "disminuir" el símbolo en la celda actual en uno ( ). ${\textstyle (}$ ${\textstyle )}$ ${\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 ^[2] proporciona el siguiente programa para calcular el predecesor ( x -1) de un número 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 en base k , codificando 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 base 2 es 100, se invierten los dígitos y se suma uno a cada uno de ellos). Al principio y al final del cálculo, la cinta -head está en el precedente de la cadena de dígitos. ${\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

1. "PDBL: una herramienta para la simulación de la máquina de Turing". 4 de septiembre de 2021.
2. Böhm, C .: "Sobre una familia de máquinas de Turing y el lenguaje de programación relacionado", ICC Bull. 3, 185-194, julio de 1964.
3. Böhm, C. y Jacopini, G.: "Diagramas de flujo, máquinas de Turing y lenguajes con sólo dos reglas de formación", CACM 9(5), 1966. (Nota: este es el artículo más citado sobre el teorema del programa estructurado .)

enlaces externos

• P′′Intérprete en línea: Demostración de la canción iterativa 99 Bottles of Beer interpretada en las instrucciones 337568 P′′ .