2008年7月14日月曜日

3 not problem

私が3notの話を最初に聞いたのは, 1960年代の始め頃, サバティカルで東大に滞在していたイリノイ大学のDavid Muller先生からだ. 研究室のお茶の時間に「アメリカの計算機科学科でよく話題になる問題」の1つとして紹介された.

この話が記述されているのはあまり見た記憶がないが 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 件のコメント:

Kenji Rikitake さんのコメント...

このへんに回答例がありますね.

http://sci.tech-archive.net/Archive/sci.math/2004-06/5683.html

http://sci.tech-archive.net/Archive/sci.math/2004-06/5730.html