PAG''

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

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

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′′.

• ${\textstyle \{\Cuadro ,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\Cuadro}$${\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 es . No es una instrucción y no se utiliza en programas, sino que se utiliza para ayudar a definir el lenguaje.${\textstyle\Cuadro}$
• ${\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 ejecuta 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}$

• P′� fue el primer lenguaje de programación estructurado imperativo "sin GOTO " que demostró ser Turing-completo ^{[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 una de un conjunto de funciones básicas suficientes para calcular cualquier función computable , utilizando solo , y las cuatro palabras donde con que denotan la iteración de , y . Estos son los equivalentes de los seis comandos Brainfuck respectivos [ , ] , + , - , < , > . Tenga en cuenta que desde , incrementar el símbolo actual veces se repetirá de manera que el resultado sea "decrementar" el símbolo en la celda actual en uno ( ).${\estilo de texto (}$${\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 }}$

Böhm ^[2] 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 entero se represente en notación biyectiva base-k , con codificación de los dígitos respectivamente, y que tenga antes y después de la cadena de dígitos. (Por ejemplo, en base-2 biyectiva, el número ocho se codificaría como , porque 8 en base-2 es 100, invierta los dígitos y agregue uno a cada uno de ellos). Al principio y al final del cálculo, el cabezal de la cinta está en el precedente de la cadena de dígitos.${\textstyle c_{1},c_{2}\ldots ,c_{k}}$${\textstyle 1,2,\ldots ,k}$${\textstyle\Cuadro}$${\textstyle \Caja c_{1}c_{1}c_{2}\Caja }$${\textstyle\Cuadro}$

• Intérprete en línea: Demostración de la canción iterativa 99 Botellas de Cerveza interpretada en 337568 instrucciones P" .