Cはチューリング完全だった

はじめに

本記事はCはチューリング完全か？の続きです。

結論から申し上げますと、Cはチューリング完全でした。

テストに使用したコードはこちらにあります(ubuntu18.04 で gcc -std=c11 -D_GNU_SOURCE でコンパイルしました)
https://gist.github.com/usm-takl/c5f903638daf03bc6f6a01d2d555372d

あらまし

前回「Cはチューリング完全か？」という題目でポエムを書きました。内容を要約すると、次の三点です。

• malloc では無限に object を作ることはできないので、mallocをアテにした方法では無限のメモリを用意できず、この方法では万能チューリングマシンを作れない
• 言語仕様上で再帰呼び出しの回数に制限がないことを利用し、Cは少なくともプッシュダウンオートマトンと同等の能力を持つことを示した
• Cで万能チューリングマシンを作ることは私にはできなかった

その後コメント欄やtwitterでご意見ご感想を頂きましたが、どうも私が狙っていたところと異なる受け取り方をしてしまっている方々が散見されました。これはそのような受け取り方をしてしまった方々が悪いのではなく、そもそも私がどのように問題設定をすべきか曖昧なまま、曖昧に問題設定を行い、曖昧な文章を書いてしまっていたから悪かったのです。

その後コメントを下さった方々との会話を通して、私が暗黙の内に仮定してしまっていた事柄や、問いたかった事が明確になりました。今回はそれを元に記事を書こうと思います。

問題設定

恐らく、次の様な問題設定をすべきだったのだと思います。

• チューリングマシンを目的コードとした、Cの言語仕様書に準拠するCコンパイラを考え、このCコンパイラに適切なCプログラムを与えることで、万能チューリングマシンを構成できるだろうか？

以下が、私が暗黙の内に仮定していたルールです。

• Cコンパイラは言語仕様書に書かれた規則のみを使う
  • つまり、独自拡張は許さない
• Cコンパイラは言語仕様書に書かれた制限を破ってはならない
• Cプログラムは undefined behavior を利用してはならない
• Cプログラムは #pragma を利用してはならない
• Cコンパイラの unspecified behavior は、仕様書が許す範囲内で自由に決めて良い。
• Cコンパイラの implementation-defined な規則は、仕様書が許す範囲内で自由に決めて良い
• Cコンパイラは、言語仕様書内で上限が定められていない規則を、上限がないものとして扱ってよい
  • 例えば、再帰呼び出しは無限に行える
  • 例えば、UINT_MAX を 2¹⁰²⁴-1 としてもよい(ただし自然数でなければならない)
• 「Cの言語仕様書」は n1570
  • 本来ならpublishされたものを参照すべきですがこれは許してください
• (まだあるかもしれません)

そして、以下のことをして、「Cはチューリング完全である」と言おうとしました。

• 適切なCコンパイラを想定し、そのCコンパイラに適切なCプログラムを与え、無限のメモリを扱える brainfuck インタプリタを実装する

「無限のメモリを扱える brainfuck」が万能チューリングマシンの一例であることは既に知られています(よね？)。従って、これができれば「Cはチューリング完全である」と言えます。

前回の記事では上手く行かなかったのですが、今回は上手く万能チューリングマシンを構成できました。

「無限のメモリ」に関して

万能チューリングマシンを構成するためには無限のメモリが必要です。Cで万能チューリングマシンを構成する上で、この「無限のメモリ」をどう実現するかが最も難しい点でしょう。また、これ以外に難しい点はないと言えるでしょう。従って、上手く無限のメモリを実現しさえすれば、Cがチューリング完全であることが主張できたも同然であると言えるでしょう。

Cで実行時にメモリを得る方法として malloc, calloc, realloc があります。しかし言語仕様上これらの関数では無限のメモリを表現できません。@yoh2_sdjさんの tweetや@miura1729さんのtweetなどがある通り、malloc族で無限のメモリを扱えないことは既に知られていた(あるいはすぐに受け入れられた)と思われます。

