Cはチューリング完全か？

逃げ口上

雑な記事です。

はじめに

ときどき「プログラミング言語と呼ぶための条件とは」のような話題が出ることがあります。よくある回答としては「チューリング完全ならプログラミング言語と呼べるんじゃないの」あたりでしょうか。「まあ、それはそうかな」とも思います。しかし、あるときCの言語仕様書を読んでいてふと思いました。

「Cはチューリング完全なんだろうか？」

実は結構怪しいのでは、と思いました。本記事ではなぜ怪しいと思うに至ったか、経緯などをてきとうに書いてみようと思います。

ちなみに自然言語で書かれた701頁に及ぶ仕様書を数学的に厳密に、というのはそもそも無茶な話なので、あまり結論にはこだわってません。というか中途半端な終わり方になっています。「こんなことを考えました」程度のポエムと受け取って頂ければ幸いです。

前提知識

前提知識1. チューリング完全とは

チューリング完全

まずチューリング完全の説明です。

とりあえずwikipedia のチューリング完全のページから引きます(5/21閲覧)。

計算理論において、ある計算のメカニズムが万能チューリングマシンと同じ計算能力をもつとき、その計算モデルはチューリング完全（チューリングかんぜん、Turing-complete）あるいは計算完備であるという。

説明そのままですね。万能チューリングマシンと同じ計算能力をもつことをチューリング完全と呼びます。

余談

ところでこのページにも書いてありますね。
   コンピュータ言語のうち、少なくともチューリング完全でなければプログラミング言語とは呼ばれない。
だそうです。

チューリングマシン

では万能チューリングマシンとは何でしょうか、という説明の前に、ただのチューリングマシンの説明をします。

これもまたwikipedia のチューリングマシンのページから引きます(5/21閲覧)。

チューリングマシンには、いわゆるハードウェアに相当するものとして、

1. その表面に記号を読み書きできるテープ。長さは無制限（必要になれば順番にいくらでも先にシークできる）とする
2. （テープに記号を読み書きするヘッド）
3. ヘッドによる読み書きと、テープの左右へのシークを制御する機能を持つ、有限オートマトン

がある。
また、ソフトウェアに相当するものとして、以下がある。
(以下略)

この説明は厳密ではありませんし、チューリングマシンの定義には亜種が多数あるらしいのですが、その辺置いておくとして、良く知使われる説明です。

これを更に、雑かつ乱暴に要約すると、「何かのソフトウェアがインストールされた ランダムアクセス可能な無限のメモリ とCPUからなる計算機」となります。

万能チューリングマシン

これも先ほどと同じ wikipedia のチューリングマシンのページから引きます。

遷移規則をうまく構成することで、驚くべきことに「いかなるチューリングマシンであろうとも、それを模倣することが可能なチューリングマシン（万能チューリングマシン）」が可能である。万能チューリングマシンは、与えられた、別のチューリングマシンを記述した記号列と、そのチューリングマシンへの入力記号列を読みこみ、それに従って動く。（エミュレータの原理）

これも雑かつ乱暴な要約をすると、万能チューリングマシンというのは「ランダムアクセス可能な無限のメモリとCPUからなる計算機にどんなソフトウェアが載っていようとエミュレートできるエミュレータ」です。

チューリング完全な言語とは

というわけで雑かつ乱暴にまとめますと、「チューリング完全な言語」というのは「ランダムアクセス可能な無限のメモリとCPUからなる計算機をエミュレートするエミュレータ」を書ける言語です。

前提知識2: チョムスキー階層

チョムスキー階層というやつがあります。オートマトンの強さを議論するのにちょくちょく参照されます(本当は形式文法のあれこれを表現するために導入されたのですが、深く立ち入りません)。オートマトンの強さはここにあるものだけではないのですが、チューリングマシンが最上位にあるのでこれを参照して議論しましょう。チョムスキー階層では強い方から順に次の4種にオートマトンを分類しています。

• チューリングマシン
• 線形拘束オートマトン
• プッシュダウンオートマトン
• 有限オートマトン

これもまた雑な説明ですが、有限オートマトンがいわゆる正規表現に対応します。正規表現の性質として、「入力の(と)が対応しているかを判別できない」というものがあります。Perlの正規表現等ではできてしまいますが、あれは有限オートマトンより強くなるような拡張が入っているからで、計算機科学用語的にはあれは正規表現より強い何かです。

プッシュダウンオートマトンを雑に説明すると、無限に伸びることができるスタックを１つ持つ有限オートマトンです。今回の記事ではCはプッシュダウンオートマトン以上の表現力をもっているはずだ、というところまでいきます。

線形拘束オートマトンはいわゆる普通のプログラミング言語によく似ている（メモリが有限）という雑な説明がされることがあります。

チューリングマシンは < と > が無限に使える brainfuck に対応します。つまり < と > が無限に使える brainfuck を実装できたら、その言語はチューリング完全と言えます。

本編

事の発端: malloc では無限のメモリを扱えない

事の発端は「Cでは無限のメモリを扱えないんじゃないか？」という疑問を抱いたことです。

