チューリングタンブル

初心者向けチューリングタンブルレイアウト

Turing Tumbleは、機械的なコンピューティングによる論理ゲートのゲームおよびデモンストレーションです。

説明

アラン・チューリングにちなんで名付けられたこのゲームは、ゲームフィールド自体が十分に広ければ、抽象的にはあらゆるコンピュータのプロセスを複製できる。これは、このゲームが回路値問題によってP完全であり、指数関数的な数のビー玉を許容する場合PSPACE完全であることから導かれる。 [ 1 ] [ 2 ]この装置はナノテクノロジーにも影響を与える。[ 3 ] [ 4 ]

このゲームはチューリング完全であると宣伝されている。無限に大きい盤と無限の数の駒を許容するゲームの拡張は、セルオートマトンの第110規則とチューリングマシンの両方のシミュレーションによってチューリング完全であることが示された。[ 5 ] [ 6 ]

重力で動く金属球を巧みに使ったパチンコ台に似ていますが、本来は論理、つまりコンピュータプログラミングの基礎を教える教材であり、ゲーミフィケーションの一例と言えるでしょう。付属のコミックブックのフレーミングデバイスには、コンピュータプログラミングの基礎を解説する60問の論理問題を、徐々に難易度が上がっていく問題で解かなければならない宇宙 飛行士が登場します。

歴史

この装置にパズルを組み込むきっかけとなったのは、当時ミネソタ大学に在籍していたプログラマー兼化学教授のポール・ボズウェル（妻でDIY愛好家のアリッサ・ボズウェルと共に）が、他の科学者たちのプロジェクトに必要な計算能力の欠如に苛立ちを感じていたことでした。ボズウェルは既にテキサス・インスツルメンツ社製のコンピュータ向けに複雑なゲームをプログラミングすることで有名でした。発明者たちは、1960年代後半に登場した先駆的な製品であるDigi-Comp IIにも影響を受けました。 [ 7 ]

コンポーネント

チューリングタンブルマシンには次の部品があります。

  • ボールドロップ - 標準バージョンでは、一定数のボールを収納できる2つのランプが使用されています。ボード下部のスイッチを押すと、パネルの左上から最初のボール（通常は青）が放出されます。右側の2つ目のランプには、赤いボールが入っています。
  • ランプとクロスオーバー – 緑のランプでは、ボールは一方向にしか走らず、その方向にのみ放出されます。一方、オレンジ色のクロスオーバーでは、ボールはどちらの側へも両方向、つまり右から左へも左から右へも通過できます。
  • インターセプター – この黒いピースはボールを止めます。
  • ビット – これは 1 ビットのストレージです。ボールが転がると方向が変わり、次のボールは反対側に移動します。
  • ギアとギアビット – ギアビットは通常のビットと全く同じですが、ギアに接続できます。ギアは状態変化を連動させ、それによって統合的に（抽象的な）パワーを追加します。

受付

批判的に言えば、このデバイスはそのコンセプトと実行において高い評価を受けているが[ 8 ]、いくつかの注意点（推奨年齢は8歳以上）がある。[ 9 ]

このコンピューティングゲームは、ペアレンツ・チョイス・ゴールド賞[ 10 ]を受賞し、アメリカ専門玩具小売協会主催の「2018年ベスト玩具賞」部門でも受賞しました。[ 11 ]

参考文献

  1. ^ジョンソン、マシュー（ 2019年4月）「チューリングタンブルはP ( SPACE)-完全である」。アルゴリズムと複雑性。コンピュータサイエンス講義ノート。第11485巻。pp.  274– 285。doi : 10.1007 /978-3-030-17402-6_23。ISBN 978-3-030-17401-9. S2CID  159042415 .
  2. ^ Hoover, H. James (2019年5月26日). 「チューリングタンブルはP完全である」 . sites.ualberta.ca . 2020年7月27日時点のオリジナルよりアーカイブ。
  3. ^富田 隆宏 (2018年6月20～22日). 「チューリングタンブルモデルにおける可逆論理要素の構築」(PDF) . Proceedings of Automata 2018 : 25–32 . 2020年5月6日時点のオリジナルよりアーカイブ(PDF) . 2019年12月10日閲覧.（注：2019年に長いバージョンが出版されました。）
  4. ^富田 貴弘; 李 賈; 磯川 貞二郎; ペパー フェルディナンド; 湯本 貴之; 上浦 直武 (2019-09-03). 「チューリングタンブル上に構築されたユニバーサル論理要素」 . Natural Computing . 19 (9). Springer-Verlag : 787– 795. doi : 10.1007/s11047-019-09760-8 . eISSN  1572-9796 . ISSN  1567-7818 . S2CID  201714072 . 2020年7月27日時点のオリジナルよりアーカイブ。 2020年7月27日閲覧。(注:この論文の短縮版はAUTOMATA 2018 で発表されました。)
  5. ^ Pitt, Lenny (2023-02-28). 「チューリングタンブルはチューリング完全である」 .理論計算機科学. 948-113734 . arXiv : 2110.09343 . doi : 10.1016/j.tcs.2023.113734 . S2CID 239016461 . 
  6. ^ 「チューリング完全性の証明？」チューリングタンブルコミュニティボード。2018年7月17日。
  7. ^ Frauenfelder, Mark (2017年4月30日). 「クールな大理石動力の機械式コンピュータが論理的な問題を解決」 . BoingBoing . 2020年7月27日時点のオリジナルよりアーカイブ。 2019年12月10日閲覧。
  8. ^ Hall, Stephen (2018年12月5日). 「Review: Turing Tumble」 . Geeks Under Grace . 2019年12月2日時点のオリジナルよりアーカイブ。 2019年12月10日閲覧。
  9. ^ 「Turing Tumble: A Timberdoodle Review」 . MamaBeanAz . 2019年9月15日. 2020年7月27日時点のオリジナルよりアーカイブ。 2019年12月10日閲覧。
  10. ^ 「チューリングタンブル：ビー玉で動くコンピューターを作ろう」ペアレンツチョイス財団。
  11. ^ 「アメリカ特殊玩具小売協会が2018年キッズ向けベスト玩具賞受賞者を発表」(PDF) 2018年7月13日。
ウィキメディア コモンズには、チューリング タンブルに関連するメディアがあります。
「 https://en.wikipedia.org/w/index.php?title=Turing_Tumble&oldid=1329528597」より取得