君は古の言語M4を知っているか (LT)

M4のチューリング完全性について、BrainF*ckを実装することで証明した

Transcript

1. 君は古の言語 M4を知っているか KLab株式会社 牧内大輔
2. 自己紹介 • 牧内大輔（MakKi） • Twitter: @makki_d • GitHub: makiuchi-d • 学生の頃 ◦ 専攻は発生生物学 ◦ 動画関連のOSS（AviUtlの透過性ロゴとかいろいろ） • 入社してから ◦ ガラケー向けブラウザゲーム→スマホゲーム
3. 最近の仕事 オンライン対戦データ中継システム • クライアント： C# (Unity/.Net) • サーバ： Go+MySQL(Aurora) • 通信： WebSocket、gRPC • 開発環境： docker-compose game (go) lobby (go) hub (go) MySQL 端末 部屋検索 gRPC 部屋作成・参加 部屋情報書き込み websocket 観戦clientとして接続 websocket clientとして接続 （Player or 観戦) HTTP(msgpack) 部屋検索・参加
4. M4 is 何？
5. M4 is 何？ “ m4 は、ブライアン・カーニハンとデニス・リッチーが設計した汎用マク ロプロセッサである。その名称は、"macro" の "m" と、AP-3ミニコ ンピュータでデニス・リッチーがそれ以前に書いたマクロプロセッサ "m3" の次、というところから来ている。 出展：wikipedia http://ja.wikipedia.org/wiki/M4_(プログラミング言語)
6. マクロプロセッサ？
7. マクロプロセッサ define(`H’, `Hello, $1!!’) こんなマクロを定義して
8. マクロプロセッサ define(`H’, `Hello, $1!!’) H(traP) こんなふうに呼び出すと
9. マクロプロセッサ define(`H’, `Hello, $1!!’) H(traP) Hello, traP!! これが出力される
10. マクロプロセッサ define(`H’, `Hello, $1!!’) H(traP) Hello, traP!! これが出力される 定型文を生成するのに便利
11. M4 is 何？ “ ……それ以前のマクロプロセッサとは異なり、特定のコンピュータ言語 や自然言語を対象としたものではない。ただし、もとはFORTRANの方言 であるRatforの開発で使うために開発された。 他のマクロプロセッサとは異なり、m4 は一般的なプログラミング言語と 同様、チューリング完全である。 出展：wikipedia http://ja.wikipedia.org/wiki/M4_(プログラミング言語)
12. チューリング完全？
13. チューリング完全 “ 計算理論において、ある計算のメカニズムが万能チューリングマシンと 同じ計算能力をもつとき、その計算モデルはチューリング完全（チューリ ングかんぜん、Turing-complete）あるいは計算完備であるという。 (中略) 簡単に言えば、チューリング完全であれば、実現可能なアルゴリズムや 手続きはすべて処理できるということを意味している。 出展：wikipedia http://ja.wikipedia.org/wiki/チューリング完全
14. つまり コンピュータで動かせるアルゴリズムは 全てM4でも記述できる
15. つまり コンピュータで動かせるアルゴリズムは 全てM4でも記述できる M4は万能
16. 確かめてみよう
17. 確かめてみよう チューリング完全性の証明 • チューリング完全な処理系を実装できればOK
18. 確かめてみよう チューリング完全性の証明 • チューリング完全な処理系を実装できればOK チューリング完全な処理系 Brainfuck
19. Brainfuckとは +++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.++++++ +..+++.>-.------------.<++++++++.--------.+++.------.- -------.>+. Hello, world!
20. M4で実装してみた
21. bfm4 https://github.com/makiuchi-d/bfm4 KLab TechBook Vol.1 でも解説（PDFダウンロードできます） https://www.klab.com/jp/blog/tech/2022/tbf12.html
22. デモ
23. 結論 M4はチューリング完全である. Q.E.D.
24. ありがとうございました。