この話が記述されているのはあまり見た記憶がないが MITのHakmemには出ている. item 19の2-NOTs problemがそれである.
x,y,zの3入力, x',y',z'の3出力を持つブラックボックスがある. 入出力の関係は
x'=not x
y'=not y
z'=not z
である. ブラックボックスには, andとorは好きなだけ使われているが, notは2つしかないことが分かっている. 内部はどうなっているか.
Muller先生からこの話を聞いたわれわれは, その日は他の仕事がまったく手につかなかった. 解けてみるとなるほどと目から鱗の問題であった. 要は3は2ビットで表現できるということ.
Marvin Minsky先生の「Computation: finite and infinite machines」には閾値素子によるヒントが書いてある. 最近こういう話題は流行らないみたいで残念だ.
1 件のコメント:
このへんに回答例がありますね.
http://sci.tech-archive.net/Archive/sci.math/2004-06/5683.html
http://sci.tech-archive.net/Archive/sci.math/2004-06/5730.html
コメントを投稿