Hispanopedia Wiki
Articulo de referencia

PAG''

P′′ (P doble primo) [ 1 ] es un lenguaje de programación de computadoras primitivo creado por Corrado Böhm en 1964 para describir una familia de máquinas de Turing . [ 2 ] [ 3 ]...

Hispanopedia WikiContenido en espanolLectura gratuita

P′′ (P doble primo) [ 1 ] es un lenguaje de programación de computadoras primitivo creado por Corrado Böhm en 1964 para describir una familia de máquinas de Turing . [ 2 ] [ 3 ] Proporcionó una de las primeras formulaciones del principio de entrada única y salida única, fundamental para la programación estructurada .

Definición

P′′ se define formalmente como un conjunto de palabras en el alfabeto de cuatro instrucciones.{R,λ,(,)}{\displaystyle \{\,R,\lambda ,(,)\,\}}, de la siguiente manera:

Sintaxis

  1. R{\displaystyle R}yλ{\displaystyle \lambda }son palabras en P′′.
  2. Siq1{\displaystyle q_{1}}yq2{\displaystyle q_{2}}son palabras en P'', entoncesq1q2{\displaystyle q_{1}q_{2}}es una palabra en P′′.
  3. Siq{\displaystyle q}es una palabra en P'', entonces(q){\displaystyle (q)}es una palabra en P′′.
  4. Solo las palabras que se pueden derivar de las tres reglas anteriores son palabras en P′′.

Semántica

Sea un alfabeto finitodo={do0≡◻}∪{do1,do2,…,donorte}{\displaystyle {\mathcal {C}}=\{c_{0}\equiv \Box \}\cup \{c_{1},c_{2},\dots ,c_{n}\}}, connorte≥1{\displaystyle n\geq 1}Se le proporciona, junto con una máquina de Turing equipada con una cinta que es infinita hacia la izquierda y dividida en cuadrados, de los cuales solo un número finito contiene inicialmente símbolos no vacíos. Los cuadrados restantes contienen el símbolo vacío.do0{\displaystyle c_{0}}La máquina tiene un solo cabezal que puede leer y escribir un cuadrado a la vez y moverse a lo largo de la cinta. [ 4 ] [ 5 ]

Para formalizar, los símbolos del alfabetodoi{\displaystyle c_{i}}se identifican con sus índicesi{\displaystyle i}. El número entero0{\displaystyle 0}corresponde al símbolo en blanco (◻{\displaystyle \Box }). La aritmética sobre cuadrados se realiza módulo(norte+1){\displaystyle (n+1)}, por lo tanto incrementandonorte{\displaystyle n}produce0{\displaystyle 0}y decreciente0{\displaystyle 0}producenorte{\displaystyle n}Esta formulación coincide con la definición de Böhm y difiere únicamente en la notación, reemplazando los elementos simbólicos del alfabeto con sus índices numéricos. [ n 2 ]

Un programa (llamado: " word ") opera sobre una configuración de cinta que consiste en una cinta inicial dada junto con la posición del cabezal. Cada cuadrado de cinta contiene un valor del conjunto.{0,1,…,norte}{\displaystyle \{0,1,\dots ,n\}}Todos los cuadrados, salvo un número finito de ellos, contienen inicialmente el valor0{\displaystyle 0}.

Instrucciones

Palabras de ejemplo

Definir{H}k→HH…H⏟k veces{\displaystyle \{H\}^{k}\;\rightarrow \;\underbrace {HH\dots H} _{k{\text{ veces}}}}como aplicación repetida de una secuencia de instrucciones. [ n 5 ] Por ejemplo,{λR}3→λRλRλR{\displaystyle \{\lambda R\}^{3}\;\rightarrow \;\lambda R\,\lambda R\,\lambda R}.

Ejemplo 1

Böhm define tres macros r, r'y L: [ 6 ]

  • r≡λR{\displaystyle r\equiv \lambda R}
