教育用のチューリングマシン「Stem」を開発しました。これはチューリングマシンの基本概念を理解するためのシンプルなエミュレータです。特に、計算理論やチューリングマシンに興味がある方には必見のツールです。
Stemとは？
Stemは、「Stem: Turing Educational Machine」の略で、再帰的頭字語になっています。このエミュレータは、チューリングマシンの動作をシンプルに再現することで、教育的な価値を提供します。具体的には、以下のような特徴を持っています：
- CLI: コマンドラインで実行できるので出力をファイルにも書き込める
- JSON: 分かりやすいデータ構造JSONでチューリングマシンを定義できる
仕様
- tape: シンボルとして UTF-8 文字を含める
- start_state: 実行開始時の初期状態
- transitions: 遷移のルールを定義する
遷移ルールの形式
分割された "_" アンダースコアを記述します。
左は状態を指定し、右は読み取られるシンボルを指定します
実例: ビット反転
ここでは、ビット反転を行う簡単なチューリングマシンの例を示します。
{
"tape": "11010010",
"start_state": "q0",
"transitions": {
"q0_0": { "write": "1", "direction": "Right", "next_state": "q0" },
"q0_1": { "write": "0", "direction": "Right", "next_state": "q0" }
}
}
実行トレース
この設定を使ってチューリングマシンを実行すると以下のようになります：
Stem: Turing Educational Machine
-----------------------------------
Current State: q0, Read: 1
[1] 1 0 1 0 0 1 0
Write: 0, Move: Right, Next State: q0
0[1] 0 1 0 0 1 0
Current State: q0, Read: 1
0[1] 0 1 0 0 1 0
Write: 0, Move: Right, Next State: q0
0 0[0] 1 0 0 1 0
Current State: q0, Read: 0
0 0[0] 1 0 0 1 0
Write: 1, Move: Right, Next State: q0
0 0 1[1] 0 0 1 0
Current State: q0, Read: 1
0 0 1[1] 0 0 1 0
Write: 0, Move: Right, Next State: q0
0 0 1 0[0] 0 1 0
Current State: q0, Read: 0
0 0 1 0[0] 0 1 0
Write: 1, Move: Right, Next State: q0
0 0 1 0 1[0] 1 0
Current State: q0, Read: 0
0 0 1 0 1[0] 1 0
Write: 1, Move: Right, Next State: q0
0 0 1 0 1 1[1] 0
Current State: q0, Read: 1
0 0 1 0 1 1[1] 0
Write: 0, Move: Right, Next State: q0
0 0 1 0 1 1 0[0]
Current State: q0, Read: 0
0 0 1 0 1 1 0[0]
Write: 1, Move: Right, Next State: q0
0 0 1 0 1 1 0 1[_]
このトレースでは、次のことが確認できます：
- 初期状態
q0から開始し、テープの各シンボルを一つずつ読み取ります - 読み取ったシンボルに応じて、反転したシンボルを書き込み、右に移動して次の状態に遷移します
- テープの最後までこのプロセスを繰り返します
まとめ
Stemは、チューリングマシンの基本概念を理解するための強力なツールです。簡単な設定で動作し、視覚的に状態遷移を確認できるため、教育現場での利用に最適です。
ぜひ、このエミュレータを試してみて、チューリングマシンの世界に触れてみてください！