普段雑に「メモリ」と読んでいる者はCの仕様書上では object と言います(細かいことはおいておきます)。実行時に object を増やそうと思ったら malloc(とcalloc,realloc) を使いますよね。ところで malloc では 無限のメモリ を扱えません。

なぜか。sizeof と SIZE_MAX の存在です。sizeof 式の型は size_t で、その上限は SIZE_MAX です。ということは言語仕様上 sizeof(void *) の大きさにも上限があることになります。すると void * で表現可能な object の数に上限があるということになりますね。ここで malloc の返却値の型は void * です。ということは、 malloc では言語仕様上無限のメモリを扱えない。むしろ 扱ってはいけない ということになるのです。malloc で扱えるメモリの上限は言語仕様上 SIZE_MAX * CHAR_BITS bitなのです malloc が作成した object は同時に最大で 2のsizeof(void *) * CHAR_BITS乗個までしか存在できません(5/23 19:00 修正: twitter で誤りを yoh2_sdj さんにご指摘いただきました)。

さあ困りました。これでは「標準入力を読み(と)の対応が取れているか調べよ」という学校の課題程度のプログラムすら書けません。SIZE_MAX が 2⁶⁴-1 で CHAR_BITS が 8 とすると、内部的に malloc を使った多倍長整数ライブラリを使ったとしても、147573952589676412928個の(が連続して入ってきたら、破綻してしまうのです。(5/23 19:00打消し: 数字が盛大に間違っていました。上限があることは正しいと思います)

通常の変数の併用

malloc だけでダメなら通常の変数を併用したらよいのでは？と考えるかもしれません。しかしコンパイルできるCのソースコードは有限の長さを持ちます。するとソースコード上で宣言できる変数の個数は有限ということになります。通常の変数を併用するとしても、ソースコードの長さが有限である以上、定数倍にしかなりません。無限のメモリには程遠い状況です。

再帰呼出

すこし頭をひねって有限個の宣言で無限子の object を作る方法を思いつきました。再帰呼び出しです。通常Cでは再帰呼び出しをし過ぎるとスタックオーバーフローを起こして異常終了するとされています。しかし注意していただきたいのは、Cでは言語仕様上は再帰呼び出しの回数は制限されていないということです。ということは、言語仕様上は無限に再帰呼び出しが可能であっても良いのです。

&演算子

しかし少し考えるとダメでした。Cには&演算子というものがあり、 object への pointer を取ることができます。そしてどのような object への pointer も void * 型への変換が許されています。malloc のときと同じ論法で、同時に存在しうる object の個数に上限ができてしまいます。addressable な object は有限個しか作成できないということです。状況が更に厳しくなってしまいました。

Cのプログラムは正規表現と同程度の能力しか持たないのでしょうか？

object を使わないメモリで自然数(非負の整数)ひとつを表す

「これはまずい。Cはプログラミング言語どころか正規表現ということになってしまう。それは避けたい。」そういう思いから更に頭をひねることにしました。結果思いついたのが再帰呼び出しそのものをメモリとして利用する方法です。

関数呼び出しから帰ってくると、元の場所に戻ってきます。つまり、どこかに元の場所が記録されているのです。言語仕様上この「どこか」は規定されていませんが、何かを記録できるのです。これを利用して(と)の対応を取ることができます。やってみましょう。

#include<stdio.h>
#include<stdlib.h>
void f() {
    while (1) {
        switch(getchar()) {
        case EOF:
            exit(1);
        case '(':
            f();
            break;
        case ')':
            return;
        }
    }
}
int main() {
    while (1) {
        switch(getchar()) {
        case EOF:
            exit(0);
        case '(':
            f();
            break;
        case ')':
            exit(1);
        }
    }
}

雑な説明です。

• getchar() が入力に、exit(0) が accept に、 exit(1) が reject に対応しています。
• f() と main() の内部では変数宣言を行っていませんので、void *の制限には引っかかりません。
• f() を呼び出すことで ( がひとつ増えたことを記録します。
• return することで ( がひとつ減ったことを記録します。

実行してみましょう。

実行例

$ echo '((()()))' | ./a.out ; echo $?
0
$ echo '((()' | ./a.out ; echo $?
1
$ echo '(()))' | ./a.out ; echo $?
1
$ echo '' | ./a.out ; echo $?
0

うごきます。言語仕様上は の話ですがCは 無限のメモリ を扱えるのです。

Cは正規表現よりは強いのです！(いやまあ、厳密な話はできてませんが)

プッシュダウンオートマトンを構築する

先ほど実現したプログラムでCのプログラムでは加算無限個の状態を取り得ることがわかりました。しかし、このテクニックではカウンタがひとつしか作成できず、そのカウンタが0か0以外かしか判定できません。メモリが無限にあるにも関わらず読み書きの方法が非常に限られてしまっているんですね。

しかし、Cの関数呼び出しはスタック的な性質を持っていますし、既にいくらでも数を数えらえることはわかっています。もう少し強力なものができないでしょうか？

ということでひねり出しました。プッシュダウンオートマトンです。brainfuck の劣化版みたいなものが作れます。

仕様はこんな感じです。

• > stack に 0 を push する。
• < stack を pop する。
• + stack の top をインクリメントする。
• - stack の top をデクリメントする。
• . stack の top を出力に書き出す。
• , 入力から数を読み込んで stack の top に書き込む。
• [ stack の top が 0 なら、対応する ] の直後にジャンプする。
• ] 対応する [ にジャンプする。

実装はこんなんです。

#include<stdio.h>
#include<stdlib.h>

const char program[] = PROG;
const char *ip = program;
int tos;

void st(void);

void push(void) {
  if (tos) {
    --tos;
    push();
    ++tos;
  } else {
    st();
  }
}

// jump to the corresponding '['
void back(void) {
  --ip;
  while (1) {
    if (ip == program) {
      printf("unmatched ]");
      exit(1);
    }

    switch(*--ip) {
    case '[':
      return;
    case ']':
      back();
      break;
    default:
      break;
    }
  }
}

// jump to the next of the corresponding ']'
void forth(void) {
  if (tos) return;

  while (1) {
    switch (*ip++) {
    case '\0':
      printf("unmatched [");
      exit(1);
    case '[':
      forth();
      break;
    case ']':
      return;
    default:
      break;
    }
  }
}

// the stack is not empty
void st(void) {
  while (1) {
    switch(*ip++) {
    case '\0':
      exit(0);
    case '>':
      push();
      break;
    case '<':
      tos = 0;
      return;
    case '+':
      ++tos;
      break;
    case '-':
      --tos;
      break;
    case '.':
      printf("%d\n", tos);
      break;
    case ',':
      scanf("%d", &tos);
      break;
    case '[':
      forth();
      break;
    case ']':
      back();
      break;
    }
  }
}

// the stack is empty
int main() {
  while (1) {
    switch(*ip++) {
    case '\0':
      exit(0);
    case '>':
      st();
      break;
    case ']':
      back();
      break;
    case '<':
    case '+':
    case '-':
    case '.':
    case ',':
    case '[':
      printf("error: stack underflow\n");
      exit(1);
    }
  }
}

使い方はこんな感じです。

• プログラムはコンパイラのオプションの PROG で指定する
• 入力は標準入力から受け取る
• 出力は標準出力へ出す

実行例です。

$ gcc pda.c '-DPROG=">,+."' && echo 10 | ./a.out
11
$ gcc pda.c '-DPROG=">+++++[-.]"' | ./a.out
4
3
2
1
0
$ gcc pda.c '-DPROG=">+++[>+++[-.]<-]"' | ./a.out
2
1
0
2
1
0
2
1
0

はい、定数個の object だけを使って brainfuck っぽい感じで動いてますね。ただ、 < と > が stack の push と pop ですので、無限のメモリにランダムアクセスできません。したがって、これはチューリングマシンではなく、それより弱いプッシュダウンオートマトンです(本来なら、これが本当にプッシュダウンオートマトンであるか証明しなければいけないのですが、時間と脳みそが必要そうなのでやっていません)。

線形拘束オートマトンはよくわからなかった

線形拘束オートマトンですが、雑に言うと「入力の定数倍の有限のメモリとCPUからなる機械」です。

メモリは有限なので普通に object を用意すれば良いような気がするのですが、「入力は有限だがその長さによって CHAR_BITS の値と SIZE_MAX の値を決めてよいのか？」という疑問があります。

これは設問次第なのですが、入力の長さを知った後に CHAR_BITS の値と SIZE_MAX の値を変えられないとすると、私には線形拘束オートマトンを構成する方法を思いつきませんでした。

チューリングマシンを構築できなかった

私には無理でした。どなたかチャレンジしてください。

抜け穴

抜け穴1

fseek() に SEEK_CUR だけを指定できる無限の多きさを持つファイルを外付けできればチューリングマシンにできるのでは？ということに書いている途中に気が付きました。ただ、「外部に無限のメモリがあれば実現できます」的な話は「チューリング完全な組込関数があればチューリング完全です」みたいな話になってあんまり面白くないなぁ、とか思いました。

抜け穴2

(5/23 7:30頃追記)

twitter で @miura1729 さんからツッコミが入りました。

Cはチューリング完全か？ https://t.co/XEpoCPRQSy　ローカル変数はレジスタに格納しても合法なのだから&演算子でアドレスを取らなければ(これは静的に分かる)、アドレスを持つ必要は仕様上ないのではないだろうか？

— Miura Hideki (@miura1729) May 22, 2018

確かに&演算子さえ使わなければその object へのポインタが存在する必要はなく、従ってsizeof(void *)の制限も無関係になります。再帰を併用すれば objectを無限に作成すること自体は可能ということになります。

引数/返却値を使うことでλ計算に落とし込むこともできるのではないか、というような話もしました。

私には実際にλ計算を構成する方法を思いつかなかったので、どなたかチャレンジしてみてください。

(5/23 19:00追記)
その後 @miura1729 さんとの話の中で「スタック2本+有限オートマトン」でチューリングマシンが構成できてしまいそうなことに気が付きました。これから実験します。

まとめ

というわけで今のところの結論は「Cはプッシュダウンオートマトンと同等以上の強さをもちそう」です。

以上、ポエムでした。