■

study

ボストンへの手紙

直交の場合はOK (もう少し計算が必要だけど). 関数空間やら関数同士の内積がイメージ出来るようになったのでもうちょっと計算を続ける予定.
Rigui Zhou "Quantum Probability Distribution Network"っての見つけて名前受けしたのでメモ.

S. A. Kurtz, J. Simon "The Undecidability of the Generalized Collatz Problem" (TAMC 2007)

Collatzの関数 k(x)= x/2 (x:偶数) or 3x+1 (x:奇数)を一般化してみる.
整数mを持ってきて非負有理数の組の集合 (a_i,b_i)_{i=1,...,m}を持ってきて, g(x)=a_i x + b_i (if x \equiv i \bmod m)とする. で一般化コラッツ問題を

入力
(a_i,b_i)_{i=1,...,m}
出力
入力として任意の整数xについて必ず有限回gを適用することで1になるかどうか

と定義する.
Conwayが一般化コラッツ問題の特殊な形 (語弊がある) が\Pi_2^0完全であることを示している ("Fractran, a simple universal computing language for arithmetic" (Open Problems in Communication and Computation, 1987)).
彼らはうまい方法を思いついたらしく, 一般化コラッツ問題そのもが\Pi_2^0完全であることを示している.

というところまではわかったが, そもそも\Pi_2^0完全って何やねん. \Pi_2^Pとかなら分るんだが.
中で出てきたMinskyのcounter machineの話は面白そうだった. 内部はカウンターのみ. 操作はインクリメント, デクリメント, 停止のみ. しかもカウンターは二つあれば十分. でこのcounter machineの停止性判定問題を一般化コラッツ問題に上手く帰着させるらしい.