Este fragmento añade1mod(norte+1){\displaystyle 1{\bmod {(}}n+1)}al cuadrado actual. [ n 3 ]
  • r′≡{r}norte≡{λR}norte{\displaystyle r'\equiv \{r\}^{n}\equiv \{\lambda R\}^{n}}
Este fragmento resta1mod(norte+1){\displaystyle 1{\bmod {(}}n+1)}desde la casilla actual. [ n 6 ]
  • L≡r′λ≡{λR}norteλ{\displaystyle L\equiv r^{\prime }\lambda \equiv \{\lambda R\}^{n}\lambda }
Esta macro desplaza la cabeza un cuadrado a la izquierda.

Ejemplo 2

Basándose en estas macros, Böhm [ 2 ] proporciona la siguiente palabra para calcular el predecesor.(incógnita−1){\displaystyle (x-1)}de un número enteroincógnita>0{\displaystyle x>0}:

R(R)L(r′(L(L))r′L)Rr{\displaystyle R(R)L(r^{\prime }(L(L))r^{\prime }L)Rr}

Cuando P′′ se define utilizando valores cuadrados en{0,1,…,norte}{\displaystyle \{0,1,\dots ,n\}}, el númeroincógnita{\displaystyle x}se representa en notación biyectiva en base n(d1,…,dk)bijnorte{\displaystyle (d_{1},\dots,d_{k})_{bijn}}, dígito más significativo primero. Estas tuplas aparecen en cuadrados consecutivos, flanqueados por0{\displaystyle 0}s, con el cabezal de cinta en el extremo izquierdo0{\displaystyle 0}.

La expansión de la macro depende del módulo .

Módulo = 2, cuando los cuadrados de la cinta toman valores en{0≡◻,1}{\displaystyle \{0\equiv \Box ,1\}\,}

Cuando los valores cuadrados están en{0,1}{\displaystyle \{0,1\}}, la palabra se expande a

R(R){λR}1λ({λR}1({λR}1λ({λR}1λ)){λR}1{λR}1λ)RλR{\displaystyle R(R){\{\lambda R\}^{1}\lambda }({\{\lambda R\}^{1}}({\{\lambda R\}^{1}\lambda }({\{\lambda R\}^{1}\lambda })){\{\lambda R\}^{1}}{\{\lambda R\}^{1}\lambda })R\lambda R}

eso es

R(R)λRλ(λR(λRλ(λRλ))λRλRλ)RλR{\displaystyle R(R)\lambda R\lambda (\lambda R(\lambda R\lambda (\lambda R\lambda ))\lambda R\lambda R\lambda )R\lambda R}

En notación biyectiva de base 1 el número8{\displaystyle 8}(por ejemplo) se codifica como(1,1,1,1,1,1,1,1)bij1{\displaystyle (1,1,1,1,1,1,1,1)_{bij1}}. [ n 7 ] Por lo tanto, la cinta inicial será (con la posición del cabezal subrayada )

|1⋯|0_|1|1|1|1|1|1|1|1|0‖{\displaystyle {\phantom {\vert 1\;}}\cdots \;\vert \;{\underline {0}}\;\vert \;1\;\vert \;1\;\vert \;1\;\vert \;1\;\vert \;1\;\vert \;1\;\vert \;1\;\vert \;1\;\vert \;0\;\rVert }

Después de la ejecución de la palabra, la configuración de la cinta es

|1⋯|0|0_|1|1|1|1|1|1|1|0‖{\displaystyle {\phantom {\vert 1\;}}\cdots \;\vert \;0\;\vert \;{\underline {0}}\;\vert \;1\;\vert \;1\;\vert \;1\;\vert \;1\;\vert \;1\;\vert \;1\;\vert \;1\;\vert \;0\;\rVert }

, que corresponde a la codificación biyectiva en base 1 para 7. [ n 8 ]

Módulo = 3, cuando los cuadrados de la cinta toman valores en{0,1,2}{\displaystyle \{0,1,2\}\,}

Cuando los valores cuadrados están en{0,1,2}{\displaystyle \{0,1,2\}}, la palabra se expande a

R(R){λR}2λ({λR}2({λR}2λ({λR}2λ)){λR}2{λR}2λ)RλR{\displaystyle R(R){\{\lambda R\}^{2}\lambda }({\{\lambda R\}^{2}}({\{\lambda R\}^{2}\lambda }({\{\lambda R\}^{2}\lambda })){\{\lambda R\}^{2}}{\{\lambda R\}^{2}\lambda })R\lambda R}

eso es

R(R)λRλRλ(λRλR(λRλRλ(λRλRλ))λRλRλRλRλ)RλR{\displaystyle R(R)\lambda R\lambda R\lambda (\lambda R\lambda R(\lambda R\lambda R\lambda (\lambda R\lambda R\lambda ))\lambda R\lambda R\lambda R\lambda R\lambda )R\lambda R}

En notación biyectiva de base 2 el número8{\displaystyle 8}está codificado como(1,1,2)bij2{\displaystyle (1,1,2)_{bij2}}. [ n 9 ] Por lo tanto, la cinta inicial será (con la posición del cabezal subrayada )

|1⋯|0_|1|1|2|0‖{\displaystyle {\phantom {\vert 1\;}}\cdots \;\vert \;{\underline {0}}\;\vert \;1\;\vert \;1\;\vert \;2\;\vert \;0\;\rVert }

Después de la ejecución de la palabra, la configuración de la cinta es

⋯|0|0_|1|1|1|0‖{\displaystyle \cdots \;\vert \;0\;\vert \;{\underline {0}}\;\vert \;1\;\vert \;1\;\vert \;1\;\vert \;0\;\rVert }

, que corresponde a la codificación biyectiva en base 2 para 7. [ n 10 ]

Módulo = 256, cuando los cuadrados de la cinta toman valores en{0,1,2,⋯,255}{\displaystyle \{0,1,2,\cdots ,255\}}

Cuando P′′ se define con un alfabeto de tamaño256,Σ={0,1,⋯,255}{\displaystyle 256,\,\Sigma =\{0,1,\cdots ,255\}}, la palabra se expande a

R(R){λR}255λ({λR}255({λR}255λ({λR}255λ)){λR}255{λR}255λ)RλR{\displaystyle R(R){\{\lambda R\}^{255}\lambda }({\{\lambda R\}^{255}}({\{\lambda R\}^{255}\lambda }({\{\lambda R\}^{255}\lambda })){\{\lambda R\}^{255}}{\{\lambda R\}^{255}\lambda })R\lambda R}

Su longitud completa es 3077{\displaystyle 3077}personajes. [ n 11 ]

En notación biyectiva de base 255 el número35048731{\displaystyle 35048731}(por ejemplo) se codifica como(2,29,1,1)bij255{\displaystyle (2,29,1,1)_{bij255}}. [ n 12 ] La cinta inicial será (con la posición del cabezal subrayada ):

|0⋯|0_|2|29|1|1|0‖{\displaystyle {\phantom {\vert 0\;}}\cdots \;\vert \;{\underline {0}}\;\vert \;2\;\vert \;29\;\vert \quad \;1\;\vert \quad \;1\;\vert \;0\;\rVert }

Después de la ejecución de la palabra, la configuración de la cinta es

⋯|0|0_|2|28|255|255|0‖{\displaystyle \cdots \;\vert \;0\;\vert \;{\underline {0}}\;\vert \;2\;\vert \;28\;\vert \;255\;\vert \;255\;\vert \;0\;\rVert }

, que corresponde a la codificación biyectiva en base 255 para35048730{\displaystyle 35048730}. [ n 13 ]

Fundamentos de la programación estructurada

Böhm demostró que P′′ es Turing-completo :

Para cada función recursiva parcialF{\displaystyle \mathbb {f} }demetro≥0{\displaystyle m\geq 0}variables un programaPAGj∈PAG′′{\displaystyle \mathrm {P} _ {j}\in {\mathcal {P}}^{\prime \prime }}Existe algo que lo calcula.

— Böhm (1964) [ 7 ]

El lenguaje demuestra que se pueden escribir programas sin usar estructuras de selección (si-entonces-si no), siendo necesarias únicamente la secuencia y la iteración. Las palabras P′′ se evalúan de izquierda a derecha, eliminando recursivamente el control hacia atrás. El artículo de Böhm sobre el lenguaje P′′ es una de las primeras formulaciones explícitas de lo que hoy conocemos como la propiedad de entrada única y salida única (SESE) .

a) Solo es posible entrar en un ciclo desde su primera instrucción, ... b) Solo es posible salir de un ciclo desde su última instrucción.