また、 @nakataSyunsuke さんの C言語: チューリング完全なのか問題という記事がありました(@tenmyo さんにコメントで教えて頂きました)。前回の私の記事とほぼ同じテーマで、こちらの記事でも結論には至っていないのですが、「Cで無限長のテープを再現できるか」という問いをたて、「考え残しがあるかもしれないが出来なさそう」という論調になっています。また、「無限の大きさのファイルを使うのは反則」という立場をとっています。

というわけで、「左右に無限の長さを持ったランダムアクセス可能なメモリを如何に実現するか」が問題の肝になります。

頂いた意見

無限の大きさのファイルを使えば万能チューリングマシンを構成できるのでは？

「無限の大きさのファイルを使えば万能チューリングマシンを構成できる」に類する意見を頂いたり観測したりしました。私自信の記事でも抜け穴として記述してあります。

私の記事や「C言語: チューリング完全なのか問題」では禁じ手としていますが、確かに「無限のメモリを仮定しておきながら無限の大きさのファイルを禁止する」というのは不条理かもしれません。「Cはチューリング完全か？」という問いの答えとするかは置いておくとして、「無限の大きさのファイルを使えばCの言語仕様書内で万能チューリングマシンを構成できる」は真であると言えるでしょう。

やり方は fseek() を使ったほぼ自明な方法です。fseek(fp, 1, SEEK_CUR) でヘッドを右へ移動し、fseek(fp, -1, SEEK_CUR) でヘッドを左に移動します。読み書きは通常通りですね。

そして @raccy さんが実際にCでbrainfuckを実装して下さりました(拍手)。

停止性を考えればテープは有限でも構わないのでは？

twitter で @fetburner さんから頂いた意見なのですが、「チューリングマシンが停止するなら実際に使われるテープの領域は有限なのでは」とのことです(…でいいのかな？)。停止性に関する議論の方法を私が知らないので「なるほど」としか言えませんでした(twitterで会話したときは理解した気になっていたけれども、後から理解できていないことに気が付きました。せっかくご意見を頂けたのにすみません)。

thread を使えば良いのでは？

twitter での @miura1729 さんとの会話で思いついた、そして @as_capabl さんにコメントで指摘して頂いた、 thread を使う方法があります。ちょっと面白いと思うので、本記事ではこれを中心に解説しようと思います。

本編: C11で追加された threads.h の機能を使えばCで万能チューリングマシンを構成できる

本記事の本編です。threads.h の機能を使って万能チューリングマシンを構成します。

前回の記事でプッシュダウンオートマトンを構成しました。つまり、Cで無限の長さを持つスタックを構成することはできました。無限の長さを持つスタック二本と有限オートマトンで万能チューリングマシンを構成できることが一般に知られています。本記事ではこれを利用することで brainfuck インタプリタを実現しようと思います。

チューリングマシンのおさらい

よくある無限のテープ+ヘッドおよびbrainfuckを用いてチューリングマシンを説明したいと思います。

形式的な定義はwikipediaに譲るとして、チューリングマシンの構成要素は

• 左右に無限のテープ
• 入力テープを読みつつ無限のテープを読み書きするヘッド

である、とよく説明されます。詳細は端折りますが、brainfuckというプログラミング言語がほぼチューリングマシンそのものであるため、brainfuckとチューリングマシンを同一視することも多いです。非常に雑な話ですが、それに倣って brainfuck の説明を持ってチューリングマシンの説明に代えさせて頂きたいと思います。

wikipediaでのbrainfuckの言語仕様は以下の通りです。

処理系は次の要素から成る: Brainfuckプログラム、インストラクションポインタ（プログラム中のある文字を指す）、少なくとも30000個の要素を持つバイトの配列（各要素はゼロで初期化される）、データポインタ（前述の配列のどれかの要素を指す。最も左の要素を指すよう初期化される）、入力と出力の2つのバイトストリーム。

1. > ポインタをインクリメントする。ポインタをptrとすると、C言語の「ptr++;」に相当する。
2. < ポインタをデクリメントする。C言語の「ptr--;」に相当。
3. + ポインタが指す値をインクリメントする。C言語の「(*ptr)++;」に相当。
4. - ポインタが指す値をデクリメントする。C言語の「(*ptr)--;」に相当。
5. . ポインタが指す値を出力に書き出す。C言語の「putchar(*ptr);」に相当。
6. , 入力から1バイト読み込んで、ポインタが指す先に代入する。C言語の「*ptr=getchar();」に相当。
7. [ ポインタが指す値が0なら、対応する ] の直後にジャンプする。C言語の「while(*ptr){」に相当。
8. ] ポインタが指す値が0でないなら、対応する [ （の直後^[1]）にジャンプする。C言語の「}」に相当^[2]。

