Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
君は古の言語M4を知っているか (LT)
Search
MakKi
May 18, 2022
Programming
0
420
君は古の言語M4を知っているか (LT)
M4のチューリング完全性について、BrainF*ckを実装することで証明した
MakKi
May 18, 2022
Tweet
Share
More Decks by MakKi
See All by MakKi
XSLTで作るBrainfuck処理系
makki_d
0
210
眼鏡と視力についての誤解を解く
makki_d
0
120
標準ライブラリの動向とイテレータのパフォーマンス
makki_d
3
680
range over funcのエラー処理
makki_d
1
1.7k
GoとテストとインプロセスDB
makki_d
3
600
型パラメータが使えるようになったのでLINQを実装してみた
makki_d
2
1.4k
mallocしただけでメモリが確保できるって本当ですか?
makki_d
0
230
ホットリロードツールの作り方
makki_d
0
1.1k
JavaプログラムをGoに移植するためのテクニック――継承と例外
makki_d
1
1.8k
Other Decks in Programming
See All in Programming
ASP.NETアプリケーションのモダナイズ インフラ編
tomokusaba
1
390
データの民主化を支える、透明性のあるデータ利活用への挑戦 2025-06-25 Database Engineering Meetup#7
y_ken
0
280
Select API from Kotlin Coroutine
jmatsu
1
180
Blazing Fast UI Development with Compose Hot Reload (droidcon New York 2025)
zsmb
1
110
Enterprise Web App. Development (2): Version Control Tool Training Ver. 5.1
knakagawa
1
120
イベントストーミング図からコードへの変換手順 / Procedure for Converting Event Storming Diagrams to Code
nrslib
1
150
型付きアクターモデルがもたらす分散シミュレーションの未来
piyo7
0
800
地方に住むエンジニアの残酷な現実とキャリア論
ichimichi
2
630
関数型まつり2025登壇資料「関数プログラミングと再帰」
taisontsukada
2
840
Railsアプリケーションと パフォーマンスチューニング ー 秒間5万リクエストの モバイルオーダーシステムを支える事例 ー Rubyセミナー 大阪
falcon8823
3
750
設計やレビューに悩んでいるPHPerに贈る、クリーンなオブジェクト設計の指針たち
panda_program
3
310
Datadog RUM 本番導入までの道
shinter61
1
310
Featured
See All Featured
The World Runs on Bad Software
bkeepers
PRO
69
11k
The Success of Rails: Ensuring Growth for the Next 100 Years
eileencodes
45
7.4k
Building Better People: How to give real-time feedback that sticks.
wjessup
367
19k
No one is an island. Learnings from fostering a developers community.
thoeni
21
3.3k
Site-Speed That Sticks
csswizardry
10
650
jQuery: Nuts, Bolts and Bling
dougneiner
63
7.8k
Intergalactic Javascript Robots from Outer Space
tanoku
271
27k
Build The Right Thing And Hit Your Dates
maggiecrowley
36
2.8k
It's Worth the Effort
3n
184
28k
Designing Dashboards & Data Visualisations in Web Apps
destraynor
231
53k
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
sstephenson
161
15k
Gamification - CAS2011
davidbonilla
81
5.3k
Transcript
君は古の言語 M4を知っているか KLab株式会社 牧内大輔
自己紹介 • 牧内大輔(MakKi) • Twitter: @makki_d • GitHub: makiuchi-d •
学生の頃 ◦ 専攻は発生生物学 ◦ 動画関連のOSS(AviUtlの透過性ロゴとかいろいろ) • 入社してから ◦ ガラケー向けブラウザゲーム→スマホゲーム
最近の仕事 オンライン対戦データ中継システム • クライアント: 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) 部屋検索・参加
M4 is 何?
M4 is 何? “ m4 は、ブライアン・カーニハンとデニス・リッチーが設計した汎用マク ロプロセッサである。その名称は、"macro" の "m" と、AP-3ミニコ
ンピュータでデニス・リッチーがそれ以前に書いたマクロプロセッサ "m3" の次、というところから来ている。 出展:wikipedia http://ja.wikipedia.org/wiki/M4_(プログラミング言語)
マクロプロセッサ?
マクロプロセッサ define(`H’, `Hello, $1!!’) こんなマクロを定義して
マクロプロセッサ define(`H’, `Hello, $1!!’) H(traP) こんなふうに呼び出すと
マクロプロセッサ define(`H’, `Hello, $1!!’) H(traP) Hello, traP!! これが出力される
マクロプロセッサ define(`H’, `Hello, $1!!’) H(traP) Hello, traP!! これが出力される 定型文を生成するのに便利
M4 is 何? “ ……それ以前のマクロプロセッサとは異なり、特定のコンピュータ言語 や自然言語を対象としたものではない。ただし、もとはFORTRANの方言 であるRatforの開発で使うために開発された。 他のマクロプロセッサとは異なり、m4 は一般的なプログラミング言語と 同様、チューリング完全である。
出展:wikipedia http://ja.wikipedia.org/wiki/M4_(プログラミング言語)
チューリング完全?
チューリング完全 “ 計算理論において、ある計算のメカニズムが万能チューリングマシンと 同じ計算能力をもつとき、その計算モデルはチューリング完全(チューリ ングかんぜん、Turing-complete)あるいは計算完備であるという。 (中略) 簡単に言えば、チューリング完全であれば、実現可能なアルゴリズムや 手続きはすべて処理できるということを意味している。 出展:wikipedia http://ja.wikipedia.org/wiki/チューリング完全
つまり コンピュータで動かせるアルゴリズムは 全てM4でも記述できる
つまり コンピュータで動かせるアルゴリズムは 全てM4でも記述できる M4は万能
確かめてみよう
確かめてみよう チューリング完全性の証明 • チューリング完全な処理系を実装できればOK
確かめてみよう チューリング完全性の証明 • チューリング完全な処理系を実装できればOK チューリング完全な処理系 Brainfuck
Brainfuckとは +++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.++++++ +..+++.>-.------------.<++++++++.--------.+++.------.- -------.>+. Hello, world!
M4で実装してみた
bfm4 https://github.com/makiuchi-d/bfm4 KLab TechBook Vol.1 でも解説(PDFダウンロードできます) https://www.klab.com/jp/blog/tech/2022/tbf12.html
デモ
結論 M4はチューリング完全である. Q.E.D.
ありがとうございました。