MAKE: Japan: レゴのチューリングマシン

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

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

私は、オリジナルとはちょっと違うチューリングマシンをレゴで作ろうと考えました。双方向テープの替わりに、スタックを使っています。マシンはスタックの下のシンボルを読み取り（そして削除して）、内部状態を変えます。また、スタックの上に0個から2個までのシンボルを追加できるようにしました。

この変更は大きいかもしれませんが、この簡単なマシンが、チューリングマシンと同じ能力を発揮することができます。とりわけ重要なのは、このマシンがスタックの上に置かれたチューリングマシンをエミュレートできるという点です。

私は、簡単なアペンドできるオートマトン（AWA、またはフランスではAAA）のテストを行うための、このリンクをたどって、デモ（AAA.zip）をダウンロードしてください。

オリジナルのチューリングマシンではなく、アペンドできるオートマトンを作った理由は、（ほぼ）無限に長い双方向テープを作りたくなかったからです。

- Phillip Torrone

［原文］

Posted by Tetsuo Kanai | Jun 20, 2008 12:40 AM
LEGO | Permalink | Comments (0)