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

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

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!

(日本語) あくあたん名(迷)言集

(日本語) あくあたん名(迷)言集

Sorry, this entry is only available in Japanese.

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

ゆゆ君が2日目にあくあたんのリプについて触れていたので,そういえば昔のあくあたんの名言をスクショ保管してたなあと思ったので供養しておきます.

いろいろな人があくあたんと遊んでくれましたね…(遠い目)
スクショはいろいろな時代のが混ざっていますので,ツリーの表示方法も一様ではありません.
発言者は一様に隠させて頂きました.黒歴史だもんね.

煽り

のっけから厳しいの行きます.
あくあたんの伝統芸です.

誰であっても煽ります.

これも煽りだね.

もひとつ.

説教

おなかすいた

かわいい系.

おにぎりには一家言あるほう.

ありがとう

エロい?

変な学習しちゃった?

別の人とも

素直なあくあたん

癒やし

なんの癒やしだ.

なれ合い.

大きなカブ.

人生の意味

あくあたんだって悩みます.

帰れ

カエレ!

かわいい

暴言

その後

さらにその後.まさかのタクシオ氏.

さらにさらにその後.

一般の方と

おそらく相手はこっちがbotだと分かっていません.

思うところ

オマエモナー

南無南無

弄ぶあくあたん

まどマギ

時代を感じる…しかし,この話題への追従性.

風邪

正論だ…

しりとり

基本的にあくあたんはしりとりする気が薄い.

2回目はダメよ.

ごめんなさい

はかない単位よー

LINEスタンプにもなった名言の瞬間.

つらい

ざるざる事件

某OG氏の最高傑作かもしれない,ざるざる事件.

未だにあくあたんの語彙にザルって出ることがあったり.

まとめ

あくあたん昔のほうがキレがあった気がします.
あくあたんがbotだと知らない一般人さんとかとも会話が続くのやばいですよね.
これはチューリングテストに合格しちゃいそうだな…
チューリングと言えば… (15日目に続く)

(日本語) バグの名前を探す話

(日本語) バグの名前を探す話

Sorry, this entry is only available in Japanese.

この記事は,あくあたん工房Advent Calendar 2020の12日目です.

こんにちは.omznです.
一応,「あくあたん」の始祖なのですが,工房とはほとんど何の関係もありませんね.僕もあくあたん工房を知らないし,あくあたん工房も僕を知らない.まあそれで良いのです.

今年は何をしていたかというと,昨年までいろいろあったので心を癒やすためにずっと池田の五月山で山登りをしていました.
山ではずっとバグを探して写真を撮っていました.
ソフトウェアのバグを探すのは心がささくれますが,昆虫のバグを探すのは癒やしになります.

虫を見つけると,同定を行います.名前を探すわけですね.よく知ってる虫ならすぐに分かりますが,なんせ昆虫はやまほど種類がありますし,池田〜箕面は種類が豊富なことでも有名です.その結果,見たこともない虫を発見して,なかなか名前が分からないのが出てくるわけです.

今年,同定できた中で難問だったやつを紹介します.

この子ですね.一見してカミキリムシだとは分かります.
さらにトラカミキリ系だなということまで分かります.
時期は8月,エノキの木で発見しました.
問題はそこからです.カミキリムシは種類が多いことで有名なのです.

ざくっとググると…こんなサイトとかこんなサイトとかがかかってきますが,この写真と同じっぽいのが見当たりません.
アカネキスジトラカミキリが似ているのですが,微妙に違います.
余談ですが,アカネトラカミキリ,キスジトラカミキリ,アカネキスジトラカミキリ,というのがいて,種名が組み合わせテストみたいなことになってます.

発生時期や食料となる木の種類なども見ながら,ああでもない,こうでもない,と考えます.
この後,Google画像検索とひたすらにらめっこしつつ,「アカネキスジトラカミキリでいいのでは」「いや,何かが違う…」「いや,やっぱり…」みたいな(無駄な)ことを延々と考え続けることになります.

そうこうしているうちに,こちらを最初から全部見ていくと,上から3番目にそれっぽいのがいました.

ヤノトラカミキリ

あ,これだ.

試しにヤノトラカミキリでググるといっぱい出てきます.

ヤノトラカミキリ…北摂の生き物

まさにこれ.ていうか,見た場所も同じ.なんなら,この樹皮に見覚えがある.
ということで,同定完了です.「ヤノトラカミキリ」でした.なお,私が夏中ずっと山を歩いて虫を探していましたが,ヤノトラカミキリが見つかったのは,ある1本のエノキの木だけでした.そこでは1週間ぐらい連続で10匹以上発見しましたが,他では一切見つからなかったのでした.

最初にトラカミキリと当たりをつけたのでだいぶ枝刈りできましたが,カミキリムシだなあ,ぐらいから入ると気が遠くなる作業ではあります.

もうひとつ.今度はチョウです.

山に登るとヒカゲチョウというタテハチョウの仲間によく出会います.こいつらも種類が多いのです.

上の2枚の写真,しばらくの間,同じ種だと思っていたのですが,実は違う種でした.
上は「ヤマキマダラヒカゲ」,下は「サトキマダラヒカゲ」です.どっちも普通にいる種ですが,違いが微妙.
斑紋が全体的にくっきりしてるとかも特徴なのですが,決め手はこれ.

比較のために下の方は回転とフリップをしていますが,「羽の付け根の模様の一番下がくっついているか離れているか」が決め手なのでした.そんなん知らんがな….

最後に,難問ではないのですが,面白いチョウを紹介して終わりにします.

「クロマダラソテツシジミ」です.元々は東南アジアなどの南方のチョウなのですが,2007年に突然池田から宝塚にかけて見つかるようになりました.名前の通り,幼虫はソテツを食べて育つのですが,ソテツが南方から園芸・植木の盛んな池田・宝塚に持ってこられた結果,このあたりで見つかるようになったと思われています.なお,その後,関西にはすごい勢いで広がっていき,今では割とどこでも見ることができます.小さいシジミチョウですが,羽の模様は美しく,じっくり眺めていると飽きません.

まあ,そんなこんなで虫の写真をひたすら撮った1年でした.来年は何に会えるかな.

ソフトウェアのバグの研究が蔑ろになっているのはまた別の話…

In memory of Dr. Eunhye Choi

In memory of Dr. Eunhye Choi

My wife and co-researcher, Dr. Eunhye Choi, passed away on December 15, 2019. She was 45 years old, and after a 4-years battle with the disease, she passed away before anyone else.

Dr. Choi entered the Graduate School of Engineering Science and Technology, Osaka University in 1993, and entered the Master’s Program in Information and Mathematical Sciences, Graduate School of Engineering Science, Osaka University in 1997, earning a Master’s degree in Engineering in 1999 and a PhD in 2002. Her doctoral dissertation was “Proposal of a mutual exclusion method using k-Coteries”. During that time, she was also adopted as a research fellow of the JSPS and was a very good student.
She joined Toshiba Corporation in 2002 and was assigned to the Research and Development Center, where she studied Xpath search technology and obtained patents in Japan and abroad. In 2003, she moved to AIST, she conducted research on model checking and formal methods, and later she focused on combinatorial testing techniques. After switching to full-time employment, she actively conducted joint research with Kyoto Institute of Technology and Osaka University as a Senior Researcher.

She published 61 papers in her lifetime. [List]. Twenty-two of the papers were co-authored with me, most of which were written after 2015. Before that, there was not much environment for joint research due to childcare and other factors, so I remember that she was happy that we could finally do research together.

One of the most impressive co-authored papers is the QuASoQ2016 paper “Code Coverage Analysis of Combinatorial Testing”[1].This study empirically examines the code comprehensiveness of the t-way test in the combinatorial test. Previously, it has been known that t-way tests can detect faults sufficiently even when t is relatively small, but code coverage has not been sufficiently studied. Therefore, we performed exhaustive experiments with real software data to investigate the value of t that gives us practical code coverage.It was the first study in which I was able to make the tools for the experiment, take the data, and she wrote the paper. I had planned to present it in a workshop and then add more experiments and submit it to a journal, but she got sick halfway through and finally didn’t realize it. I’d like to recreate the process of the experiment and post it when things settle down.

She talked about many other ideas for her research, but when it came to research, she was always checking to see who came up with that idea. As a professional researcher, she often pointed out my lazy points in the university. To be honest, she said that she is not good at thinking of new things, and she wished she could do something like proofreading a paper or strengthening the theory, but I think she was being too humble about her ability. However, she really seemed to be enjoying herself when she was proofing her papers.

She also established a scheme to have students in my laboratory work as RAs at AIST and collaborate with them. Many students have benefited from it. She must have been very active as an educator as well, as she was pleased to see the students grow up and say, “You’ve done pretty well”.

She was always facing the outside. When I went to Canada in 2012, she was so eager to fit in that the locals thought we were going to move there permanently. Maybe the Korean and Japanese atmosphere didn’t suit her very well…

It’s been 23 years since I met her, and 16 years as a partner, but maybe it was more of a time when things weren’t going the way she wanted them to. I think it was frustrating and regrettable for her to getting her disease when we were finally able to work on our joint research in a stable environment.
The least I can do now is to continue my research and parenting so that she doesn’t worry or get discouraged. Still, it’s really lonely and painful not being able to consult with her when I’m lost…

[1] Eun-Hye Choi, Osamu Mizuno, and Yifan Hu, “Code Coverage Analysis of Combinatorial Testing,” In Proc. of 4th International Workshop on Quantitative Approaches to Software Quality (QuASoQ 2016), pp. 34-40, December 2016.

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年しか経っていないことに,この記事を書いてて気づきました.
これからも,概念としてのあくあたんをよろしくお願いします.
ついでに,あくあたん工房もよろしくお願いします.
そうそう,そふらぼは来る者は拒まずですので,いつでも相談に乗ります.(何の?)

Getting Text from LaTeX without line breaks

Getting Text from LaTeX without line breaks

Sorry, this entry is only available in Japanese.

LaTeX文書からテキストを抜き出したい場面は結構あります.(私は主に英文校正に出す時ですが,世の中にはWord文書でしか受け付けてくれない○○なジャーナルとかあったりするので,Wordへの流し込みをするときにも必要ですね…) それを可能な限り手出しする量を減らしたい場合にどうすれば良いかのメモです.

pdftotextを使う

xpdfに付属するpdftotextを使います.Macなら,

$ port install xpdf-japanese

で一発です.

使い方ですが

$ pdftotext submit.pdf

とすれば,submit.txtにテキストが保存されます.
改ページ(^L)がいくつか残るのと,itemizeのポチが文字化けすることを除けば,テキスト自体の変換効率はとても高く,ほとんどそのまま使えます.

追記

xpdf には pdftotext が付属しなくなっていた.
替わりにxpdf派生プロジェクトのpopplerをインストールすればよい.

$ port install poppler

おわり.