遞歸等價(recursive equivalence)遞歸論的基本概念之一指自然數集在遞歸意義下的等價關係.若A,B為自然數集，並且存在一一的部分遞歸函式筍，使得ACdom rp，並且抓(A)=B，則稱A,B遞歸等價.由遞歸等價關係定義的(自然數集的)等價類，稱為遞歸等價型.遞歸等價關係類似於集合論中的等勢關係.遞歸等價型則類似於集合論中的基數概念.遞歸等價關係的概念是德克爾(Dekker,J.)於1955年引人的.
遞歸等價(recursive equivalence)遞歸論的基本概念之一指自然數集在遞歸意義下的等價關係.若A,B為自然數集，並且存在一一的部分遞歸函式筍，使得ACdom rp，並且抓(A)=B，則稱A,B遞歸等價.由遞歸等價關係定義的(自然數集的)等價類，稱為遞歸等價型.遞歸等價關係類似於集合論中的等勢關係.遞歸等價型則類似於集合論中的基數概念.遞歸等價關係的概念是德克爾(Dekker,J.)於1955年引人的.
遞歸等價(recursive equivalence)遞歸論的基本概念之一指自然數集在遞歸意義下的等價關係.若A,B為自然數集，並且存在一一的部分遞歸函式筍，使得ACdom rp，並且抓(A)=B，則稱A,B遞歸等價....
發現：f(n)=qⁿ滿足斐波那契遞歸關係若且唯若qⁿ=q+q，或對於n=2，3，4，…有q(q²-q-1)=0。因為假設q≠0，所以得到f(n)=qⁿ是斐波那契遞歸關係的一個解若且唯若q²-q-1=0，或等價地講，若且唯若q是二次...
為部分遞歸函式，則存在e，使得 。與第二遞歸定理等價的是下列不動點定理：對任何遞歸函式f，存在自然數n(稱為f的不動點)，使φₙ=φ。不動點定理有一些推廣的形式：帶參數的遞歸定理。若f為n+1元遞歸函式，則存在一一的n元...
尾部遞歸是指遞歸函式在調用自身後直接傳回其值，而不對其再加運算。尾部遞歸與循環是等價的，而且在一些語言（如Scheme中）可以被最佳化為循環指令。 因此，在這些語言中尾部遞歸不會占用調用堆疊空間。以下Scheme程式同樣計算一個數字的階乘...
遞歸語言有兩種等價的主要定義：遞歸語言是在形式語言的字母表上的所有可能的字的集合的遞歸子集。設S⊆ Σ是一個語言，M是一台圖靈機， 若對於任何字元串 ω ∈ Σ，有 ω ∈S若且唯若M接受 ω ω ∉S若且唯若M拒絕 ω ...
其他等價的函式類是λ-遞歸函式和馬爾可夫算法可計算的函式。一個直接的例子 條件 一個含直接或間接調用本函式語句的函式被稱之為遞歸函式，在上面的例子中能夠看出，它必須滿足以下兩個條件：1） 在每一次調用自己時，必須是（在某種...
一般遞歸式通常寫為：其中，為歸宿於零的函式，即從任何一值(作為第一變元)經過有限次迭置之後 的值必為零。摹狀式一般寫為：但要求對任何 都有 使得 其中，表示滿足(1)的最小自然數 。已經證明這兩個定義是等價的。邱吉建議把...
遞歸同構 遞歸同構是一個數學術語。 遞歸同構(recursively isomorphism)自然數集在遞歸置換意義下的等價關係.對自然數集A,B，若存在遞歸置換P，使得P
遞歸神經網路（recursive neural network）提出於1990年，被視為循環神經網路（recurrent neural network）的推廣。當遞歸神經網路的每個父節點都僅與一個子節點連線時，其結構等價於全連線的循環神經網路。遞歸神經網路可以引入門控機制（...
等價於3是奇數?，依次等價於2是偶數?，直到0. 這個例子是相互單遞歸，很容易改寫為疊代。這個例子中的互遞歸是尾調用，尾調用最佳化是必須的以能在常量大小棧空間完成計算。C語言這要求O(n)棧空間，除非重寫用跳轉代替調用。對於樹，...
”良序化定理作為選擇公理的一個等價命題，是集合論中的一個重要定理。可構造序數 可構造序數是一種特殊的序數。α為可構造序數，是指存在一個記號系統S，使得S中有α的記號。可構造序數都是可數序數，可構造序數的全體構成序數的一個...
這裡，丘奇把算法可計算性與遞歸性之間的這種等價稱為“定義”，波斯特(E.Post)1936年曾極力反對定義的提法，認為應當僅僅作為一種工作假說看待 。1943年克林尼指出，描述這種等價性的命題包含了很強的工作假說的特徵，儘管我們確有不得...
產遞歸函式恰好為HU可計算函式，它們都是直觀上能行可計算的函式，在上述定義中，若允許部分函式，便得到部分遞歸函式.此外，只要在上述定義中 由克林足義的產遞歸函式.簡稱遞歸函式.遞歸函式有許多種等價定義形式:埃爾布朗一哥德爾一般...
這導致數學家和計算機科學家相信可計算性的概念可由上述三種等價的計算過程描述。簡單來講，邱奇-圖靈論題認為如果某種方法（算法）可進行運算，那么該運算也可被圖靈機執行（也可被遞歸定義的函式或λ函式執行）。邱奇-圖靈論題是對計算...
，aₙ)形的關係，其中R為遞歸關係，Q₁，Q₂，…，Qₙ為一階量詞∃或ᗄ。基本介紹 算術關係是可以通過對遞歸關係添加有窮個量詞定義的關係，即可以表示 形的關係，其中R為遞歸關係，為一階量詞∃或ᗄ。等價地，算術...
的關係式。此外，以下的條件也可以被驗證是與之等價的：純數數列 {cₙ}ₙ滿足c₀≠0，並且 純數數列 {cₙ}ₙ滿足c₀≠0，並且 其中 對所有的n= 0, 1, 2, ...,遞歸公式 假設 其中後一個等式是在以x為不定元的...
n- re度(n-re degree)遞歸論的基本概念之一指包含n-r‘集的度.若n＞1，且n-re度a中不包含(n - 1)-re度，則稱a為真n-re度.n-r。度與d-re度有許多類似之處，已知的d-re度的結論在-re度中皆成立.因此，一個很重要...
上述計算模型等價性的證明， 主要採用將一種模型用另一種模型表示的方法證明。 可計算理論中，計算模型很多, 如有窮自動機, 正則算法在本質上都與圖靈機相似。 Church-Turing 論題指出： 通常說的能行可計算函式等同於部分遞歸函式, ...
，用某種數學方法導出等價的形式 ，然後按以下步驟執行：1、選一個方程的近似根，賦給變數 ；2、將 的值保存於變數 ，然後計算 ，並將結果存於變數 ；3、當 與 的差的絕對值還小於指定的精度要求時，重複步驟2的計算。
2.遞歸 遞歸是設計和描述算法的一種有力的工具，由於它在複雜算法的描述中被經常採用，為此在進一步介紹其他算法設計方法之前先討論它。能採用遞歸描述的算法通常有這樣的特徵：為求解規模為N的問題，設法將它分解成規模較小的問題，然後...
斯普萊格–格隆第定理指出：每個無偏博弈等價於一個特定大小的尼姆堆。尼姆數的加法運算（叫做尼姆加法）可以用於計算等價於多個堆的單一尼姆堆大小。對於序數的集合S，mex(S)定義為“局外最小序數”，也就是說序數中不是S的元素的最小...
cultural equivalence 文化對等譯法 ; 文化對等 ; 文化等值 ; 文化等價 Textual Equivalence 語篇對等 ; 篇章等值 ; 文本等值 ; 行文對等 recursive equivalence 遞歸等價性 style equivalence 風格等值 ; 風格對等 雙語例句 This irref...
由於循環和遞歸的程式相似的原因，證明帶有不變數的循環的部分正確性和證明通過歸納的遞歸程式的正確性極其相似。事實上，循環不變數通常是一個遞歸程式可以等價為一個給定循環的遞歸的屬性。霍爾邏輯 在弗洛伊德-霍爾邏輯，While循環的部分...
1933～1936年A.丘奇 (1903～ )和S.C.克利尼 (1909～ )構造了λ可定義演算，證明了λ可定義性和一般遞歸的等價關係。1936年丘奇提出能行可計算函式即是遞歸函式或λ可定義函式的論題。1936年也出現了E.波斯特（1897～1954）的...