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