title: P′′
text: # 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.
  
  