— Böhm (1964) [ 8 ]

Este diseño anticipó la defensa que hizo Dijkstra en 1968 de la programación estructurada . [ 9 ] Mientras que Dijkstra argumentaba que los programadores debían evitar las instrucciones goto, [ n 14 ] el P′′ de Böhm impedía el flujo de control no estructurado a través del diseño del lenguaje, imponiendo la estructura en la fuente en lugar de requerir una transformación posterior o disciplina del programador.

Sus resultados fueron reformulados en el teorema del programa estructurado de Böhm-Jacopini de 1966 , [ 3 ] que combinó la eliminación de selección de Böhm con el método de transformación de diagramas de flujo de Jacopini .

Relación con otros lenguajes de programación

P′′ frente a lenguajes basados ​​en WHILE

En los lenguajes de alto nivel convencionales, un bucle while ejecuta un bloque de código basado en una expresión booleana fija que se evalúa al inicio de cada iteración. La misma condición se comprueba cada vez que se ejecuta el bucle:

mientras expresión_de_condición : # cuerpo del bucle

En P′′, los bucles se escriben como(q){\displaystyle (q)}, dóndeq{\displaystyle q}es una secuencia de instrucciones. La continuación del bucle la determina dinámicamente el cabezal de la cinta: después de ejecutarq{\displaystyle q}, el programa examina el valor del cuadrado de cinta actual, que puede cambiar durante la ejecución debido a las instrucciones enq{\displaystyle q}puede mover la cabeza. Esto hace que los bucles P′′ sean más generales que los bucles de preprueba convencionales , ya que la condición del bucle está integrada en los datos en lugar de especificarse por separado. Un bucle while convencional es equivalente a un bucle P′′ solo cuando en′(′{\displaystyle '('}y′)′{\displaystyle ')'}La cabeza apunta al mismo cuadrado.

