Kids

2008.06.20

レゴのチューリングマシン

Text by kanai

Turing Top
Turing Middle
Turing Bottom
レゴで作ったチューリングマシンだ。Denisの記事より:

私は、オリジナルとはちょっと違うチューリングマシンをレゴで作ろうと考えました。双方向テープの替わりに、スタックを使っています。マシンはスタックの下のシンボルを読み取り(そして削除して)、内部状態を変えます。また、スタックの上に0個から2個までのシンボルを追加できるようにしました。
この変更は大きいかもしれませんが、この簡単なマシンが、チューリングマシンと同じ能力を発揮することができます。とりわけ重要なのは、このマシンがスタックの上に置かれたチューリングマシンをエミュレートできるという点です。
私は、簡単なアペンドできるオートマトン(AWA、またはフランスではAAA)のテストを行うための、このリンクをたどって、デモ(AAA.zip)をダウンロードしてください。
オリジナルのチューリングマシンではなく、アペンドできるオートマトンを作った理由は、(ほぼ)無限に長い双方向テープを作りたくなかったからです。

– Phillip Torrone
原文