brainfuck の仕様では「少なくとも30000個の要素を持つバイトの配列」とありますが、「本記事では左右に無限の長さを持つバイトの配列」になります。

さて、T をテープ、I を命令列、 v をデータポインタおよびインストラクションポインタとして、AAで brainfuck の動作の具体例を説明しましょう。まず、brainfuckでは要素は全て 0 で初期化されます。Tとvの状態は次のようになります。

               v
T: ... 0 0 0 0 0 0 0 0 0 ...

それでは "+>++" というプログラムを実行する例を見てみましょう。
次のようになります。

               v                 v
T: ... 0 0 0 0 0 0 0 0 0 ...  I: +>++

  ↓ "+" を実行
               v                  v
T: ... 0 0 0 0 1 0 0 0 0 ...  I: +>++

  ↓ ">" を実行
               v                   v
T: ... 0 0 0 1 0 0 0 0 0 ...  I: +>++
注) ポインタが右に移動 = テープ全体が左に移動

  ↓ "+" を実行
               v                    v
T: ... 0 0 0 1 1 0 0 0 0 ...  I: +>++

  ↓ "+" を実行
               v                     v
T: ... 0 0 0 1 2 0 0 0 0 ...  I: +>++

  ↓
次の命令がないので実行終了

繰り返しの例も見てみましょう。 "++[-]+"

               v                 v
T: ... 0 0 0 0 0 0 0 0 0 ...  I: ++[-]+

  ↓ "++" を実行
               v                   v
T: ... 0 0 0 0 2 0 0 0 0 ...  I: ++[-]+

  ↓ "[" を実行(ヘッダの指す位置が0でないので、単に次の命令に進む)
               v                    v
T: ... 0 0 0 0 2 0 0 0 0 ...  I: ++[-]+

  ↓ "-" を実行
               v                     v