No todos los bucles P′′ se pueden transcribir trivialmente a un whilebucle estándar. Por ejemplo, la palabra(λ){\displaystyle (\lambda )}

  • no hace nada si los escaneos de cabeza inicialmente0{\displaystyle 0}; de lo contrario
  • va hacia la izquierda hasta que escanea0{\displaystyle 0}, incrementando cada casilla en su camino.

Esta palabra no se puede traducir a un whilebucle sin replantear la lógica.

Relación con Brainfuck

En la teoría del lenguaje formal , el lenguaje Brainfuck (en adelante: BF) puede considerarse como una instanciación reflejada de P′′ , donde P′′ se define con un alfabeto de tamaño256,Σ={0≡◻,1,⋯,255}{\displaystyle 256,\,\Sigma =\{0\equiv \Box ,1,\cdots ,255\}}. [ n 15 ]

Los dos lenguajes se diferencian únicamente en la orientación de sus cintas: P′′ opera sobre una cinta con sentido infinito hacia la izquierda, mientras que BF opera sobre una cinta con sentido infinito hacia la derecha. Como es habitual en los modelos tipo máquina de Turing, esta diferencia puede eliminarse reflejando la cinta e invirtiendo la dirección del movimiento del cabezal.

Según esta convención, existe una correspondencia literal uno a uno entre las instrucciones de P′′ y BF. Las operaciones aritméticas y las estructuras de bucle se conservan directamente, mientras que los movimientos del cabezal se invierten para tener en cuenta la orientación reflejada de la cinta. [ n 16 ] En otras palabras, P′′ y BF son bisimilares bajo la expansión macro con cintas/cabezales reflejados y entrada ignorada.

