递归分析

扩展释义

递归分析（recursive analysis）以递归理论为工具解决有关问题的一种分析。由于数理逻辑的某些方面本身就不可避免地包含着可构造性和能行性概念，因此，递归理论正是为了适应逻辑研究的需要而产生的。例如哥德尔不完全性定理，就可以通过表明句子的可证性是递归可枚举性质，而句子的真理性却不是递归可枚举性质来加以证明。递归理论能用于分析判定问题。希尔伯特第十问题就是一个判定问题，它要求设计一种算法，以对任何给定的丢番都方程（即整系数多项式方程），判定其是否有整数解。通过递归分析，这一问题能得到否定的解答。递归分析还包括不可解问题及其不可解度，计算复杂性，能行描述集合论等多方面的研究。