『アンダースタンディングコンピューテーション』

https://gyazo.com/48c02a1eabde550887fd1a329f5685b7

/mrsekut-book-487311697X

計算可能性理論をRubyでやる本

かなり実装よりなのでちゃんとした理論をやりたいならちょっと違う

良い本なのだが、Rubyなのもあり、真面目に読めていないmrsekut.icon

一度読んだことがあったが途中で時間が開いてしまったので再読mrsekut.icon

前はRubyでやったけど、今回は練習がてらRustでやってみる

github

https://learning.oreilly.com/library/view/andasutandeingu-konpiyutesiyon-dan-chun-naji-jie-karabu-ke-neng-napuroguramumade/9784873116976/

オライリーのサブスク日本語

2章プログラムの意味

言語仕様

操作的意味論

スモールステップ意味論

Rustがむずいのと、コンパイラを作ったことがアレば、いちいち実装しなくても具体的に理解できるので、手を動かすのはもういいかな、、ってなった..mrsekut.icon

ここでやっているのは、lexer、parserは実装せずに、ASTをクラスで表現して、それを評価する評価器を作ってる感じ

while文を簡約するとif&whileになるのは面白い

3章最も単純なコンピュータ

有限オートマトン

正規表現

#未読

https://qiita.com/ogata-k/items/60788a507ee224494fbe

5章究極の機会

チューリングマシン

プッシュダウンオートマトンってなんやmrsekut.icon

4章にかいてるんか？

pp.142-147

シミュレーションの部分未読

非決定性チューリングマシン

p.147-未読

6章無からのプログラミング

procだけを用いてFizzBuzzを実装する

ラムダ計算

型なしラムダ計算

外延的等価性

extensional equality

外から見える振る舞いに基づいて2つのものを等価に扱うこと

ex. 関数A, 関数Bは内部の実装は知ることが出来ないが、すべての引数に対し、等しい結果を返すので、等価と扱う

アクションの反復によって数を特徴づける

procをn回呼び出すことで、数nを表現する

Church encoding

8章

ライスの定理

日本語版まえがき

はじめに

1章　Rubyひとめぐり

1.1　対話型 Rubyシェル

1.2　値

1.2.1　基本データ

1.2.2　データ構造

1.2.3　Proc

1.3　制御フロー

1.4　オブジェクトとメソッド

1.5　クラスとモジュール

1.6　その他の機能

1.6.1　ローカル変数と代入

1.6.2　文字列の式展開

1.6.3　オブジェクトのインスペクト

1.6.4　文字列のプリント

1.6.5　可変長引数のメソッド

1.6.6　ブロック

1.6.7　Enumerable

1.6.8　Struct

1.6.9　モンキーパッチング

1.6.10　定数の定義

1.6.11　定数の削除

第I部　プログラムと機械

2章　プログラムの意味

2.1　「意味」の意味

2.2　構文

2.3　操作的意味論

2.3.1　スモールステップ意味論

2.3.2　ビッグステップ意味論

2.4　表示的意味論

2.4.1　式

2.4.2　文

2.4.3　応用

2.5　実際の形式意味論

2.5.1　形式

2.5.2　意味の理解

2.5.3　その他のスタイル

2.6　パーサの実装

3章　最も単純なコンピュータ

3.1　決定性有限オートマトン

3.1.1　状態、規則、入力

3.1.2　出力

3.1.3　決定性

3.1.4　シミュレーション

3.2　非決定性有限オートマトン

3.2.1　非決定性

3.2.2　自由移動

3.3　正規表現

3.3.1　構文

3.3.2　意味論

3.3.3　パース

3.4　等価性

4章　能力を高める

4.1　決定性プッシュダウン・オートマトン

4.1.1　ストレージ

4.1.2　規則

4.1.3　決定性

4.1.4　シミュレーション

4.2　非決定性プッシュダウン・オートマトン

4.2.1　シミュレーション

4.2.2　非等価性

4.3　プッシュダウン・オートマトンによるパース

4.3.1　字句解析

4.3.2　構文解析

4.3.3　実用性

4.4　どれだけ能力があるか

5章　究極の機械

5.1　決定性チューリングマシン

5.1.1　ストレージ

5.1.2　規則

5.1.3　決定性

5.1.4　シミュレーション

5.2　非決定性チューリングマシン

5.3　最大の能力

5.3.1　内部ストレージ

5.3.2　サブルーチン

5.3.3　複数のテープ

5.3.4　多次元のテープ

5.4　汎用機械

5.4.1　エンコード

5.4.2　シミュレーション

第II部計算と計算可能性

6章無からのプログラミング

6.1　ラムダ計算をまねる

6.1.1　Procの利用

6.1.2　問題

6.1.3　数

6.1.4　ブール値

6.1.5　述語

6.1.6　ペア

6.1.7　数値演算

6.1.8　リスト

6.1.9　文字列

6.1.10　解答

6.1.11　高度なプログラミングテクニック

6.2　ラムダ計算の実装

6.2.1　構文

6.2.2　意味論

6.2.3　パース

7章　至るところにある万能性

7.1　ラムダ計算

7.2　部分再帰関数

7.3　SKIコンビネータ計算

7.4　Iota

7.5　タグシステム

7.6　循環タグシステム

7.7　コンウェイのライフゲーム

7.8　ルール 110

7.9　ウルフラムの 2,3チューリングマシン

8章　不可能なプログラム

8.1　厳然たる事実

8.1.1　万能システムはアルゴリズムを実行できる

8.1.2　プログラムはチューリングマシンの代わりになる

8.1.3　コードはデータである

8.1.4　万能システムは永久にループできる

8.1.5　プログラムは自己参照できる

8.2　決定可能性

8.3　停止性問題

8.3.1　停止性チェッカーの構築

8.3.2　決してうまくいかない

8.4　その他の決定不能な問題

8.5　残念なこと

8.6　なぜ起こるのか

8.7　計算不能性に対処する

9章　おもちゃの国のプログラミング

9.1　抽象解釈

9.1.1　ルート計画

9.1.2　抽象化：符号の掛け算

9.1.3　安全と近似：符号の足し算

9.2　静的意味論

9.2.1　実装

9.2.2　利点と制限

9.3　応用

あとがき

監訳者あとがき

索引

#スクボ読書化した本