Correspondencia de instrucciones

Las correspondencias entre P′′ y BF pueden interpretarse como reglas de reescritura de términos bidireccionales ( no deterministas ) . Por ejemplo, el programa BF puede traducirse a P′′ de dos maneras:+>

  1. λ{\displaystyle \lambda }, aplicando la regla 4,
  2. λR{λR}255λ{\displaystyle \lambda R\{\lambda R\}^{255}\lambda }, aplicando las reglas 3 y 1.

Tenga en cuenta que los cabezales de cinta en P′′ y BF se mueven en direcciones opuestas.

Duplicación de cinta

La ejecución del programa traducido requiere una configuración de cinta duplicada. La cinta de bucle infinito izquierdo en la que opera P′′

⋯|A|B|do|D_|mi|F|GRAMO‖{\displaystyle \cdots \;|\;A\;|\;B\;|\;C\;|\;{\underline {D}}\;|\;E\;|\;F\;|\;G\;\rVert }

debe reflejarse en una cinta de sentido infinito derecho sobre la que opera BF.

‖GRAMO|F|mi|D_|do|B|A⋯{\displaystyle \lVert \;G\;|\;F\;|\;E\;|\;{\underline {D}}\;|\;C\;|\;B\;|\;A\;\cdots }

El cabezal BF se inicializa en la posición correspondiente al cabezal P′′ mediante simetría. Con esta configuración, la ejecución de un programa BF relacionado por la correspondencia de instrucciones imita el comportamiento del programa P′′ correspondiente.

En términos generales, P′′ — cuando se define con un alfabeto de tamaño 256 — se puede traducir a BF mediante

  1. reemplazando cada ocurrencia deλ{\displaystyle \lambda }con , y luego, en el programa resultante,+<
  2. invirtiendo la dirección de todas las instrucciones de movimiento del puntero <y >.

Ejemplo de traducción de P′′ a BF

Consideremos el programa P′′ del ejemplo 2 anterior:

R(R){λR}255λ({λR}255({λR}255λ({λR}255λ)){λR}255{λR}255λ)RλR{\displaystyle R(R){\{\lambda R\}^{255}\lambda }({\{\lambda R\}^{255}}({\{\lambda R\}^{255}\lambda }({\{\lambda R\}^{255}\lambda })){\{\lambda R\}^{255}}{\{\lambda R\}^{255}\lambda })R\lambda R}

eso es

R(R)λRλRλR⋯⋯⋯RλR{\displaystyle R(R)\lambda R\lambda R\lambda R\cdots \cdots \cdots R\lambda R}

La cinta

  • P′′ inicia los cálculos en una cinta poblada, con una posición de cabezal determinada.
  • BF inicia los cálculos en una cinta vacía, con el cabezal apuntando a la celda situada más a la izquierda.

Por lo tanto, el programa BF traducido primero tiene que actualizar su cinta a la copia reflejada de la cinta en la que comenzó el programa P''.

En notación biyectiva de base 255 el número35048731{\displaystyle 35048731}está codificado como(2,29,1,1)bij255{\displaystyle (2,29,1,1)_{bij255}}. [ n 12 ] En P′′, una cinta inicial puede ser (con la posición del cabezal subrayada ):

⋯|0_|2|29|1|1|0‖{\displaystyle \cdots \;\vert \;{\underline {0}}\;\vert \;2\;\vert \;29\;\vert \;1\;\vert \;1\;\vert \;0\;\rVert }

En BF, la cinta reflejada

‖0|1|1|29|2|0_|⋯{\displaystyle \lVert \;0\;|\;1\;|\;1\;|\;29\;|\;2\;|\;{\underline {0}}\;|\;\cdots }

puede ser ingresado por el código

 // Celda 0 = 0 > +  // Celda 1 = 1 > +  // Celda 2 = 1 > +++++++++++++++++++++++++++++  // Celda 3 = 29 > ++  // Celda 4 = 2 >  // Cabeza inicialmente en la celda 5

La ejecución de un programa traducido a BF transformará la cinta duplicada al estado final.

