P′′

P′′
?
Información general
Paradigma	Esotérico
Apareció en	1964
Diseñado por	Corrado Böhm
Implementaciones	Múltiples
Influido por	Máquina de Turing
Ha influido a	Brainfuck

${\displaystyle {\mathcal {P}}^{\prime \prime }}$ (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. Solamente 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 de 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.

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.[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 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₀, 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^2 + 1*2^1 + 2*2^0.) 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

1. Böhm, C.: "On a family of Turing machines and the related programming language", ICC Bull. 3, 185-194, julio de 1964.
2. Böhm, C. and Jacopini, G.: "Flow diagrams, Turing machines and languages with only two formation rules", CACM 9(5), 1966. (Nota: Este es el artículo más citado sobre el Teorema del programa estructurado.)

• Datos: Q2072087