チューリング計算可能関数とは？：加算関数を例にシミュレーターで追う
計算機科学において、「計算可能である」とはどういうことかという問いは、チューリングマシンが登場するまで厳密に定義されていませんでした。アラン・チューリングは、この「計算可能」という概念を、自身の考案した抽象的な機械、チューリングマシンによって形式化しました。本記事では、チューリングマシンによって「計算可能」とされる関数、すなわちチューリング計算可能関数について解説し、簡単な例として単項表現における加算関数がどのようにチューリングマシンで計算されるかをシミュレーターの動作と対応させながら掘り下げていきます。
チューリング計算可能関数とは
チューリングマシンは、その定義からわかるように、特定の入力テープに対して一連の操作を行い、最終的に停止するか、あるいは停止しないかのいずれかの振る舞いをします。この機械の動作を、関数計算の観点から捉え直すことができます。
ある関数 $f(x_1, x_2, \ldots, x_n)$ がチューリング計算可能であるとは、以下のような性質を持つチューリングマシンが存在することを指します。
- 入力の形式: 関数の入力 $x_1, x_2, \ldots, x_n$ は、チューリングマシンのテープ上に特定の形式でエンコード（符号化）されて初期状態として与えられます。例えば、自然数の入力は単項表現（1を並べたもの）や二進数表現などでエンコードされることが一般的です。複数の入力がある場合は、区切り文字などを用いてテープ上に配置されます。
- 計算の実行: チューリングマシンは定義された遷移規則に従って動作します。ヘッドを移動させ、テープ上の記号を読み書きしながら状態を遷移させていきます。
- 出力の形式: もし関数 $f$ が入力に対して定義されている（つまり、計算結果が存在する）ならば、チューリングマシンは有限時間で停止し、その停止状態において、テープ上の特定の位置（通常は初期位置）に計算結果 $f(x_1, x_2, \ldots, x_n)$ が特定の形式でエンコードされて残されています。
- 未定義の場合: もし関数 $f$ が入力に対して定義されていない場合（例：ゼロ除算、負の数の平方根など）、チューリングマシンは停止しないか、あるいは関数が未定義であることを示す特別な状態や記号で停止します（ただし、標準的な定義では停止しないことと等価とみなされることが多いです）。
簡単に言えば、関数 $f$ がチューリング計算可能であるとは、「その関数を計算するアルゴリズムが、チューリングマシンで実現可能である」ということと同義です。計算機科学の分野では、直感的に「計算可能」と考えられるほとんどの関数は、チューリング計算可能であることが知られています。これはチャーチ＝チューリングの提唱（Thesis）と呼ばれ、数学的な証明が可能な定理ではありませんが、広く受け入れられている原理です。
例：単項表現による加算関数 $f(m, n) = m + n$
$m$ と $n$ を自然数とします。関数 $f(m, n) = m + n$ は、明らかに計算可能な関数です。この関数がチューリング計算可能であることを、単項表現を用いたチューリングマシンで示してみましょう。
単項表現では、自然数 $k$ は $k$ 個の '1' を並べた文字列として表されます。例えば、3は '111'、0は空文字列（あるいは特別な記号）で表されます。
入力として $m$ と $n$ を与える場合、テープ上には単項表現された $m$ と $n$ を、例えば '+' という記号で区切って配置することにします。初期状態のテープは「...(空白) 11...1 (m個) + 11...1 (n個) (空白)...」のようになります。ヘッドは通常、最初の '1' の位置に置かれます。
この加算を行うチューリングマシンの基本的なアルゴリズムは以下のようになります。
- $m$ を表す最初の '1' の並びの最後を見つける。
- 区切り記号 '+' を '1' に置き換える。
- これでテープ上には $m$ 個の '1' と $n$ 個の '1' が '+' で区切られていた状態から、合計 $m+n$ 個の '1' が並んだ状態となる。
- 最初の $m$ の並びの先頭に戻る（これは単項表現の数値の開始位置を示すため）。
- 停止する。
このアルゴリズムを実現するチューリングマシンの状態遷移を考えてみましょう。
- 状態 q0 (初期状態): テープの先頭（最初の '1'）から開始します。右へ移動しながら最初の '1' の並び（m）を走査します。'1' を読み取ったら '1' のまま右へ移動します。
- 状態 q1: q0で '+' を読み取った状態です。これはmの並びの終わりを示します。'+' を '1' に書き換えます。これでテープ上には $m$ 個の '1' と $n$ 個の '1' が連続して並びました。ヘッドは '+' だった場所（現在の '1'）にあります。この後、計算結果（$m+n$個の '1' の並び）の先頭に戻る必要があります。左へ移動を開始します。
- 状態 q2: q1から左へ移動中に '1' を読み取った状態です。先頭に戻るため、'1' はそのままにして左へ移動を続けます。
- 状態 q3 (停止状態): q2から空白（テープの左端を示す記号と見なす）を読み取った状態です。これは $m+n$ 個の '1' の並びの左端、すなわち計算結果の先頭に到達したことを示します。計算が完了したので停止します。
より正確な状態遷移表（例）を記述します。ここでは、テープ記号として '{' （左端を示す）、'1'、'+'、' '（空白）を使用します。
| 現在の状態 | 読み込んだ記号 | 書き込む記号 | ヘッドの移動 | 次の状態 | | :--------- | :------------- | :----------- | :----------- | :------- | | q0 | { | { | R | q0 | (左端をスキップ) | q0 | 1 | 1 | R | q0 | (mの並びを右へ走査) | q0 | + | 1 | L | q1 | (区切りを1に変換し左へ移動) | q1 | 1 | 1 | L | q1 | (1をスキップし左へ移動) | q1 | { | { | R | q_halt | (左端到達、停止)
※この遷移表は非常に単純化された例です。例えば、入力が $0+n$ や $m+0$ の場合、あるいは $0+0$ の場合などを考慮すると、もう少し複雑な遷移が必要になります。しかし、基本的な加算（$m, n > 0$）であれば、上記のロジックで計算が可能です。より完全な実装では、初期状態で左端 '{' をスキップする処理、空白を読み込んだ場合の処理、入力形式の検証なども考慮する必要があります。
シミュレーターでの動作追跡
上記の遷移表に基づいて、シミュレーターで $2+3$ の計算を追跡してみましょう。
入力テープ: {11+111 } (ここで { は左端、 は空白、ヘッドは最初の '1' に位置)
- 初期状態: q0, ヘッドは最初の '1'
テープ:
{ **1** 1 + 1 1 1 } - q0, '1' 読み取り: '1' を書き込み（変化なし）、ヘッドを右へ移動。状態は q0 のまま。
テープ:
{ 1 **1** + 1 1 1 } - q0, '1' 読み取り: 同上。
テープ:
{ 1 1 **+** 1 1 1 } - q0, '+' 読み取り: '+' を '1' に書き込み、ヘッドを左へ移動。状態は q1 へ遷移。
テープ:
{ 1 **1** 1 1 1 }(ヘッドは元の2番目の '1' の位置) - q1, '1' 読み取り: '1' を書き込み（変化なし）、ヘッドを左へ移動。状態は q1 のまま。
テープ:
{ **1** 1 1 1 1 } - q1, '1' 読み取り: 同上。
テープ:
{ **{** 1 1 1 1 1 } - q1, '{' 読み取り: '{' を書き込み（変化なし）、ヘッドを右へ移動。状態は q_halt へ遷移。
テープ:
{ **1** 1 1 1 1 } - 停止状態 q_halt: マシンは停止します。テープ上には '{11111 }' となっており、左端の '{' を除けば '1' が5つ並んでいます。これは単項表現で 5 を示しており、$2 + 3 = 5$ という計算結果が得られました。
シミュレーター上では、現在の状態、テープの内容、ヘッドの位置、読み取った記号、書き込む記号、ヘッドの移動方向、そして次の状態がステップごとに表示されます。この表示を追うことで、上記の理論的な状態遷移が具体的にどのように実行されているかを視覚的に理解することができます。特に、状態が変化するタイミングや、ヘッドの移動が計算のどの部分に対応しているのかを確認することが重要です。
まとめ
本記事では、チューリング計算可能関数という概念について、それがチューリングマシンによる計算可能性の形式化であることを解説しました。そして、具体的な例として単項表現による加算関数を取り上げ、そのチューリングマシンによる実装の基本的な考え方と、シミュレーター上での動作追跡例を示しました。
チューリングマシンをシミュレーターで動かしてみることは、抽象的な「アルゴリズム」や「計算可能」といった概念が、テープ、ヘッド、状態、遷移規則といった具体的な要素の単純な相互作用から生まれることを体感するための非常に有効な手段です。今回扱った加算だけでなく、他の様々な関数や問題をチューリングマシンで表現することを試み、シミュレーターでその動作を確認することで、計算の限界や可能性についての理解を一層深めることができるでしょう。ぜひ、当サイトのシミュレーターを活用して、理論と実践を結びつける学習を進めてみてください。