2017チューリングマシンについての個人的なまとめです。TM)チューリングマシンは計算論において最も重要な計算モデルの一つである。この仮想的な機械は無限長のマス目を持つテープとその上を動くテープヘッド、現在の状態から構成される。遷移規則をもとに与えられた入力が受理可能かを判断するという点では有限状態機械と同様だが、それが計算可能とする問題の範囲は広い。チューリングマシンの遷移規則は以下の要素から成る。左)チャーチ・チューリングのテーゼでは、計算可能な関数をチューリングマシンで計算可能とする関数のクラスと同一視しており、チューリングマシン以上の能力を持つ計算モデルは存在しないと推測している。するチューリングマシンは以下のように表現される。いう表記になっている。上記チューリングマシンの動作をプログラムで実装すると以下のようになる。UTM)「遷移規則と処理対象の文字列を一つの入力として受け取り、規則で記述された計算を実行する」ことができるチューリングマシンを考える。この機械は入力の規則を変えるだけであらゆるチューリングマシンで行える計算が実行可能であり、いわばチューリングマシンのインタプリタのような機能を持つ。このような機械は実際に作成可能であり、万能チューリングマシンと呼ばれる。計算可能なこと上述のように一般的に計算可能とする関数とチューリングマシンで計算可能な関数のクラスは一致する。そのため有限状態機械やプッシュダウンオートマトンで計算可能な関数は全てチューリングマシンでも計算可能である。計算可能な関数が持つ性質については計算可能関数についてにまとめている。他に計算可能な関数の具体例としては原始再帰関数が挙げられる。簡単な原始再帰関数としては以下のようなものがある。計算不可能なこと代表的なものとして停止性問題が挙げられる。