チューリングマシン

チューリングマシン(Turing Machine)

計算モデル

チューリングマシン

関連

参考

チューリングマシン　概要説明

https://youtu.be/K5WnmOvXAMI?si=FsS8FaqFHLUgWNMz

【2022/05/11】チューリングマシンを学ぼう ～コンピュータサイエンス入門～【アーカイブ】

https://www.youtube.com/watch?v=edRU9O-VAxs

計算: ある規則に基づいて機械的に実行される手続き

計算を行うのに必要なもの

計算の経過の取りうる状態

記号

計算規則

計算の初期状態(開始状態)

計算の終了状態(受理状態)

アルファベット: 有限の記号の集合

例: { 0, 1 }、{ a, b,..., z }、{ !, ?, # }

系列: いくつかのアルファベットの要素の連ねた記号列

例: 001, 010、0111など

言語: 一定の規則(文法)によって生成される系列の集合