実数計算と複雑性
Real number computation and dynamical systems
生成分割により導入される記号力学をTuring machineの計算過程ととらえることにより、計算理論と力学系理論の関係が明らかになります。Mooreらは区分線形な二次元写像の記号力学に万能Turing機械を埋め込んで、その決定不能性を示しました[1]。例えば三次元の古典ビリアード系でこういった系を構成できます。L. Blumらは実数計算のモデルであるBlum-Shub-Smale machineを与えて、Julia集合の複雑さを評価しました[2]。これらは古典計算理論[3]に対峙する、力学系的視点に基づく計算理論の研究といえます。この分野には未解決の問題が多数存在します。
[1] C. Moore, Phys. Rev. Lett., 64, p2354–2357, (1990);C. Moore, 1991 Nonlinearity, 4, p199, (1991).
[2] L. Blum, M. Shub, and S. Smale, Bull. Amer. Math. Soc., 21(1), p1, (1989); L. Blum, F.Cucker, M. Shub, S. Smale, "Complexity and Real Computation," Springer, (1997).
[3] A. M. Turing, Proc. London Math. Soc., 2-42, p230, (1936);
M. B. Pour-El, J. I. Richards, "Computability in Analysis and Physics," Springer, (1989).
