先日、『精霊の箱 チューリングマシンをめぐる冒険』を読み終えたのですが、非常に面白かったので、いくつか実際に動かしてみました。
turing_machine.rb
ショールマンに割り当てられた設計図
1行目に入力文字列、2行目以降にファウマン卿の記述方法を書いていきます。本の中では、終了状態が丸付き数字で表現されていましたが、最後の行の最右の数字を終了状態にしています。
$ cat input.txt ○○●●○○●○● 1○○→1 1●●→1 1 ○←2 2○○←2 2●●←2 2 →3 3○ →4 3● →4
実行
ショールマンに割り当てられた設計図は入力数を2倍するものでした。
$ ruby turing_machine.rb < input.txt ○○●●○○●○●: 状態1 ↑ ○○●●○○●○●: 状態1 ↑ (途中略) ○○●●○○●○●○: 状態3 ↑ ○●●○○●○●○: 状態4 ↑
ララヴに割り当てられた設計図
$ cat input.txt ○●○○●●●○●○○●●○ 1○○→1 1 →5 1●●→2 2●●→4 2○○←3 2 ←3 3●○→1 4●●→4 4○○→1 4 →5
実行
ララヴに割り当てられた設計図は、○と○に挟まれた単独の●が○に変えられ、●の連続だけが残るものでした。
$ ruby turing_machine.rb < input.txt ○●○○●●●○●○○●●○: 状態1 ↑ ○●○○●●●○●○○●●○: 状態1 ↑ (途中略) ○○○○●●●○○○○●●○ : 状態1 ↑ ○○○○●●●○○○○●●○ : 状態5 ↑
ヤークフに割り当てられた設計図
$ cat input.txt ○●●○○ 1○○→1 1●●→1 1 ｜←2 2××←2 2○×→3 2●×→4 2 →6 3○○→3 3●●→3 3××→3 3｜｜→3 3 ○←5 4○○→4 4●●→4 4××→4 4｜｜→4 4 ●←5 5○○←5 5●●←5 5｜｜←2 6× →6 6｜ →7
実行
ヤークフに割り当てられた設計図は、元の文字列を反転させるものでした。
$ ruby turing_machine.rb < input.txt ○●●○○: 状態1 ↑ ○●●○○: 状態1 ↑ (途中略) ｜○○●●○: 状態6 ↑ ○○●●○: 状態7 ↑
全角スペースのところで表示が崩れていますが、実際は以下のように表示されています。
