P′′

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

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

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

1. ${\textstyle R}$ と ${\textstyle \lambda }$ は P′′ のワードである。
2. もしも ${\textstyle q_{1}}$ と ${\textstyle q_{2}}$ が P′′ のワードならば、それらを繋げた ${\textstyle q_{1}q_{2}}$ も P′′ のワードである。
3. もしも ${\textstyle q}$ が P′′のワードならば、${\textstyle (q)}$ も P′′ のワードである。
4. 以上の3つの法則から得られるワードだけが P′′ のワードである。

• ${\textstyle \{\Box ,c_{1},c_{2},\ldots ,c_{n}\}}$ は無限長のテープを搭載したチューリングマシンのテープ・アルファベット（テープに書かれるデータの種類）である。${\textstyle \Box }$ は空白の記号であり、${\textstyle c_{0}}$ と等価である。
• P′′ の全命令は、全てのあり得るテープの構成の集合 ${\textstyle X}$ の順列である。つまり、テープの内容とテープヘッドの位置の両方を考慮した全てのあり得る構成である^{[注釈 1]}。
• ${\textstyle \alpha }$ は述語（値を受け取ってから真偽が決定するもの）であり、現在位置のシンボルは ${\textstyle \Box }$ ではないことを示している。これは命令ではなく、プログラム中で使用されない。しかし、その代わりとして言語の定義を補助するために使われる。
• ${\textstyle R}$ は、（可能であれば）1セル分テープヘッドを右方向へ移動することを意味する。
• ${\textstyle \lambda }$ は、現在位置のシンボル ${\textstyle c_{i}}$ を ${\textstyle c_{(i+1){\bmod {(}}n+1)}}$ に置き換える（つまり、現在位置のシンボルが ${\textstyle c_{n}}$ のときは ${\textstyle c_{0}}$ に置き換えられる）。そして、テープヘッドを1セル分左方向へ移動することを意味する。
• ${\textstyle q_{1}q_{2}}$ は関数の合成 ${\textstyle q_{2}\circ q_{1}}$ を意味する。言い換えると、命令 ${\textstyle q_{1}}$ は ${\textstyle q_{2}}$ の前に実行される。
• ${\textstyle (q)}$ は、条件 ${\textstyle \alpha }$ が成立している間だけ while ループで ${\textstyle q}$ を反復することを意味する。

• 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 }$ の上にヘッドが位置することになる。