P′′ （P double prime：ピーダブルプライム^[1]）は1964年にコラド・ベーム^[2][3]によって作成された、チューリングマシンの一種を記述するための言語である。

チューリングマシンを記述するがゆえにその仕様は原始的である。チューリングマシンにもかかわらず、状態遷移はテープの内容とテープヘッドの位置だけで表現されるので、有限オートマトンの概念が希薄である。

定義

${\textstyle {\mathcal {P}}^{\prime \prime }}$ (以下 P′′)は以下のように4つの命令アルファベット ${\textstyle \{R,\lambda ,(,)\}}$ におけるワードの集合として形式的に定義される（formally defined）。

他のプログラミング言語との関連

• Brainfuck 言語は、P′′ の^{[注釈 2]}非形式的な変種（informal variation）である（Brainfuck はテープの代わりにメモリを使うので、I/Oを扱わないところは異なる）。ベームはあらゆる計算可能関数を計算するのに十分な基本関数の集合のそれぞれに対して明確な P′′ のプログラムを提供している。使用したものは ${\textstyle (}$, ${\textstyle )}$ そして4つのワード ${\textstyle r\equiv \lambda R}$、 ${\textstyle r^{\prime }\equiv r^{n}}$（ここで ${\textstyle r^{n}}$ は ${\textstyle r}$ の ${\textstyle n}$ 回の反復である）、 ${\textstyle L\equiv r^{\prime }\lambda }$、 ${\textstyle R}$ だけである。これらは6つの Brainfuck の命令 [, ], +, -, <, > と等価である。注意するべきは、${\textstyle c_{n+1}\equiv c_{0}\equiv \Box }$ なので、現在位置のシンボルをn回インクリメントするとラップアラウンド（${\textstyle c_{n}}$ をインクリメントすると ${\textstyle c_{0}}$になること）する。そのため、一つの ${\textstyle r^{\prime }}$ によって、その結果は現在位置のシンボルをデクリメントすることになる（訳注：テープ・アルファベットは n+1 種類あるので、n回インクリメントするとラップアラウンドして1つ少ない数のテープ・アルファベットになる）。

プログラムの例

ベーム^[2]は、x > 0 を満たす整数xの前の数 (x-1) を計算する以下のプログラムを提供している。

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

これを等価のBrainfuckのプログラムに直接変換すると、

 >[>]<[−[<[<]]−<]>+

このプログラムは bijective base-k 記法で表現されているある一つの整数を想定している。${\textstyle c_{1},c_{2}\ldots ,c_{k}}$ は ${\textstyle 1,2,\ldots ,k}$ にそれぞれエンコードされる。そして、数字列の前後に ${\textstyle \Box }$ がある（例えば、bijective base-2 の場合、数字の8は ${\textstyle \Box c_{1}c_{1}c_{2}\Box }$ とエンコードされる。なぜなら、bijective base-2 において8は112である）。計算の最初と最後に数字列の前にある ${\textstyle \Box }$ の上にヘッドが位置することになる。

注釈

出典