SICP問題1.45の回答と説明（SICP1.3.4, ex1.45）

この記事の対象読者：『計算機プログラムの構造と解釈』を読んだことがあって、問題1.45に納得がいってないひと



1.3.4 値として返される手続き （計算機プログラムの構造と解釈 第二版）

SICPの読んでたときにけっこう苦労した練習問題。
n乗根を求めるための平均緩和法の適用回数を「実験して確かめよ」って書いてあるけど、たぶん実験だけでは分からない。回答自体はカンニング（検索）して見つけたけど、なぜそうなのかをちゃんと説明しているのを見つけられなかったので、この記事で説明してみる。

平均緩和法、不動点探索の復習

回答のまえに平均緩和法や不動点探索についておさらいしておきます。

『コンピュータシステムの理論と実装』第5章 CPUを作ったよ

個人的に進めてる『コンピュータシステムの理論と実装』の実装メモを書きますよ。
今回はCPUを作るのが山場でした。

「第5章　コンピュータアーキテクチャ」ではHackコンピュータというこの本オリジナルのコンピュータを作ります。前章まででALU、レジスタやプログラムカウンタなんかは作ってあるので、それらを組合せてなんとかします。

命令メモリ、CPU、データメモリを合体させるとHackコンピュータになるらしい（P.105、5.3.3）。メモリは前章のRAMを利用すればすぐ作れるので、問題はCPUを作ることです。


P.102に概略図が載ってるのでそのとおりに作るんですが、詳細が省かれてるので実際にHDLで書こうとすると大変でした。この本は実践に重きを置いているので、詳細を省いているのはたぶん意図的です。実装を通じて学んで欲しいということでしょう。

下に私の考えた実装コードを載せますけど、本の思想に忠実に自分で考えたいというひとはネタバレ注意です。（GW中にやったけどハマった部分があって3日ぐらいかかってしまったｗ）

AND、ORだけではNOT回路は作れないのか

「コンピュータシステムの理論と実装」読書会のときの疑問を追っかけて考えてみました。

NotとAnd／Orからならすべての論理回路が作れることは分かりました。ではAnd、OrのみからNot回路は作れないのでしょうか？
直感的に「作れない」って感じるんですが、きちんと論理的に説明するのはけっこう難しい気がします。

ではどうやったら説明できるか。

Notは１入力１出力の回路です。まずは入力をaとおきます。最初の入力の可能性としてはa、定数0、定数1のどれかしかありません。
最初の入力から次の出力の可能性は次の表の通りです。やっぱりa,0,1のどれかになってしまいます。

入力１	入力２	And出力	Or出力
a	0	0	a
a	1	a	1
a	a	a	a
0	0	0	0
0	1	0	1
1	1	1	1

つぎに1出力ってことを考えます。And、Orのみで回路を作るならケーブルをまとめる最後の素子はAndまたはOrのどっちかになります。そして回路の最初の入力も次の出力もa,0,1になってるので、最後の出力もやっぱりa,0,1になってしまう。
雑に図解するとこんな感じ。

途中の回路がどんな複雑でもAnd／Orのみなら中間出力も変わらないので、最後の論理素子の入力も変わらない。だから最後までNot aを作ることはできない。


……という説明を考えてみたけど、なんだかすっきりしない。背理法か何かでさっぱりと証明する方法はないのかなー。




追記：ツイートしたら@chiralさんが速攻で返信くれました。だいぶすっきりした！

@deltam それを実現する段数が最小の回路をXとしましょう。いま、出力が1だとすると、出力の手前の素子Yへの入力は(Xの段数最小性より)全てゼロのはずです。するとYがANDでもORでも入力が全てゼロなら出力は決して1にならないので矛盾。 Q.E.D.

— ITコンサルタント (@chiral) 2015, 4月 19

#nandris コンピュータシステムの理論と実装 読書会(2) に参加してきました

「コンピュータシステムの理論と実装」は論理回路から順を追ってコンピュータの仕組みを知ろうという教科書です。
Nand回路から初めて論理回路、加算器から機械語、OSや高級言語のコンパイラを経てテトリスを作っちゃおうという、デアゴスティーニでやりそうな構成。

この本の内容はNand2Tetrisというオンライン学習コースで、私はこのTED Talksで知りました。