Turing Machine

It is a thinking calculating machine conceived by the British mathematician Turing. It can be said to be the theoretical prototype of modern computers. Because it is a thinking machine for developing the theory of calculation, it does not have mechanisms for shortening calculation time like real computers, or printers to make the results easier to view. It only has the minimum parts necessary to develop the theory.

A Turing machine consists of only three parts: (1) an infinitely long tape, (2) a head, and (3) a control unit. The tape has sections where information can be stored, and one symbol can be written in each section. The tape extends infinitely in both the left and right directions. The head reads and rewrites the symbols written in one section of the tape. The control unit exchanges information with the head and moves the position of the head. The control unit can have a finite number of states. The next action the machine should take is determined by the symbol read by the head and the state of the control unit. The specifications for the machine's operation are expressed by listing several rules such as the following: "When the head is in state q, if it reads symbol a from the tape, perform operation z and move to state r." Here, there are three types of z: (1) Write symbol b in the section of the tape where the head is currently located (the read symbol a is lost). (2) Move the current head position one section to the right. (3) Move the current head position one division to the left.

Assume that there are only a finite number of types of symbols that can be written to and read from tape. Also, there are only a finite number of possible states and rules for the specification of the machine's behavior. The behavior of such a machine is determined by specifying the following four things: (1) all symbols to be used, (2) possible states, (3) the state the machine starts in, and (4) the specification of the machine's behavior (a set of rules).

Although Turing machines are very simple compared to real computers, Turing defined it as "the existence of an algorithm to solve a problem means that the problem can be solved by this machine." The concept of the existence of an algorithm was thought up separately by Turing, Stephen Cole Kleene (1909-1994), Gödel, Alonzo Church (1903-1995), and Emil Leon Post (1897-1954), but it was later shown that all of these definitions were equivalent. The idea of ​​Turing machines has brought about important results for modern computer science. In particular, it was proven that "there are problems that cannot be solved by Turing machines," and it became clear that "there are problems for which algorithms do not exist." In other words, this shows that there are problems that cannot be solved by computers.

A Turing machine that will behave in the same way as a machine with the specifications of a Turing machine written on a tape is called a Universal Turing Machine. This is essentially the same as today's stored-program computers. Universal Turing Machines with simple specifications have been created by many people, including Turing, Takahashi Hidetoshi (1915-1985), Ikeno Shinichi (1924-1988), and Minsky (1927-2016).

[Masakazu Nakanishi]

"Mathematical Theory of the Computer" by M. Minsky, translated by Yu Kanayama (1970, Kindaikagakusha) " "Foundations of the Theory of Computation" by Teruaki Aizawa (1970, Bunichi Sogo Shuppan) " "Introduction to Computability" by Kojiro Kobayashi (1980, Kindaikagakusha)"

Source: Shogakukan Encyclopedia Nipponica About Encyclopedia Nipponica Information | Legend

イギリスの数学者チューリングが考えた、思考のうえでの計算機械である。これは、現在のコンピュータの理論的な原型であるともいえる。計算の理論を展開するための思考上の機械であるから、現実のコンピュータのように計算時間を短縮するための機構や結果を見やすくするためのプリンターなどはついていない。理論を展開するのに必要な最小限の部品しかついていない。

　チューリング機械は、(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・近代科学社）』

出典　小学館　日本大百科全書(ニッポニカ)日本大百科全書(ニッポニカ)について　情報 | 凡例