再帰理論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/12/24 16:20 UTC 版)
再帰理論（さいきりろん、英：Recursion theory）は、数理論理学の一分野で、1930年代の計算可能関数とチューリング次数の研究が源となっている。
- ^ 彼らの基本的な論文の多くは Martin Davis The Undecidable (1965) に集成されている。
- ^ Conference on Logic, Computability and Randomness, January 10–13, 2007.
- ^ The homepage of Andre Nies has a list of open problems in Kolmogorov complexity
- ^ 訳注：リンクは原文ママ。正しくは一階算術（ペアノ算術）とすべきかも知れない
- ^ MathSciNetで検索すると、"computably enumerable" や "c.e." といった文字列が題名にある論文が多数存在している（注:購読者以外は検索できない）。
- ^ Lance Fortnow, "Is it Recursive, Computable or Decidable?," 2004年2月15日、2006年1月9日参照。
- ^ Stephen G. Simpson, "What is computability theory?," FOM email list, 1998年8月24日、2006年1月9日参照。
- ^ Harvey Friedman, "Renaming recursion theory," FOM email list, 1998年8月28日、2006年1月9日参照。
再帰理論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/08 05:41 UTC 版)
詳細は「再帰理論」を参照 再帰理論（計算可能性理論とも呼ばれる）は計算可能関数とチューリング次数（これは計算不可能関数を同じレベルの計算不可能性を持つ集合に分ける）の性質を研究する。再帰理論はまた一般計算可能性と定義可能性の研究を含む。再帰理論はアロンゾ・チャーチとアラン・チューリングによる1930年代の仕事（これはクリーネとポストによって1940年代に大きく拡張された）から生まれた。 古典再帰理論は自然数から自然数への関数の計算可能性に着目する。基本的な結果は、チューリング機械やラムダ計算やその他のシステムなど、多数の独立だが同値な特徴づけを持つ、ロバストかつカノニカルな計算可能関数のクラスを確立したことである。より高度な結果はチューリング次数の構造や帰納的可算集合の成す束に関するものである。 一般再帰理論は再帰理論の諸概念をもはや有限ではないような計算へと拡張する。そこには高階の型の計算可能性の研究や超算術的理論（英語版）や&alpha-再帰理論（英語版）などの分野を同様に含む。 再帰理論の現代的研究には、純粋な再帰理論の新しい結果と同様に、その応用研究（例えばアルゴリズム的ランダムネス、計算可能モデル理論（英語版）、逆数学など）が含まれる。
※この「再帰理論」の解説は、「数理論理学」の解説の一部です。
「再帰理論」を含む「数理論理学」の記事については、「数理論理学」の概要を参照ください。
固有名詞の分類
- 再帰理論のページへのリンク
