Route 477

■ [esolang] P''に関する最初の論文を探しています

http://q.hatena.ne.jp/1221708568#c131059 のshiroさんのコメントから知ったんですが、 brainf*ckの元となったP''(P prime prime)という言語が存在するんですね。

P''はチューリング・マシンをモデルにした言語で、「R」と「λ」と「()」のみから出来ています。

可能な操作は

• R: ヘッドを右に1移動 (※P''ではテープは左側にのみ無限長。右端では移動できないので単に何もしない)
• λ: ヘッド位置の値をインクリメントして左に1移動 (※上限に達したら0に戻る)
• ( ): while。ヘッド位置の値が0でない間、括弧内のコードを繰り返す

となっています。(厳密にはテープに書かれるのは数値とは決まって無くて、{a0, a1, .. an}という記号の集合とされています)

んでぱっと見ではbrainf*ckより貧弱そうなんですが、

• r: λ R
• r': r r r r ... r (rをn回行う)
• L: R' λ

と定義することによって、brainf*ckの [ ] + - < > が ( ) r r' L R に対応するので、実はbrainf*ckと同じ能力を持つと。(IOは除く)

記号がn+1個なので、rをn回行うと一周してデクリメントすることになる、というのがポイントですね。(+1しか用意しないというのはGrassも一緒ですけど、うえのさんはP''を知っていたのだろうか)

何の話だっけ、そうだ、Wikipediaで触れられている論文1「On a family of Turing machines and the related programming language」が検索しても 見つからないのですよ。1964年と古い論文だから残ってないのだろうか…。どなたか入手手段をご存じの方がおられましたらご一報ください。メールアドレスはyhara.at.kmc.gr.jpです。

(追記: 「元となった」は嘘かも知れません。「brainf*ckの作者がP''を意識していたかは定かではない」って書いてますね。)