微分再帰の諸性質

Akitoshi Kawamura. Differential recursion. ACM Trans. Comput. Logic 10(3), Article 22 (April 2009), 22 pages. DOI = 10.1145/1507244.1507252

本文

校正前の版.pdf（英文，レター判20頁）

ACMによる正版はこちら

摘要

（非公式の邦訳です　正版は英文頁を御覧下さい）

通常の再帰函数の定義に倣ってC.ムーア氏が平成8年（1996, Theoret. Comput. Sci. 162）に創めた「再帰的」実数値函数の理論はアナログ計算の研究に一新期を劃した．しかし原論文には若干の誤りがある．本稿ではこれを匡すべく，部分函数に対する各演算子の振舞を曖昧なく定める方法幾つかを検討し，得られる函数類，就中微分方程式を解く演算子が生成する「原始再帰的」実函数の性質を調べる．適当な定義の下で，原始再帰的実函数は解析的であり，且つ伝統的な再帰理論に則した或る意味において可計算であることが判る．他方原論文の主張のうち微分代数函数ないしC. E.シャノン氏の汎用アナログ計算機との関係は崩れることを，ガンマ函数を用いた反例を以て示す．故にムーア氏の函数類をアナログ計算の模型とする従来の見方は再考を要する．

語句

アナログ計算（analog computation）

実再帰函数（real recursive functions）

初期値問題（initial value problems）

超超越函数（transcendentally transcendental functions，hypertranscendental functions）

微分代数函数（differentially algebraic functions）

関連資料

短い邦文の内容紹介をこちらに書きました

古い版

以下の発表の内容はすべて含んでおりますので　引用は上掲論文へお願い致します

• Differential recursion and differentially algebraic functions平成19年3月
• Rebuilding Moore's real recursion theory平成19年1月
• Type-2 Computability and Moore's Recursive Functions平成17年1月