遞歸函數維基百科,自由的 encyclopedia 在數理邏輯和電腦科學中,遞歸函數或μ-遞歸函數是一類從自然數到自然數的函數。直覺上遞歸函數是"可計算的"。事實上在可計算性理論中已經證明了它確實是圖靈機的可計算函數。遞歸函數與原始遞歸函數相關,而且遞歸函數的歸納定義(見下)建立在原始遞歸函數之上。但不是所有遞歸函數都是原始遞歸函數——其中最著名的是阿克曼函數。 其他等價的函數類是λ-遞歸函數和馬爾可夫演算法可計算的函數。 所有遞歸函數的集合叫做R。
在數理邏輯和電腦科學中,遞歸函數或μ-遞歸函數是一類從自然數到自然數的函數。直覺上遞歸函數是"可計算的"。事實上在可計算性理論中已經證明了它確實是圖靈機的可計算函數。遞歸函數與原始遞歸函數相關,而且遞歸函數的歸納定義(見下)建立在原始遞歸函數之上。但不是所有遞歸函數都是原始遞歸函數——其中最著名的是阿克曼函數。 其他等價的函數類是λ-遞歸函數和馬爾可夫演算法可計算的函數。 所有遞歸函數的集合叫做R。