P′′

(denotado también simplemente P′′) es un lenguaje de programación esotérico, creado por Corrado Böhm^{[1] [2]} 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

1. R y λ son palabras en P′′.
2. Si p y q son palabras en P′′, entonces pq es una palabra en P′′.
3. Si q es una palabra en P′′, entonces (q) es una palabra en P′′.
4. Sólo palabras derivadas de las tres reglas anteriores son palabras en P′′.

Semántica

• {a₀, a₁, ..., a_n}(n ≥ 1) es el alfabeto de la cinta de una máquina de Turing con cinta infinita por la izquierda, siendo a₀ 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₀), 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₀.
• 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.

Relajación a 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.^{[1] [2]}

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^[1] define programas explícitos para P′′ para cada uno de los conjuntos de funciones básicas suficientes para computar cualquier función computable, utilizando sólo (, ) y las cuatro palabras r ≡ λR, r′ ≡ rⁿ, L ≡ r′λ, R. Estos son los comandos equivalentes de los seis usados respectivamente por Brainfuck: [, ], +, -, <, >. Note que desde a_n+1 = a₀, 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^[1] 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₁, ..., a_n codificando los dígitos 1,...,n, respectivamente, y agregando un blanco a₀ 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₀a₁a₁a₂a₀, porque 8 = 1*2² + 1*2¹ + 2*2⁰.) Al comienzo y al final del cómputo, la cabeza de la cinta está en el a₀ precediendo el string que representa el dígito.

Referencias