Spiceだと埒が明かないので、件の回路の実験をソフトウェアで行ってみた。
残念ながら、中立点で閉塞するケースを発見してしまい、案の定バックトラックが必要な事態になった。プログラムを置いておく。
件の回路もどうせ-1と+1と0の３値しかないのでH,L,Xで探索している。
チューリングマシンに比べて計算オーダーは減っているのだが、O(2^n) のオーダーに準じていると思われ、非多項式時間問題に対する根本的なソリューションにはならないようだ。
後は、チューリングがボンベでやったように、計算中に発生する恒等ポイントを短絡したり、インバータでつないだりなど、論理圧縮しながら解探索という、それはそれで面白そうな遊びが考えられるが、枝狩りの効率化の範疇の可能性が高い。
逆に、NANDの組合せという汎用計算問題なので、閉塞条件やその仕組みの解明はP≠NP問題に対するアプローチにはなりうるかもしれない。
もう少し掘ってみよう。
夢が覚めてしまった(苦笑)。残念なような、ほっとした様な(汗)。
コメント