P′′

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

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

定義

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

文法

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

意味論

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

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

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

プログラムの例

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

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

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

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

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