「チューリングマシン」の版間の差分
削除された内容 追加された内容
6行目:
== 概要 ==
ここでは非形式的（直感的）に述べる。理論的には形式的に述べる必要がある。
チューリングマシンには、いわゆるハードウェアに相当するものとして、
#その中に格納された情報を読み書きするヘッド▼
#その表面に記号を読み書きできるテープ。長さは無制限（必要になれば順番にいくらでも先にシークできる<ref>一般的には両方向にいくらでもシークできるものとするが、理論的には片方には端があっても良いのでそのように制限することもある。</ref>）とする
#ヘッドによる読み書きと、テープの左右へのシークを制御する機能を持つ、[[有限オートマトン]]
がある。
*ヘッドを右か左に一つ移動する▼
また、ソフトウェアに相当するものとして、以下がある。
#テープに読み書きされる有限個の種類の記号
#最初から（初期状態において）テープにあらかじめ書かれている記号列
#有限オートマトンの状態遷移規則群。詳細は次で述べる
この有限オートマトンの状態遷移規則は、その有限オートマトンの「現在の状態」（内部状態）と、ヘッドがテープの「現在の場所」から読み出した記号の組み合わせに応じて、次のような動作を実行する。
*テープの「現在の場所」に新しい記号を書き込む（あるいは、現在の記号をそのままにしてもよい）
▲*ヘッドを右か左に一つ移動する（あるいは、移動しなくてもよい）
*有限オートマトンを次の状態に状態遷移させる（同じ状態に遷移してもよい）
さらに、この有限オートマトンには（一般的な有限オートマトンの「受理状態」と同様な）「受理状態」がある。[[計算可能性理論]]的には、[[決定問題]]の2種類の答えに対応する、2種類の受理状態が必要である。
== 現実の計算との関係 ==
| |||