T: ... 0 0 0 0 1 0 0 0 0 ...  I: ++[-]+

  ↓ "]" を実行(ヘッダの指す位置が0でないので、対応する[の次に移動)
               v                    v
T: ... 0 0 0 0 1 0 0 0 0 ...  I: ++[-]+

  ↓ "-" を実行
               v                     v
T: ... 0 0 0 0 0 0 0 0 0 ...  I: ++[-]+

  ↓ "]" を実行(ヘッダの指す位置が0なので、次の命令に進む)
               v                      v
T: ... 0 0 0 0 0 0 0 0 0 ...  I: ++[-]+

  ↓ "+" を実行
               v                       v
T: ... 0 0 0 0 1 0 0 0 0 ...  I: ++[-]+

  ↓
次の命令がないので実行終了

これぐらいで十分でしょうか。brainfuckインタプリタは世の中にたくさんありますので、触ってみるのもいいでしょう。また、(メモリ無限はともかくとして)自分で実装してみるのもいいと思います。非常に簡単な機械ですが、これでいわゆる計算機なら何でもシミュレートできるというのですから、驚くべきことです。

無限のスタック2本(とセルひとつ)で無限のテープを実現する

さて、これから無限のスタックふたつとセルひとつを使って無限のテープを作成します。

実は結構簡単にできてしまいます。

通常スタックは空から始まりますが、今回のスタックは初期状態で無限に 0 が積まれているスタックを考えます。
このスタックを2本用意し、片方をL、もう片方をRと名付けます。また、1つだけ数を保持できる C を用意します。

そして、 brainfuck の仕様を次の様に読み替えます。

• < を実行すると、 C の値を L に push し、 R から pop した値を C に代入する
• > を実行すると、 C の値を L に push し、 R から pop した値を C に代入する
• +, -, ., , の操作は C に対して行う
• [ と ] は C の値が 非0 / 0 だったら～とする

これで brainfuck と同等の動作が実現できます。

例として +++<++>+> を実行してみましょう。
brainfuck の説明のときに使った T と、スタック2本で実現した L, C, R の両方を AA で表示しています。

               v                v
T: ... 0 0 0 0 0 0 0 0 0 ...  I:+++<++>+>
L: ... 0 0 0 0
C: 0
R: ... 0 0 0 0

  ↓ "+++" を実行
               v                   v
T: ... 0 0 0 0 3 0 0 0 0 ...  I:+++<++>+>
L: ... 0 0 0 0
C: 3
R: ... 0 0 0 0

  ↓ "<" を実行(C の値を L に PUSH し、 R から POP した値を C に代入)
               v                   v
T: ... 0 0 0 3 0 0 0 0 0 ...  I:+++<++>+>
L: ... 0 0 0 3
C: 0
R: ... 0 0 0 0

  ↓ "++" を実行
               v                      v
T: ... 0 0 0 3 2 0 0 0 0 ...  I:+++<++>+>
L: ... 0 0 0 3
C: 2
R: ... 0 0 0 0

  ↓ ">" を実行(C の値を R に PUSH し、 L から POP した値を C に代入)
               v                       v
T: ... 0 0 0 0 3 2 0 0 0 ...  I:+++<++>+>
L: ... 0 0 0 0
C: 3
R: ... 0 0 0 2

  ↓ "+" を実行
               v                        v
T: ... 0 0 0 0 4 2 0 0 0 ...  I:+++<++>+>
L: ... 0 0 0 0
C: 4
R: ... 0 0 0 2

  ↓ ">" を実行(C の値を R に PUSH し、 L から POP した値を C に代入)
               v                         v
T: ... 0 0 0 0 0 4 2 0 0 ...  I:+++<++>+>
L: ... 0 0 0 0
C: 0
R: ... 0 0 2 4

  ↓
次の命令がないので実行終了

brainfuck との対応が取れていることが一目瞭然ですね。初期状態で 0 が無限に詰まったスタックを2本用意できれば、brainfuckを実装できてしまうのです。

C の thread で無限のスタックを実現

再帰を使えば容量無限のスタック1本を実現できることは前回の記事で示しました(ここに対する疑義は見当たらなかったので、たぶん大丈夫だと思います)。

では2本のスタックを用意するにはどうしたら良いでしょうか。実はC11で標準に threads.h が追加され、thread が使えるようになったのです。言語仕様書を眺めた限り各 thread での関数呼出の回数に制限はなさそうでしたので、 thread を2本用意すれば前回の議論と同じ方法で長さ無限のスタックを2本用意することができます。さっそく threads.h を試してみましょう。

$ cat th.c
#include<threads.h>
$ gcc th.c -std=c11
th.c:1:20: fatal error: threads.h: そのようなファイルやディレクトリはありません
compilation terminated.

...gcc(glibc?)ですら対応していないようです...(言語仕様書を読むと処理系が __STDC_NO_THREADS__ を定義すれば実装しなくて良いことになっている)。

が。twitterで@yohhoyさんから教えて頂きました。yohhoyさん作のthreads.hが既にあります。これを使うことにしました。

さて、「初期状態で 0 が無限に詰まった」スタックをどう実現するかですが、これも実は簡単でスタックが空なら 0 を POP するように作るだけです。

というわけで、いきなり実装をぽんと置いてしまいます。

enum stack_command {
  STACK_COMMAND_NONE,
  STACK_COMMAND_PUSH,
  STACK_COMMAND_POP,
};

struct stack {
  thrd_t thrd;
  volatile enum stack_command command;
  volatile int argument;
  cnd_t cnd;
  mtx_t mtx;
};

void stack_not_empty(struct stack *stack, int cell) {
  stack->command = STACK_COMMAND_NONE;
  cnd_signal(&stack->cnd);

  while (1) {
    switch (stack->command) {
    case STACK_COMMAND_NONE:
      cnd_wait(&stack->cnd, &stack->mtx);
      break;
    case STACK_COMMAND_PUSH:
      stack_not_empty(stack, stack->argument);
      break;
    case STACK_COMMAND_POP:
      stack->argument = cell;
      stack->command = STACK_COMMAND_NONE;
      cnd_signal(&stack->cnd);
      return;
    }
  }
}

void stack_empty(struct stack *stack) {
  while (1) {
    switch (stack->command) {
    case STACK_COMMAND_NONE:
      cnd_wait(&stack->cnd, &stack->mtx);
      break;
    case STACK_COMMAND_PUSH:
      stack_not_empty(stack, stack->argument);
      break;
    case STACK_COMMAND_POP:
      stack->argument = 0;
      stack->command = STACK_COMMAND_NONE;
      cnd_signal(&stack->cnd);
      break;
    }
  }
}

int stack_start(void *stack_) {
  struct stack *stack = stack_;
  mtx_lock(&stack->mtx);
  stack_empty(stack);
  return 0;
}

void stack_init(struct stack *stack) {
  stack->command = STACK_COMMAND_NONE;
  cnd_init(&stack->cnd);
  mtx_init(&stack->mtx, mtx_plain);
  mtx_lock(&stack->mtx);
  thrd_create(&stack->thrd, stack_start, stack);
}

void stack_push(struct stack *stack, int i) {
  stack->command = STACK_COMMAND_PUSH;
  stack->argument = i;
  cnd_signal(&stack->cnd);
  cnd_wait(&stack->cnd, &stack->mtx);
}

妙に長いですが、ほとんどはスレッドの同期のためだけのコードです。実態としてはほぼ次のような感じです。

void stack_not_empty(struct stack *stack, int cell) {
  while (1) {
    switch (GET_NEXT_COMMAND(stack)) {
    case STACK_COMMAND_PUSH:
      stack_not_empty(stack, stack->argument); // 再帰呼び出しで PUSH を表現
      break;
    case STACK_COMMAND_POP:
      stack->argument = cell; // stack の top の値を返す
      return; // return で POP を表現
    }
  }
}

void stack_empty(struct stack *stack) {
  while (1) {
    switch (GET_NEXT_COMMAND(stack)) {
    case STACK_COMMAND_PUSH:
      stack_not_empty(stack, stack->argument); // 再帰呼び出しで PUSH を表現
      break;
    case STACK_COMMAND_POP:
      stack->argument = 0; // stack が空のときは 0 を POP したことにする
      break;
    }
  }
}

使い方ですが、

• stack_create で stack として動作する thread を作成
• stack_push で stack に値を push
• stack_pop で stack から値を pop

これだけです。

ところで引数の struct stack *stack と int cell が気になる方が居られるかもしれません。これは @miura1729 さんから twitter で頂いた「ローカル変数はレジスタに格納しても合法なのだから&演算子でアドレスを取らなければ(これは静的に分かる)、アドレスを持つ必要は仕様上ないのではないだろうか？」という意見に甘えさせて頂きました。

仮に int cell を容認しないことにしたとしても、無限個の int の stack を object なしで作成できることは前回の記事で実証済みですし、struct stack *stack を容認しないことにしても、Lスタック用とRスタック用に関数をコピペすれば済む話です。いずれにせよ「万能チューリングマシンを構成できるか？」という問いに答える上での問題にはならないと考えます。

brainfuck 本体を作る

もう簡単ですね。コード貼ります。もうほぼそのままです。プログラムは gcc の -D オプションで PROG を #define して渡すようになっています。ちなみに、ですが「ちょっと動かしてみるのに便利」と言う理由で「;」コマンドが追加されています。これはヘッドの位置にある数値を数として表示するコマンドです。

const char * const prog = PROG;

const char *back(const char *ip) {
  int nest = 0;

  while (1) {
    if (ip == prog) {
      printf("invalid ']'\n");
      exit(EXIT_FAILURE);
    }

    switch (*--ip) {
    case '[':
      if (nest == 0) return ip;
      --nest;
      break;
    case ']':
      ++nest;
      break;
    default:
      break;
    }
  }
}

const char *forth(const char *ip) {
  int nest = 0;

  while (1) {
    switch (*ip++) {
    case '\0':
      printf("invalid '['\n");
      exit(EXIT_FAILURE);
    case '[':
      ++nest;
      break;
    case ']':
      if (nest == 0) return ip;
      --nest;
      break;
    default:
      break;
    }
  }
}

int main() {
  struct stack ls, rs;
  stack_init(&ls);
  stack_init(&rs);

  int cell = 0;
  const char *ip = prog;

  while (1) {
    switch(*ip++) {
    case '\0':
      return 0;
    case '+':
      ++cell;
      break;
    case '-':
      --cell;
      break;
    case ';':
      printf("[%d]", cell);
      fflush(stdout);
      break;
    case '.':
      printf("%c", cell);
      fflush(stdout);
      break;
    case ',':
      cell = getchar();
      break;
    case '>':
      stack_push(&ls, cell);
      cell = stack_pop(&rs);
      break;
    case '<':
      stack_push(&rs, cell);
      cell = stack_pop(&ls);
      break;
    case '[':
      if (cell == 0) ip = forth(ip);
      break;
    case ']':
      if (cell != 0) ip = back(ip - 1) + 1;
      break;
    default:
      break;
    }
  }
}

試してみましょう。ubuntu 18.04 での実行例です(警告を消したい方は -Wno-pointer-to-int-cast -Wno-int-to-pointer-cast を追加してください)。

$ # 一重ループ
$ gcc bf.c -std=c11 -lpthread -D_GNU_SOURCE '-DPROG="+++[-;]"' && ./a.out
[2][1][0]
$ # 二重ループ
$ gcc bf.c -std=c11 -lpthread -D_GNU_SOURCE '-DPROG="+++[>+++[-;]<-]"' && ./a.out
[2][1][0][2][1][0][2][1][0]
$ # Hello World!
$ cat hello.bf
>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-]<.>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.[-]>++++++++[<++++>-]<+.[-]++++++++++.
$ gcc bf.c -std=c11 -D_GNU_SOURCE -DPROG=\"`cat hello.bf`\" && ./a.out
Hello World!

動いてるっぽいです。

結論

というわけで、 c11 で追加された threads.h があれば brainfuck を実装できるようです。
厳密な証明をしたわけではありませんが、c11はチューリング完全であることが示せたと思います。
やったね！

次の問題

さて、「無限の大きさを持つファイル」を使う方法と「threads.h」を使う方法と、2種類の方法で、Cで万能チューリングマシンを構成することができました。ところでファイルも threads.h もCの言語仕様書で言う hosted environment 用のライブラリとされています。それでは

「freestanding environment で最低限サポートしなければならないとされたライブラリだけで万能チューリングマシンを構成することはできるか？」

というのが次の問題になるかと思います。どなたかチャレンジしてみてください。前回の私の記事の手法を用いれば、とりあえずプッシュダウンオートマトンまでは構築できそうです。
(注: c11 の freestanding environment で提供しなければならない標準ライブラリは <float.h>, <iso646.h>, <limits.h>, <stdalign.h>, <stdarg.h>, <stdbool.h>, <stddef.h>, <stdint.h>, <stdnoreturn.h> だけです。)

謝辞

(IDのasciiコード順)
@akinomyoga さんとの twitter 上でのやりとりは私の理解を整理する上で大いに役立ちました。
@as_capabl さんは thread を使用することで無限のメモリにランダムアクセスできる可能性を指摘して頂きました。
@fetburner さんは私の気付いていなかった停止性という観点を与えてくれました。
@miura1729 さんとの twitter 上でのやりとりで thread を使う方法を思いつきました。また、私の理解を整理する上で大いに役立ちました。
@nakataSyunsuke さんの記事は私の説の補強に役立ちました。
@raccy さんはファイルを使って brainfuck を実装して下さいました。
@tenmyo さんには私の文章の曖昧な点や不十分な点を指摘していただきました。
@y_futatuki さんは twitter 上で @miura1729 さんと共に私の記事の検証をしてくださっていました。その結果は私を勇気付けました。
@yoh2_sdj さんは twitter 上で私の記事の誤りを指摘して下さいました。
@yohhoy さん作の threads.h がなければ実装に苦労しいただろうと思います。
皆様に感謝いたします。
その他、捕捉しきれていませんが、様々な場所でコメントを下さった方々にも感謝いたします。