エクセルチューリングマシン

この記事では、チューリングマシンとExelでの実装について簡単に説明します。 役立つ記事は、チューリングマシンに精通したい人、およびExcel機能の視野を広げたい人向けです。

チューリングマシンとは

チューリングマシンは、セルを備えた無限のリボンです。 各セルには1文字が含まれます。 特に、空のセルは、空のセルのシンボルが記録されているセルです。 セル内のシンボルは、このマシンのアルファベットに属します。

ヘッドはテープに沿って移動しますが、テープはいくつかの状態にあり、状態の1つはマシンの終わりです。 ヘッドは現在のセルを読み取り、このセルの値とその現在の状態に応じて、現在のセルの値を変更してから、右に移動するか、左に移動するか、所定の位置に留まります。

マシンを起動するには、テープの初期状態、ヘッドの状態、およびヘッドの位置を指定する必要があります。 そして、もちろん、マシンのアルファベット、ヘッドの状態、ルールを定義する必要があります。

頭のルール全体を決定する必要がありますN =（アルファベットの文字数）*（状態の数-1）。 最終状態にはルールがないため、状態の数は1です。マシンは停止します。

簡単な例：2進数に1を追加する

このようなマシンの場合、3文字のアルファベット（0、1、x）が必要です-0と1は数字を表し、xは空のセルを表します。 つまり、空のテープはすべて文字「x」で満たされています。

ヘッドには4つの状態があります：q1、q2、q3、q4-マシンを停止します。

マシンのルールをマトリックスの形式で書きます。





このようなマシンが、初期状態がq1の2進数の最上位の桁にヘッドを置くと、この数が1増えることを確認するのは簡単です。

Excelの実装

上記の例のように、ルールテーブルを作成します。 このテーブル全体を選択し、「ルール」と呼びます。 Enterキーを押します。







テーブルの構造は上記の例と同じですが、少し変更されています。

•マシンの状態は単に番号と呼ばれます（qなし）

•空のセルは、記号「2」を意味します

•頭の動きは1-右に、-1-左に、0-所定の位置に設定されます



テープの初期状態を設定します。





これは、番号10111がテープに書き込まれ、ヘッドが状態1にあり、最上位に対応するセルにあることを意味します。 Excelは、より明確にするために使用される条件付き書式をサポートしています。

マシンの新しいステップは新しいExcel行でモデル化され、式はルールに従ってマシンの状態を模倣します。



相対式-つまり、それらを新しいセルにコピーすると、Excelはマシンの以前の状態に対応するセルからデータを取得します。

その結果、すべてのステップが完了し、マシンは「停止」します。状態「4」に到達すると、番号に1が追加されます。







ここにExcelファイルへのリンクがあります

おわりに

Excelが任意の数の行と列をサポートしている場合、Excelはチューリング完全であるため、Excelの数式を使用して計算可能な関数を実装できることを自動的に意味します



PSトリッキーなタスク：記事で説明されているチューリングマシンのルールを変更して、2進数を1減らすようにします。