Spiceだと埒が明かないので、件の回路の実験をソフトウェアで行ってみた。
残念ながら、中立点で閉塞するケースを発見してしまい、案の定バックトラックが必要な事態になった。プログラムを置いておく。
件の回路もどうせ-1と+1と0の３値しかないのでH,L,Xで探索している。
チューリングマシンに比べて計算オーダーは減っているのだが、O(2^n) のオーダーに準じていると思われ、NPに対する根本的なソリューションにはならないようだ。
後は、チューリングがボンベでやったように、計算中に発生する恒等ポイントを短絡したり、インバータでつないだりなど、論理圧縮しながら解探索という、それはそれで面白そうな遊びが考えられるが、枝狩りの効率化の範疇の可能性が高い。
逆に、NANDの組合せという汎用計算問題なので、閉塞条件やその仕組みの解明はP≠NP問題に対するアプローチにはなりうるかもしれない。
もう少し掘ってみよう。
夢が覚めてしまった(苦笑)。残念なような、ほっとした様な(汗)。
理想ダイオードに近い回路の実現に難儀している。
普通のダイオードモデルだと降下電圧などが問題になるからだ。
順方向に電位差がある場合のみ、信号の強弱によって干渉して、逆方向に電位差がある場合は互いに干渉にないという素子を作りたい。
コンパレータ＋スイッチというのが理想的であるし実際に作れるのだが、Spiceだとスイッチが各種のabortを引き起こしてしまう。
OPアンプを用いて作る理想ダイオードの回路をこちらなどで見かけた。
http://www.nahitech.com/nahitafu/mame/mame3/ideald.html
これを例によって自己回帰ループを組めば、良いはずなのだが、この回路自体
理想OPアンプでシミュレーションすると、負帰還がないので逆方向電位差の場合に-∞Vに発散してしまい(実OPアンプは電源電圧でクリップされるので無問題)シミュレーションがめんどくさくなる。
もともとシミュレーションでabortしないように各所に余計な抵抗をいれて理想OPアンプからは特性をずらして実験しているので、いっそうのこと実OPアンプのモデルで実験しようかとも考えている。
LTSpice がフリーで公開されているので、これを勉強中。
全加算器が動いたので添付しておく。
「nand3.cir」をダウンロード
"Timestep too small" のエラーを回避するために、スイッチなどを緩やかに設定しているし、テンションを掛けるための信号も正弦波に変えた。より現実的な装置に近づいている。
加算結果の方をまずStrongで固定した後、入力に当たる側を真/偽それぞれにweekに振って振り切れたらそこでStrongにKeepする回路を追加した。
図のとおり順に固定されていく。
図はひとつだけ張ったが、解を 10 とした場合、入力はキャリーIN含めて3つの入力は (1,1,0), (1,0,1), (0,1,1)の３つをとりうるが、探索順序を変えることでそれぞれの結果を得ることが出来た。
出力を固定した時点で入力側は、取りうる３つの解以外は取れないが、解の中では自由遷移できる(遷移間にポテンシャルの壁がない)ので、各方向に力を掛けて、デジタル値として有意なところに落とし込めばよい。どちらの方向に力を掛けるかで解が順にセレクトできる。
イメージとしては、出力側をロックした後、入力側に順に上下にテンションを掛けていって固定していくというやり方で、なんか古いシリンダー錠のピッキングに非常に似ているような(苦笑)。
シミュレータの使いこなしに苦戦している。
いつ、乗算器にたどり着けるやら(汗)。
いわゆる「２入力１出力」な論理素子を考えた場合。入出力で３つの値があり、入力が４パターンあるわけで、それぞれをXYZ空間にマップした場合、立方体の8頂点のうちの任意の4点の選択という問題に帰着する。
この場合、三角錐と方形の２パターンしかない。方形の場合に砂時計型にならないように注意だけすれば（XORなどで注意）、必ず各点を結んでできる空間は凸多面体(平面も含めて)になる。
ということは、つまるところ、電子スイッチはもちろん、歯車も、火計算機も、水計算機も、うっかり一方向論理素子でコンピュータを実装してしまった為に、OneWayファンクションなどというものが出来てしまっただけで、、、、
断っておくが、一般に言うP≠NP問題とは違う話である(面白い切り口にはなるかもしれないが)。
チューリングマシンの計算オーダーで、クラスNPに属する問題は多数あるが、これを非チューリングマシンでPの計算オーダーで解く事は可能である。
たとえば量子コンピュータがそうであるし、当のチューリング自身がチューリングボンベでエニグマを解読する際に示している。
チューリングマシン自体は「計算する」ということの範疇を定義するためのモデルでありそれ以上でも以下でもない。
たとえば素因数分解はクラスNPに属する。
ここで、件のNAND恒等回路で乗算器を組むことを考える。
A*B=C の回路において、まずCの部分の各端子を+1 or -1 で固定します（ここでテンション掛けてもその値に出来なければそれは素数）。
この段階でこの回路は、乗算結果がそうなる値の集合の範疇でしか遷移不能になる。
先の記事で示したとおり、各解の集合間での遷移はスムーズに進行する。
Nbit桁の乗算の場合、O(N)のオーダーで一つ目の解の探索が完了する。
量子コンピュータに比べて対応する記憶素子が無いなどのデメリットもあるが、この回路は現在のCMOSプロセスで容易に構成可能である点はメリットであるであろう。
P≠NPの仮定の基、各種の暗号の安全性も担保されているわけだが、まあ世の中には既にどこかにこの手の装置は実用化されていそうな気がする。
殆ど説明なく書き殴ってしまっているので一度整理しておく。
件の遊星歯車を使ったギアもOPアンプ回路もアナログ的には
A+B+C+D=0
A+D≦0
B+D≦0
-1≦A≦+1, -1≦B≦+1, -1≦C≦+1, -1≦D≦+1
という不等式を恒に満たす。
ここで一度デジタルな視点で、A～Cが 真(+1)、偽(-1) のどちらかの値しか取れないとすると論理式として
C = !(A・B)
という所謂NAND論理が成立する。
NAND論理がとり得る値の集合は
(A,B,C) = {(-1, -1, +1), (-1, +1, +1), (+1, -1, +1), (+1, +1, -1)}
の４パターンである。
ここで、再び初期の不等式でアナログ的に考えた場合、この４パターン間のそれぞれの遷移においてA,B,Cのうち何れかの値を固定したまま２値の連続変化による遷移が可能である。
即ちこのロジックの組合せで作った計算機械はデッドロックする恐れがない。
一方で、たとえばXORを数式で安直に表した場合
|A-B| - 2C = 0
という式が思いつく。
これには罠があり、
(A, B, C) = {(-1, -1, +1), (-1, +1, -1), (+1, -1, -1), (+1, +1, -1)}
の関係のうち
(-1, +1, -1) ⇔ (+1, -1, -1) の遷移で、Cを-1に固定したままABが入れ替わることが出来ない。
|A-B| - 2C = 0 を満たす回路は作成可能だが、もしこのような回路を作った場合、欲しい解に収束しない可能性がある。
では、先のNAND式の組合せでXORを作るとどうなるかであるが、ここで面白いことが起こる。
NAND式にはDという自由変数が組み込まれているが、これが所謂「遊び」となり、値間の遷移でポテンシャルの壁を作らない。変わりにA,B,Cは A≦0 とかの領域としての束縛のみを受ける。この領域がデジタル的な解を限定しつつも、恒常的に凸多角形を壊さないため局解にデッドロックすることなく計算が進行する。
いきなりでかい回路を書いてみたらわけわからなくなってきたので、懸念だったXORを組んでみた。
いあ、もともと回路がアレなのですぐAbortしてしまい、原理が確認できる範囲で抵抗を挟んで騙し騙しシミュレーションしているので、大きくなるとその按配が難しい。
XORはおおむね動いているように見えるのだが、全端子をHに引っ張った場合の逆算のみしくじっている。対称性が失われている時点で原理以前に何かがおかしい。記述ミスっぽいなぁ。
PSpiceの体験版のパーツ数制約で止まっていた、NAND恒等式ネタをNGSPICEでやってみた。
OPアンプでNANDっぽい動きができた。理想ダイオードを使ってしまったが、それに近い等価化回路は、ダイオードを使わなくとも作れるはずなので(コンパレータとアナログスイッチとか)まあこの段階ではよしとしよう。
[2016.05.29 追記]
この記事はブログ始める前の
とかの続きネタです（今更ですが）。
