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