P′′
# P′′

${\mathcal {P}}^{\prime \prime }$ (denotado también simplemente P′′) es un lenguaje de programación esotérico, creado por Corrado Böhm en 1964 para describir a una familia de máquinas de Turing.

## Definición

P′′ se define formalmente como un conjunto de palabras sobre un alfabeto de cuatro instrucciones {R, λ, (, )}, como sigue:

### Sintaxis

* R y λ son palabras en P′′.
* Si p y q son palabras en P′′, entonces pq es una palabra en P′′.
* Si q es una palabra en P′′, entonces (q) es una palabra en P′′.
* Solamente palabras derivadas de las tres reglas anteriores son palabras en P′′.

### Semántica

* ${a_0,$ $a_1,$ ..., $a_n}(n$ ≥ 1) es el alfabeto de la cinta de una máquina de Turing con cinta infinita por la izquierda, siendo $a_0$ el símbolo blanco.
* R significa mover la cabeza de la cinta una celda hacia la derecha (si procede).
* λ significa reemplazar el símbolo actual $a_i$ por $a_{i+1}$ (tomando $a_{n+1}$ = $a_0),$ y luego moviendo la cabeza de la cinta una celda hacia la izquierda.
* (q) significa iterar q en un bucle while, con la condición que el símbolo actual no sea $a_0.$
* Un programa es una palabra en P′′. La ejecución de un programa se produce de izquierda a derecha, ejecutando R, λ, y (q) según como se encuentren, hasta que no haya más que ejecutar.

## Relación con otros lenguajes de programación

P′′ fue el primer lenguaje imperativo de programación estructurada que prescindió del GOTO para ser demostrada su pertenencia a los Turing completos.

El lenguaje Brainfuck (aparte de sus comandos de E/S) es una variación menos informal de P′′, que influyó a su vez posteriormente la creación de otros lenguajes esotéricos, tales como Ook! y Tink. Böhm define programas explícitos para P′′ para cada uno de los conjuntos de funciones básicas suficientes para computar cualquier función computable, utilizando solo (, ) y las cuatro palabras r ≡ λR, r′ ≡ $r^n,$ L ≡ r′λ, R. Estos son los comandos equivalentes de los seis usados respectivamente por Brainfuck: [, ], +, -, <, >. Note que desde $a_{n+1}$ = $a_0,$ realizar r (símbolo de "incremento" en la celda actual) n veces dará como resultado un "decremento" del símbolo en la celda actual (r′).

## Ejemplos de programas

Böhm define el siguiente programa para computar el antecesor (x-1) de un entero x > 0:

    R ( R ) L ( r' ( L ( L ) ) r' L ) R r

lo que se traduce directamente al equivalente programa en brainfuck

Este programa recibe como entrada un número entero definido en notación de numeración biyectiva base-n, con $a_1,$ ..., $a_n$ codificando los dígitos 1,...,n, respectivamente, y agregando un blanco $a_0$ antes y después del string del dígito. (Por ejemplo, en numeración biyectiva base-2, el número 8 se codificaría como $a_0a_1a_1a_2a_0,$ porque 8 = $1*2^2$ + $1*2^1$ + $2*2^0.)$ Al comienzo y al final del cómputo, la cabeza de la cinta está en el $a_0$ precediendo el string que representa el dígito.

