コトバンクはYahoo!辞書と技術提携しています。

チューリング機械 チューリングキカイ

4件 の用語解説(チューリング機械の意味・用語解説を検索)

デジタル大辞泉の解説

チューリング‐きかい【チューリング機械】

チューリングマシン

出典|小学館
デジタル大辞泉について | 情報 凡例

百科事典マイペディアの解説

チューリング機械【チューリングきかい】

英国の数学者A.M.チューリングデジタル計算機モデルとして1936年に提唱した仮想的な機械。このモデルによれば,デジタル計算機で処理可能なことはチューリング機械の動作として記述可能であり,逆にチューリング機械で原理的に計算不可能な問題はデジタル計算機では処理できない。

出典|株式会社日立ソリューションズ・クリエイト
百科事典マイペディアについて | 情報

世界大百科事典 第2版の解説

チューリングきかい【チューリング機械 Turing machine】

イギリスの数学者A.M.チューリングは1936年に発表した論文で,数学基礎論で当時懸案となっていた〈計算可能とはどういうことか〉という問題に対する一つの解答として,ある仮想的な機械を提案した。これが今日チューリング機械と呼ばれているものである。 チューリング機械は,図に示すように機械Mと両方向に無限にのびるテープTからなる一個の自動機械(オートマトン)である。テープは桝目に区切られており,そこには記号が1個書かれているか,何も書かれていない。

出典|株式会社日立ソリューションズ・クリエイト
世界大百科事典 第2版について | 情報

日本大百科全書(ニッポニカ)の解説

チューリング機械
ちゅーりんぐきかい

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

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

世界大百科事典内のチューリング機械の言及

【オートマトン】より

…たとえば,神経細胞網モデル,セルオートマトン,自己増殖オートマトン,などであり,その一部は今でも研究されている。計算機モデルとしては,これらよりも前に,チューリング機械があり,アルゴリズムや計算に関する研究がなされていた。 初期のころは,オートマトンさえ研究すればすべて解決するといったような楽観論が支配していたように思われる。…

【計算モデル】より

…コンピューターが行う計算を数学的に表したモデルのこと。計算モデルとしては複数の種類が提唱されているが,もっとも有名なのはA.M.チューリング が考案したチューリング機械である。チューリング機械は,有限状態の制御部と,左右無限に伸びたテープと,そのテープ上の記号を読み取るためのヘッドからなる(図)。…

【計算量】より

…そこで,アルゴリズム自体の効率を議論するために,ある程度抽象化された計算モデルを用い,そのうえでの計算時間を測る。 厳密な議論では,チューリング機械などの原始的な抽象機械を計算モデルとし,機械の計算ステップ数を計算時間とみなすのが一般的である。そこまで抽象化しなくてもよい場合には,プログラムの各単位実行文を1ステップとみなし,プログラムの実行に要したステップ数を計算時間としてもよい。…

【形式言語】より


[無制限文法]
 書き換え規則に対してどんな制約もおかない文法を無制限文法unrestricted grammar,あるいは0型文法という。この文法で生成される言語は無制限言語,あるいは0型言語といわれ,チューリング機械によって識別される。この言語の族は,前述の全ての言語の族を含む。…

※「チューリング機械」について言及している用語解説の一部を掲載しています。

出典|株式会社日立ソリューションズ・クリエイト
世界大百科事典 第2版について | 情報

今日のキーワード

百条委員会

地方自治体が議決により設置する特別委員会の一つ。名称は「地方自治法第100条」に基づく。百条委員会は、地方公共団体の事務に関する調査を行い、関係者への聞き取りや記録の提出を請求、拒否した者には罰則が科...

続きを読む

コトバンク for iPhone