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.
  
  # P′′
  ## Definición
  
  P′′ se define formalmente como un conjunto de palabras sobre un alfabeto de cuatro instrucciones {R, λ, (, )}, como sigue:
  
  # P′′
  ## Definición
  ### 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′′.
  
  # P′′
  ## Definición
  ### 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.
  
  # P′′
  ## 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′).
  
  # P′′
  ## 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$_0$a$_1$a$_1$a$_2$a$_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.