遞歸等價(recursive equivalence)遞歸論的基本概念之一指自然數集在遞歸意義下的等價關係.若A,B為自然數集，並且存在一一的部分遞歸函式筍，使得ACdom rp，並且抓A)=B，則稱A,B遞歸等價.由遞歸等價關係定義的(自然數集的)等價類，稱為遞歸等價型.遞歸等價關係類似於集合論中的等勢關係.遞歸等價型則類似於集合論中的基數概念.遞歸等價關係的概念是德克爾(Dekker,J.)於1955年引人的.
遞歸等價(recursive equivalence)遞歸論的基本概念之一指自然數集在遞歸意義下的等價關係.若A,B為自然數集,並且存在一一的部分遞歸函式筍,使得ACdom rp,並且抓A)...
遞歸定理(recursion theorem)亦稱不動點定理。反映部分遞歸函式類基本性質的重要定理。最初是由美國邏輯學家、數學家克林(Kleene, S. C.)於1938年證明的,克林所...
一般遞歸函式(general recursive function)亦稱遞歸函式,是指一類具有能行可計算的全數論函式。不僅如此,現在一般認為,能行可計算的全數論函式恰好就是一般遞歸函式,...
遞歸算法(英語:recursion algorithm)在計算機科學中是指一種通過重複將問題分解為同類的子問題而解決問題的方法。遞歸式方法可以被用於解決很多的計算機科學問題,因此它...
在數學、邏輯和計算機科學中,遞歸語言或遞迴語言是也叫做可判定語言或圖靈可判定語言的形式語言類型。所有遞歸語言的類經常被稱為 R。這種語言類型在喬姆斯基層級中...
Church-Turing 論題指出: 通常說的能行可計算函式等同於部分遞歸函式, 也等同於Turing 機計算的部分函式; 也就是說, Turing 機可計算性與遞歸性是等價的。 ...
由於循環和遞歸的程式相似的原因,證明帶有不變數的循環的部分正確性和證明通過歸納的遞歸程式的正確性極其相似。事實上,循環不變數通常是一個遞歸程式可以等價為一個...