チューリングマシン単語

20件

チューリングマシン

1.1千文字の記事

掲示板へ

記事編集

チューリングマシンとは、アラン・チューリングによって考え出された仮想上の機械である。仮想上とは言え、現在開発されているコンピュータは全てこのチューリングマシンの考えに則っていると言われる。

概要

基本的に、ある1つの問題を解くものである。入力に対してYesかNoかを返す。例えば、「入力された数は素数か?」「入力された目的地には1日で行けるか?」等。同じ問題でも解く手順は1つとは限らないので、チューリングマシンも手順の数だけ存在する。

チューリングマシンはテープとヘッドによって構成される。テープには予め入力情報が格納されており、ヘッドが順次読み取ることにより実行される。ただ順に読み取るだけでなく、書き込んだり逆方向に進むことも可能。テープは無限の長さを持っている。言うなれば、予定が書かれた手帳を順に読んで実行するようなものである。

定義

チューリングマシンは次のように定義される。

M = (Q,Γ,b,Σ,δ,q_init,q_acc)

記号だけ書かれても訳わからんという方が多いと思うので、テープを手帳、ヘッドを持ち主になぞらえて解説する。

状態

持ち主の状態。厳密にはヘッドの状態ではないが、チューリングマシンはこの「状態」を変化させながら実行される。Qは状態からなる有限集合である。

記号

手帳に読み書きする内容のこと。手帳1ページにつき1つ書かれている。それ自体に具体的な意味があるわけではないが、次の状態を決定する要因である。Γは記号からなる有限集合である。

空白記号

手帳で言えば、何も書かれてないページ。入力はテープの先頭から有限の長さで書かれるが、その終端より後に格納されている。bは空白記号である。

入力記号

予め手帳に書いてある記号。空白記号はこれに属さない。Σは入力記号からなる集合である。

状態遷移関数

現在の状態と読み取った記号から、次の状態を決める関数。何を書き込んで前後どちらに進むかについても決定される。δは状態遷移関数である。

初期状態

持ち主の最初の状態。q_initは初期状態である。

受理状態

問題が解け、Yesに至った状態。いわばグッドエンディング。q_accは受理状態である。ちなみにNoに至った状態を拒否状態という。こちらがバッドエンディングである。

ニコニ広告で宣伝された記事

ニコニコ動画 (単) 記事と一緒に動画もおすすめ！

提供：ゲスト

40323800pt

この記事の掲示板に最近描かれたお絵カキコ

お絵カキコがありません

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません