アナログ計算と複雑度

河村彰星．アナログ計算と複雑度．平成21年度夏のエルエーシンポジウム，発表番号5，東松島，平成21年7月22日．

河村彰星．アナログ計算と複雑度．「計算可能性問題における極限再帰関数の役割の多角的研究」セミナー，京都，平成21年7月29日．

エルエーシンポジウムでの資料.pdf（平成21年7月21日作成，A4判2頁）

京都での配布資料.pdf（平成21年7月21日作成，A4判8頁）

概要

物理現象は多く単純な微分方程式に従う．これを天然の計算機械と看做すとき，その能力や限界は如何なるものであろうか．このような「アナログ計算」の複雑度に関る研究について拙著

• Akitoshi Kawamura. Differential recursion. ACM Transactions on Compututational Logic 10(3), Article 22, April 2009.
• Akitoshi Kawamura. Lipschitz continuous ordinary differential equations are polynomial-space complete. In Proceedings of the 24th IEEE Conference on Computational Complexity (CCC 2009), Paris, France, July 2009.

を含め紹介する．

1. 微分解析機と汎用アナログ計算機
2. ムーアの実原始再帰函数
3. 微分方程式の解の計算複雑度