‖0|255|255|28|2|0_|0|⋯{\displaystyle \lVert \;0\;|\;255\;|\;255\;|\;28\;|\;2\;|\;{\underline {0}}\;|\;0\;|\;\cdots }

que corresponde a la codificación biyectiva en base 255 para35048730{\displaystyle 35048730}. [ n 13 ]

El programa Las correspondencias 1, 2, 3 en la tabla anterior son reglas de optimización que corresponden a la macro Ly dadas por Böhm. [ 6 ]r' Usando estos atajos , la traducción más corta a BF tiene 18 instrucciones (+ la inicialización de la cinta):r

< [ < ] > [ - [ > [ > ]] - > ] < +

Cuando no se aplica ningún atajo, la traducción más corta según las reglas tiene 4612 instrucciones, sin incluir las instrucciones necesarias para inicializar la cinta.

< [ < ] + > < + > < + > < + > < + > < + > < + >< + > < + >< + >< + >< + >< + >< + >< + >< + >< + >< + > < + >< + >< + >< + >< + >< + >< + >< + > < + > < + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + > < + >< + >< + >< + >< + >< + >< + >< + > < + > < + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + > < + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< <ai=178>+ >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< + >< +><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+>[+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><[+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+>[+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+>]]+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+><+>]<+><

Véase también

Notas y referencias

Notas
  1. ↑ Por ejemplo, pueden asignarse a unacodificación de caracteres orientada a bytes de 256 valores (por ejemplo, ASCII extendido ), como en Brainfuck (ver más abajo ).
  2. ↑ Los valores numéricos pueden asignarse a los símbolos.do0,do1,…,donorte{\displaystyle c_{0},c_{1},\dots ,c_{n}}a través de una tabla de búsqueda fija. [ n 1 ] Estas etiquetas sirven únicamente como etiquetas para la interpretación y no desempeñan ningún papel en la ejecución del programa en sí.
  3. 1 2 En particular, sii=norte{\displaystyle i=n}, el siguiente valor es0{\displaystyle 0}(envolvente).
  4. 1 2 Böhm define un predicado unario —pag{\displaystyle p}en Böhm (1964 , p. 187) , α{\displaystyle \alpha }en Böhm y Jacopini (1966 , p. 370) — eso es cierto si y solo si el cuadrado realmente escaneado (por el cabezal de la máquina de Turing) está en blanco (es decir, contiene ◻{\displaystyle \Box }) .
  5. 1 2 3 En el contexto de P′′, la repetición podría escribirse de forma equivalente utilizando la notación de corchetes.[⋅]k{\displaystyle [\,\cdot \,]^{k}}, como en Böhm (1964) . Sin embargo, dado que los corchetes ya denotan el operador de repetición (bucle) en Brainfuck, en su lugar usamos llaves.{⋅}k{\displaystyle \{\,\cdot \,\}^{k}}para indicar la repetición de una secuencia de instrucciones y evitar ambigüedades en la notación.
  6. ↑ En particular, sii=0{\displaystyle i=0}, el siguiente valor esnorte{\displaystyle n}(envolvente).
  7. ↑8=1⋅17+1⋅16+1⋅15+1⋅14+1⋅13+1⋅12+1⋅11+1⋅10{\displaystyle 8=1\cdot 1^{7}+1\cdot 1^{6}+1\cdot 1^{5}+1\cdot 1^{4}+1\cdot 1^{3}+1\cdot 1^{2}+1\cdot 1^{1}+1\cdot 1^{0}}.
  8. ↑7=1⋅16+1⋅15+1⋅14+1⋅13+1⋅12+1⋅11+1⋅10{\displaystyle 7=1\cdot 1^{6}+1\cdot 1^{5}+1\cdot 1^{4}+1\cdot 1^{3}+1\cdot 1^{2}+1\cdot 1^{1}+1\cdot 1^{0}}.
  9. ↑8=1⋅22+1⋅21+2⋅20{\displaystyle 8=1\cdot 2^{2}+1\cdot 2^{1}+2\cdot 2^{0}}.
  10. ↑7=1⋅22+1⋅21+1⋅20{\displaystyle 7=1\cdot 2^{2}+1\cdot 2^{1}+1\cdot 2^{0}}.
  11. ↑3077=4+510+2+510+1+510+2+510+3+510+510+5.{\displaystyle 3077=4+510+2+510+1+510+2+510+3+510+510+5.}
  12. 1 235048731=2⋅2553+29⋅2552+1⋅2551+1⋅2550{\displaystyle 35048731=2\cdot 255^{3}+29\cdot 255^{2}+1\cdot 255^{1}+1\cdot 255^{0}}.
  13. 1 235048730=2⋅2553+28⋅2552+255⋅2551+255⋅255035048730=2\cdot 255^{3}+28\cdot 255^{2}+255\cdot 255^{1}+255\cdot 255^{0}.
  14. ↑ Dijkstra (1968) : "El uso indiscriminado de la instrucción 'go to' tiene como consecuencia inmediata que resulta sumamente difícil encontrar un conjunto de coordenadas significativo para describir el progreso del proceso. ... La instrucción 'go to', tal como está, es demasiado primitiva; es una invitación a que el programa se convierta en un desastre."
  15. ↑ Esolang (2026) : "Al publicar el lenguaje de programación formal P'' en 1964, Corrado Böhm utilizó seis símbolos precisamente equivalentes a los comandos de lógica "brainfuck" +, -, <, >, [, y ], y proporcionó un programa explícito para cada una de las funciones básicas que, en conjunto, sirven para calcular cualquier función recursiva parcial. (Así pues, en un sentido muy real, los primeros programas "brainfuck" aparecen en el artículo de Bohm de 1964)."
  16. ↑ Esta correspondencia se basa únicamente en una inversión de la orientación de la cinta, una equivalencia estándar para modelos computacionales tipo máquina de Turing . No se requiere ninguna modificación de la semántica de BF. Bajo esta interpretación, BF sirve como una realización concreta de la máquina abstracta P′′ hasta la inversión de la cinta.
