オートマトンとチューリングマシン
ここら辺からプログラミング的な内容に向かって突っ込むのですが、原始的過ぎてもはやコンピュータじゃねーだろ、という領域から掘り下げていきます。
オートマトン
オートマトンは一定の規則に従って複数の内部状態の間を遷移する仮想的な機械で、現在の状態と入力の組み合わせを規則の中から探し出し、指定された次の状態へ遷移する。規則に該当する組み合わせがなければ同じ状態を維持する。規則は状態遷移表や状態遷移図として書き表すことができる。
https://e-words.jp/w/%E3%82%AA%E3%83%BC%E3%83%88%E3%83%9E%E3%83%88%E3%83%B3.html
チューリングマシンとの境界としては、チューリングマシンはオートマトンの条件付きな一種である。
その条件とは「無限のテープ(ノイマン型コンピュータでいう主記憶装置：メモリ)をもつ。ちなみにランダムアクセス可能(番号を飛ばして先に行ったり戻ってきたりが可能)」「状態を制御するヘッドがある(ノイマン型コンピュータでいう制御装置がある)」「ヘッドによる読み書きとシークするテープを持つ」である。
このチューリングマシンについての詳細はあとの話題として取っておくこととして、今回は汎用的なオートマトンについて話を進める。
和訳するとき電気羊とか書かれることがあるオートマトンだが、そのほとんどは「有限個の状態」を入力によって「状態1⇒状態2」のように変化させるもので、かつ「スタートとゴールがある」ものである。この「有限個の状態」で「スタートとゴールを持つ」ものを有限オートマトンという。
次に示す有限オートマトンが受理する入力例はどれか。ここで，S1は初期状態を，S3は受理状態を表している。
ア：1011 イ：1100 ウ：1101 エ：1110
応用情報処理技術者試験 H21春季午前問題3より引用
この問題の解説を例にすると、最初はS1にいます。で、暗黙の了解として左のビットから1bitずつ一が変化します。この場合、4つの選択肢の最左bitはすべて1なので、S1->S2になります。
2bit目はS2から始まりますが、実はS2->S3という矢印はありません。アの場合はS2->S2というループをしています。イウエはS2->S1でS1に帰ってきます。
3bit目はア：S1->S2->S2->S1と帰ってきました。 イ,ウ：S1->S2->S1->S3と移動します。 エ：S1->S2->S1->S2と行ったり来たりします。
4bit目はア：S1->S2->S2->S1->S2でゴールにたどり着けなかったので不正解。 イ：S1->S2->S1->S3->S2でゴールから出てしまったので不正解。
ウ：S1->S2->S1->S3->S3でゴールでループして終わったのでこれが正解。 エ：S1->S2->S1->S2->S2でループして不正解。
という感じで追いかけるといいよ。今回はbit数でみて全選択肢並行で見たけど、選択肢ごとにみてS3で終わるか確認するほうが楽。
個人的にオートマトンの勉強をするなら「白と黒のとびら」をオススメ。
https://bookmeter.com/books/6519548
ファンタジー小説風にオートマトンの説明をしている(この世界の魔法はオートマトンによる状態遷移を定義・実施することなので弟子入りしたばっかの魔術師見習いの主人公の成長物語的にどんどん高度なオートマトンになっていく。) 2作目「精霊の箱」でチューリングマシンに入り、万能チューリングマシンで終わるので数学ガール的な読み物として面白い。ちなみにパッと見た限り数学ガールシリーズでオートマトンの回はなかったが。
チューリングマシン
状態及び入力による遷移ができるものがオートマトンでした。
で、オートマトンのうちオートマトンの項目で述べた特徴があるものを「チューリングマシン」と言います。
https://e-words.jp/w/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%9E%E3%82%B7%E3%83%B3.html
んで、実装実例の一つとしてこんな動画がありますねぇ...。
https://wired.jp/2012/06/22/lego-turing-machine/
で、「テープの後ろのほうにある内容をコピーしてきて動作できる」チューリングマシンを「万能チューリングマシン」と言います。後ろのほうにどんな内容でも書いておけば動くということで、プログラムの実装に該当するわけです。ゆえに万能。
で、特定の条件下で万能チューリングマシンとして動作できることが保証されるとそれをチューリング完全と言います。
https://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E5%AE%8C%E5%85%A8
裏返すとチューリング完全ならばコンピュータとして動作することが保証されるので、変なものを計算機として扱ってみるという試みが情報数学者の遊びとしてあります。
スーパーマリオ計算機
https://nlab.itmedia.co.jp/nl/articles/1907/04/news068.htmlとマリオメーカー学会https://dic.nicovideo.jp/a/%E3%83%9E%E3%83%AA%E3%82%AA%E3%83%A1%E3%83%BC%E3%82%AB%E3%83%BC%E5%AD%A6%E4%BC%9A
マリメ1のころの話だけど、マリメ2でもできる。
情報処理技術者試験だとチューリングマシンレベルの問題はあんまりでないですね。
次の話題は論理演算だけど、長ーくなるし重要な話なので次回ですねー。