遞歸分析

遞歸分析（recursive analysis）是以遞歸理論為工具解決有關問題的一種分析。

基本介紹

• 中文名：遞歸分析
• 外文名：recursive analysis
• 工具：遞歸理論
• 目的：適應邏輯研究的需要
• 定義：以遞歸理論為工具解決有關問題的一種分析

由於數理邏輯的某些方面本身就不可避免地包含著可構造性和能行性概念，因此，遞歸理論正是為了適應邏輯研究的需要而產生的。例如哥德爾不完全性定理，就可以通過表明句子的可證性是遞歸可枚舉性質，而句子的真理性卻不是遞歸可枚舉性質來加以證明。遞歸理論能用於分析判定問題。希爾伯特第十問題就是一個判定問題，它要求設計一種算法，以對任何給定的丟番都方程（即整係數多項式方程），判定其是否有整數解。通過遞歸分析，這一問題能得到否定的解答。遞歸分析還包括不可解問題及其不可解度，計算複雜性，能行描述集合論等多方面的研究。