Referencias
  1. ↑ GitHub 2021 .
  2. 1 2 Böhm 1964 .
  3. 1 2 Böhm y Jacopini 1966 .
  4. ↑ Böhm 1964 , pág. 185.
  5. ↑ Böhm y Jacopini 1966 , pág. 370.
  6. ^ Böhm 1964 , págs.190, 190, 187 (nota a pie de página). 
  7. ↑ Böhm 1964 , pág. 191, Resultado principal de este artículo.
  8. ↑ Böhm 1964 , pág. 189.
  9. ↑ Dijkstra 1968 .

Bibliografía

  • Böhm, Corrado (junio de 1962). "Machine a indirizzi, dotate di un numero minimo di istruzioni" . Rendiconti dell'Accademia Nazionale dei Lincei . Classe di Scienze Fisiche, Matematiche e Naturali, Serie VIII (en italiano). 32 : 923–930 .
  • Böhm, Corrado (1964). "Sobre una familia de máquinas de Turing y el lenguaje de programación relacionado" (PDF) . Boletín ICC . 3 : 185–194 .
  • Esolang, Wiki (2026). "Brainfuck" . Esolang . Recuperado el 13 de febrero de 2026 .
  • GitHub (4 de septiembre de 2021). "PDBL: Una herramienta para la simulación de máquinas de Turing" . GitHub .
  • Yourdon, EN , ed. (1979). Clásicos en ingeniería de software . Nueva York, NY: Yourdon Press. pp.  xi, 424. ISBN 978-0-917072-14-7. LCCN 79-63449 . 
  • Elsner, Mathias. "Lenguajes de programación esotéricos: P'' en 'modo de producción'" . www.mathiaselsner.de . Consultado el 6 de diciembre de 2025 .: Demostrando la canción iterativa de 99 botellas de cerveza interpretada en las instrucciones 337568 P''.
  • Wiki de Esolangs. "P′′" . Esolangs . Consultado el 6 de diciembre de 2025 .