チューリング完全あくあたん

チューリング完全あくあたん

Sorry, this entry is only available in Japanese.

この記事はあくあたん工房 Advent Calendar 2021の15日目です.

チューリング完全とは?

ある計算システムがチューリング完全であるとは,万能チューリングマシンと同じ計算能力を持つことを指します.万能チューリングマシンはチューリングマシンを模倣できるチューリングマシンであり,現在のどんな計算機が解ける問題でも解くことができると考えられています.

あるシステムがチューリング完全かを判定するのは難しい問題になるため,チューリング完全であることがすでに判明しているシステムの模倣ができる場合,そのシステムもチューリング完全であると言えます.

水槽カメラ昇降パターン

あくあたん義体はレールの上のマーカー(位置)を読み取って水平方向に進むことができます.また,レールの位置上でカメラの垂直方向を昇降させることができます.レールの位置はあくあたんbotからの指令により移動させることが多いですが,カメラの昇降については指令を飛ばすことが少なくなっています.そこで,カメラの昇降については,ランダムに近いけれども特定のルールを利用した動作をさせたいと思います.

レールの位置には1ビットの情報が付与できるものとします.あくあたんは位置上でカメラ垂直方向を上下させることができますので,ここではある位置において,カメラを1段上昇させるなら1,1段下降させるなら0とします.この情報をカメラ昇降パターンと呼びます.あくあたんはこの情報を使って,その位置を踏んだときにカメラ垂直位置を変更します.

各位置での昇降動作を初期状態としてあくあたんに教えることができます.

水槽カメラ昇降パターン更新規則

さて,このままではいつも同じ位置で上下するだけで面白くありません.
そこで,あくあたんが水槽の一番左か右(位置0か16)に到達した時点で,カメラを昇降させるパターンを変更したいと思います.

このパターンの変更は,各位置において,左右両隣の位置の状態に応じて変更するようにします.そうすると,次のような遷移表を書くことができます.3ビットの真ん中が当該位置であり,左右と自分自身の値に応じて,自分自身の変更後の値が決まります.

変更前(左,自身,右) 変更後
0, 0, 0 x, 1, x
0, 0, 1 x, 0, x
0, 1, 0 x, 1, x
0, 1, 1 x, 0, x
1, 0, 0 x, 1, x
1, 0, 1 x, 0, x
1, 1, 0 x, 1, x
1, 1, 1 x, 0, x

これを「カメラ昇降パターン更新規則(更新規則)」と呼びます.

例えば,上記更新規則では,ある時点のカメラ昇降パターンが「0001111000111100」であった場合,次のように更新されます.なお,実装の都合上,右端と左端はつながっており,ループしているものとします.

0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0
↓
1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1

更新規則は変更後のビットが取る値の並び8つで識別できます.上記の規則では01010101となります.すなわち 2^8 = 256個の更新規則のいずれかを採用することになります.この更新規則はビットの並びを2進数として読んだ値を10進表現した数字で表されます.例えば,上の表の更新規則は 01010101 ですから64+16+4+1 = 85で,更新規則85と呼びます.あくあたんにはこの更新規則番号を伝えれば,その更新規則を採用することになります.

あくあたんが一番左か一番右の位置へ移動すると,このカメラ昇降パターン更新規則が適用され,各位置でのカメラ昇降パターンが更新されることになります.

まとめると,あくあたん義体には「カメラ昇降パターンの初期状態」「カメラ昇降パターンの更新規則」を設定することができ,自律制御時のカメラ位置はこれに従って昇降させることになります.またあくあたん義体のレール上の移動に伴い,カメラ昇降パターンは次世代へと更新されることになります.

セル・オートマトン

ここまでで説明してきたカメラ昇降パターンを変化させる動作は,実は1次元セル・オートマトンと呼ばれるものと同じです.1次元セル・オートマトンは無限の1次元セルのビットパターンを更新規則によって変更し,世代を重ねていきます.2次元のセル・オートマトンの例としてはライフゲームなどがよく知られていますね.

