日本大百科全書(ニッポニカ) 「チューリング機械」の意味・わかりやすい解説
チューリング機械
ちゅーりんぐきかい
イギリスの数学者チューリングが考えた、思考のうえでの計算機械である。これは、現在のコンピュータの理論的な原型であるともいえる。計算の理論を展開するための思考上の機械であるから、現実のコンピュータのように計算時間を短縮するための機構や結果を見やすくするためのプリンターなどはついていない。理論を展開するのに必要な最小限の部品しかついていない。
チューリング機械は、(1)無限に長いテープ、(2)ヘッド、(3)制御部、の三つの部分だけから成り立っている。テープには、情報を格納することのできる区分があり、一つの区分の中に一つの記号を書き込むことができる。そしてこのテープは、左右の方向に無限に延びている。ヘッドは、テープの一つの区分に書かれている記号を読み取ったり、書き換えたりする。制御部は、ヘッドとの情報のやり取りをしたり、ヘッドの位置を動かしたりする部分である。制御部は、有限個の状態をもちうる。ヘッドで読み取った記号と、制御部の状態により、次に機械がなすべき動作が決まる。機械の動作の仕様は、次のような規則をいくつか書き並べて表すことにしている。「状態qのとき、ヘッドがテープから記号aを読み取ったら、zという作業をして、状態rへ移る」。ここでzには、次の3種類がある。(1)現在ヘッドがあるところのテープの区分の中にbという記号を書く（読み取った記号aは失われる）。(2)現在のヘッドの位置を右へ1区分だけ動かす。(3)現在のヘッドの位置を左へ1区分だけ動かす。
テープに書き込んだり読み取ったりすることのできる記号は、有限個の種類しかないものとする。また、とりうる状態も、動作の仕様の規則も有限個に限る。このような機械に対して、次の四つを指定すると、この機械の動作が決まる。(1)利用するすべての記号、(2)とりうる状態、(3)この機械が始めにとる状態、(4)動作の仕様（規則の集まり）。
チューリング機械は現実のコンピュータに比べると非常に簡単なものであるが、チューリングは、「ある問題を解くアルゴリズムが存在するということは、その問題がこの機械で解けることである」と定義した。アルゴリズムの存在の概念は、チューリングのほかに、クリーニStephen Cole Kleene（1909―1994）、ゲーデルや、チャーチAlonzo Church（1903―1995）、ポストEmil Leon Post（1897―1954）などが別々に考えていたが、のちになって、どれも同値の定義であったことが示された。チューリング機械の考え方は、現在のコンピュータ科学にとって重要な成果をもたらした。とくに、「チューリング機械で解けない問題が存在する」ことが証明されて、「アルゴリズムが存在しない問題がある」ことが明らかになった。つまり、このことはコンピュータに解けない問題があることを示している。
あるチューリング機械の仕様をテープに書いておけば、その仕様の機械と同じ動きをするチューリング機械を万能チューリング機械という。これは、現在のプログラム内蔵方式のコンピュータと本質的に同じものである。万能チューリング機械は、チューリングのほか、高橋秀俊（1915―1985）、池野信一（1924―1988）、M・ミンスキー（1927―2016）など多くの人たちによって、簡素な仕様のものがつくられている。
［中西正和］
『M・ミンスキー著、金山裕訳『計算機の数学的理論』（1970・近代科学社）』▽『相沢輝昭著『計算理論の基礎』（1970・文一総合出版）』▽『小林孝次郎著『計算可能性入門』（1980・近代科学社）』
