「チューリングマシン」の版間の差分

タグ: モバイルアプリ編集
数学の[[形式体系]]はすべてこの仮想機械の動作に還元できるといわれている。この機械で決定できない命題も存在する。例えば与えられたチューリング機械が停止するかどうかをチューリング機械で決定することはできない([[停止性問題]])。これは[[ゲーデルの不完全性定理]]の別の表現の形とみなすことができる。
 
== 厳密形式的な定義 ==
<!--「形式的」というのはこの分野の専門用語であり、少なくともこの節において専門用語的に正確でない「厳密」という表現を使うのは間違い-->この節では、チューリング機械を形式的(formal)に記述する。
チューリング機械とは次の<math>7</math>つ組<math>M = \langle Q, \mathit\Gamma, b, \mathit\Sigma, \delta, q _{\mathrm{init}}, q _{\mathrm{acc}} \rangle</math>である。
 
あるチューリング機械は次の<math>7</math>つ組<math>M = \langle Q, \mathit\Gamma, b, \mathit\Sigma, \delta, q _{\mathrm{init}}, q _{\mathrm{acc}} \rangle</math>で定義される。
* Q は[[有限集合]]であり、その元を'''状態'''という。
* ''Γ'' は ''Q'' に交わらない有限集合であり、'''[[アルファベット (計算機科学)|字母]]'''とよばれる。その元を'''記号'''という。