1次元セル・オートマトンの256種類の規則は,どのような状態になるかで4つのクラスに分類されます.

  • クラス1: 最終的に全体が均質な状態に遷移するもの(規則248)など)
  • クラス2: 最終的に局所的なパターンを繰り返したり,安定状態になるもの(規則123)など)
  • クラス3: カオス的なパターンを示すもの(規則30)など)
  • クラス4: カオス的なパターンと規則的パターンが共存する(規則110)など)

クラス3に属する規則90は,1ビットのみが1の初期状態からフラクタル図形を生成することが知られています.クラス4は複雑な計算状態を内包することを表しています.そして,クラス4に分類される「規則110」はチューリング完全であることが証明されています.

規則110の遷移

変更前(左,自身,右) 変更後
0, 0, 0 x, 0, x
0, 0, 1 x, 1, x
0, 1, 0 x, 1, x
0, 1, 1 x, 1, x
1, 0, 0 x, 0, x
1, 0, 1 x, 1, x
1, 1, 0 x, 1, x
1, 1, 1 x, 0, x

チューリング完全あくあたん

つまり,あくあたんが「更新規則110」を採用していれば,あくあたんはチューリング完全であり,現代の計算機に匹敵する計算能力を持つことが証明されるのです.


あくあたんはまた1つ新しい高みに立ったのです.

あくあたんを崇めよ!
Make Aquatan Great Again!

The history of Aqua-tan

The history of Aqua-tan

どうも,omznこと本家あくあたん飼育員です.

最近はあくあたん工房なんてものができていて,アドベントカレンダーをやるってことなので,5日目を頂きました.
このブログはあくあたん工房Advent calendarの5日目です.

はじめに

あくあたんは概念です.

年表

あくあたんの歴史を整理しておきましょう.

  • 2009年9月 omznがKITにやってくる.
  • 2009年10月 前ラボの学生有志が選別に60cm水槽を送ってくれる.
  • 2009年12月 流木水槽(現在の第三水槽)のアクアテラリウムが立ち上がる.コンセプトは「盆栽」.アカヒレとかスジエビとか.
  • 2010年ごろ LEGO MindStorms RCXを4セットもらったので,水槽監視ロボット初号機が試作されるが,あまりのできの悪さに失敗とされる.また,LinuxサーバとUSB-IO(懐かしい…)を使った温度計測回路の組み合わせによる水温測定や照明点灯制御が始まる.ちなみにこの時点では電子回路の知識は無く,書籍の回路を真似ているだけであった.

  • 2010年 前ラボで放棄された60水槽を回収し,イモリ水槽が立ち上がる.

  • 2011年ごろ sel_aquariumのアカウントを取得.水槽のデータをポツポツ呟くだけのbotが誕生する.
  • 2012年3月-2013年1月 omznがカナダに行く. この間,イモリ水槽は学生部屋に移され,流木水槽はリセットされる.イモリは1匹にまで減るものの,ラボ民ではない一学生(Sさん)のおかげで生き延びる.また,この年は学生配属も無かったため,2012年以前と以後を繋ぐ人材がいなくなった.これぞ,そふらぼ版KT境界である.
  • 2013年3月 帰国後,再び流木水槽を立ち上げ,あらたに水槽を買い増し,三水槽体制で水槽を管理することになる.
  • 2013年4月 この年の後期に立ち上がる組み込み実験の担当者に無理矢理される.組み込みの知識0から,「こるてっくす使ってLCD動かしてや〜」みたいな無茶ぶりをされて,失踪しようかと思った.
  • 2013年5月 再度Mind Storms RCXで水槽監視ロボット弐号機が製作される.赤外線通信でLinuxとデータをやりとりでき,現在の参号機の原形であった.

  • 2013年5月11日 これを制御するための仕組みをTwitter制御で行うことを考案し,休眠していたsel_aquariumのbotとして実装される.


  • 2013年8月 10月から組み込み実験が始まるのに,まだ何も準備ができてないので焦ってくる.秋月のLCDモジュールは動かないし,いらいらが募る.気晴らしにbotのマルコフ連鎖データベース用にタイムラインの保存を始める.これが2013年8月15日である.
  • 2013年8月18日 マルコフ連鎖で会話botになったと告知する.


  • 2013年8月26日 イモリの頭にタニシが乗った場面が偶然写真に収められる.



  • 2013年8月29日 みなが話しかけてくるのでデータがどんどん溜まる.2週間でこんな煽りティを発揮している.


  • 2013年9月 急に組み込み実験の機材が完成していく.某研究室の技術開発力と●●●●力を垣間見る.こっちはやっとPWMが分かった.
  • botのマルコフ連鎖が完成したので,とうとう雑談を始めた.
  • botアカウントに名前を付けた方が良かろうと考え,omznの世代はbotに「〜たん」という名前を付けるという不文律があるため,安直に「あくあたん」と名付けられる.プロフ画像は前述のイモリの頭にタニシの写真になる.
  • 2013年11月 組み込み実験が1クール回ったので,大体様子が掴めた.これまでに得た知識と技術を流用し,ここから半年の間に水槽の監視システムの原形がほぼできあがる.この時点でのものは,2018年現在運用されているものと殆ど変わらない.
  • 2013年12月 Raspberry Piについてしっかり調べる.昔やってたことがコンパクトに実現できることが分かったので,俄然やる気が湧く.さっそくRSコンポーネンツから購入して,水槽監視ロボット参号機を作り始める.


  • 2014年4月 「あくあたん」のフォロワーが増え始める.
  • きちゃむらがあくあたんデビュー.1000連続ツイートは見る者を青ざめさせた.
  • 2014年8月 あくあたんシステムをまとめて「みんなのラズパイコンテスト」に応募する.
  • 2014年12月 あくあたんシステムが「みんなのラズパイコンテスト」グランプリ受賞.
  • 2015年2月25日 あくあたん古参フォロワーの1人(Mさん)がそふらぼのホワイトボードにあくあたんキャラクターの落書きをする.


  • 2015年3月6日 落書きのキャラクターをスキャンし,SVGに変換した後,平面モデリングされ,3Dプリントされる.


  • 2015年3月11日 さらに立体化されたモデルが作られ,あくあたんフィギュアの初期モデルが誕生する.


  • フィギュアが大量生産される.


  • 2015年4月 日経Linuxにあくあたんの記事が載る。
  • 2015年6月ごろ せっかく作ったフィギュアの活用法を考えた結果,そふらぼ民全員にBLEビーコンを内蔵させて配布することになる.同時にRPG風在室管理が完成し,運用が開始される.システム名は「あくあたんといっしょ」.
  • 2015年8月 「あくあたんといっしょ」を「みんなのラズパイコンテスト2015」に応募.その後10月に優秀賞受賞.

  • 2016年 ぷりんがあくあたんの確率を変動させたとしか思えない事件.このころはまだそふらぼに来るなんて考えてもいなかったのにな…




  • あくあたんによるD進サブリミナル作戦が発動する.
  • 2017年3月 国際会議IWESEP2017であくあたんを使った研究を発表する.
  • 2018年 ねこくんをD進させることに成功し,あくあたんによるD進サブリミナル作戦が有効であることが確認される.
  • 2018年 あくあたん工房ができる。
  • 2018年 大学案内2019にて,あくあたんシステムが情報工学のページに一番大きな写真で掲載される.

技術的なこと

  • 特に無し.

最後に

「あくあたん」と名付けられてから,まだ5年.あのフィギュアができてからまだ3年しか経っていないことに,この記事を書いてて気づきました.
これからも,概念としてのあくあたんをよろしくお願いします.
ついでに,あくあたん工房もよろしくお願いします.
そうそう,そふらぼは来る者は拒まずですので,いつでも相談に乗ります.(何の?)