P′′

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
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
[editar datos en Wikidata]

\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[editar]

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

Sintaxis[editar]

  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[editar]

  • {a0, a1, ..., an}(n ≥ 1) es el alfabeto de la cinta de una máquina de Turing con cinta infinita por la izquierda, siendo a0 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 ai por ai+1 (tomando an+1 = a0), 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 a0.
  • 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[editar]

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′ ≡ rn, L ≡ r′λ, R. Estos son los comandos equivalentes de los seis usados respectivamente por Brainfuck: [, ], +, -, <, >. Note que desde an+1 = a0, 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[editar]

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 a1, ..., an codificando los dígitos 1,...,n, respectivamente, y agregando un blanco a0 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 a0a1a1a2a0, porque 8 = 1*22 + 1*21 + 2*20.) Al comienzo y al final del cómputo, la cabeza de la cinta está en el a0 precediendo el string que representa el dígito.

Referencias[editar]

  1. a b c d Böhm, C.: "On a family of Turing machines and the related programming language", ICC Bull. 3, 185-194, Julio de 1964.
  2. a b 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.)