枚舉定理（enumeration theorem）是2018年公布的計算機科學技術名詞。
基本介紹
- 中文名：枚舉定理
- 外文名：enumeration theorem
- 所屬學科：計算機科學技術
- 公布時間：2018年
定義,出處,
定義
如下定理：存在一個部分可計算二元函式 ，使對一切 e,x ，有φ (e,x)=(x) ，這裡 是編碼為 e 的圖靈機計算的函式。
出處
《計算機科學技術名詞 》 (第三版)。
枚舉定理
相關詞條
- 枚舉定理
枚舉定理（enumeration theorem）是2018年公布的計算機科學技術名詞。定義如下定理：存在一個部分可計算二元函式 ，使對一切 e,x ，有φ (e,x)=(x) ，這裡 是編碼為 e 的圖靈機計算的函式...
- 部分遞歸函式枚舉定理
稱為n元部分遞歸函式的部分遞歸枚舉或能行枚舉.枚舉定理可由克林範式定理直接推出.不僅如此，由克林謂詞T,:關於n的一致性，可以證明，存在全體部分遞歸函式的通用函式滬，即對任何值得指出的是，n元部分遞歸函式的部分遞歸枚舉並不惟一但是，遞歸論中關於部分遞歸函式的討論並不依賴於任何一種具體枚舉的特殊性質.因此...
- 算術枚舉定理
算術枚舉定理(arithmetical enumeration theo-rem)算術表示定理的推廣.其內容是:對任何n,m,1，存在m十1元乏。關係，使得該關係枚舉所有m元三關係.類似地，亦存在m十1元二。關係，使得該關係枚舉所有m元二，關係.算術枚舉定理是美國邏輯學家、數學家克林(Kleene, S. C.)與波蘭數學家莫斯托夫斯基(Mostowski, A.)...
- 解析枚舉定理
解析枚舉定理(analytical enumeration theo-rem)解析表示定理的推廣 其內容為:對任何n,m>1及L，存在習關係R,R具有m}-1個自然數變元、L個函式變元、R枚舉所有具有m個自然數變與L個函式變元的習關係.類地，將上面的定理中的酬換為n:,後定理仍然成立.這兩個定理統稱解析枚舉定理.解析枚舉定理是美國邏輯學家、...
- 枚舉法
（1）確定枚舉對象、枚舉範圍和判定條件；（2）枚舉可能的解，驗證是否是問題的解。結構 枚舉算法的一般結構：循環+判斷語句。首先考慮一個問題：將1到100之間的所有整數轉換為二進制數表示。算法一 for i:=1 to 100 do begin 將i轉換為二進制，採用不斷除以2，餘數即為轉換為2進制以後的結果。一直除商為0...
- 相對化枚舉定理
相對化枚舉定理 相對化枚舉定理（elativized enumeration theorem）是2018年公布的計算機科學技術名詞。 公布時間 2018年，經全國科學技術名詞審定委員會審定發布。出處 《計算機科學技術名詞 》 (第三版)。
- 計算可枚舉集的範式定理
計算可枚舉集的範式定理 計算可枚舉集的範式定理（normal form theorem for the computably enumerable sets）是2018年公布的計算機科學技術名詞。定義 定理如下：一個集合 A 是計算可枚舉的，若且唯若它是的。出處 《計算機科學技術名詞 》 (第三版)。
- 列舉定理
列舉定理 列舉定理是2018年公布的計算機科學技術名詞 。 定義 一個集合 A 是計算可枚舉的，若且唯若 A =, 或者 A 是某個可計算函式的值域。 出處 《計算機科學技術名詞 》。
- 計算可枚舉度的並定理
計算可枚舉度的並定理（join theorem for the computably enumerable Turing degrees）是2018年公布的計算機科學技術名詞。定義 對任意的非零計算可枚舉圖靈度 x ，存在計算可枚舉圖靈度 a 使得 a ″=( a ∨ x )′=0″，這裡 y′ 是 y 的圖靈躍變。出處 《計算機科學技術名詞 》第三版。
- 遞歸可枚舉語言
下列定理揭示了遞歸可枚舉語言和圖靈可識別語言的聯繫。定理：一個語言是圖靈可識別的，若且唯若它是遞歸可枚舉的。證明：若有枚舉器E枚舉語言S，構造一個圖靈機M如下：對於輸入ω 運行E，依次生成字元串s₁,s₂, ...；若遇到某個s= ω則進入接受狀態並停機。注意當ω ∉S時，M可能永不停機，但M所...
- 遞歸可枚舉集合
這也是遞歸可枚舉集合的常見定義。例子 所有遞歸集合都是遞歸可枚舉的，但不是所有遞歸可枚舉集合都是遞歸的。遞歸可枚舉語言是在形式語言的字母表上所有可能詞的集合中的遞歸可枚舉集合。Matiyasevich 定理聲稱所有丟番圖集合都是遞歸可枚舉的。簡單集合是遞歸可枚舉的但不是遞歸的。創造集合是遞歸可枚舉的但不是遞歸...
- 遞歸定理
對一個遞歸函式f，其不動點不僅存在，而且一定有無窮多個，它們所組成的集合可能是遞歸集，也可能是非遞歸的.值得指出的是，對部分遞歸函式，其不動點定理與第二遞歸定理是等價的，但兩者的證明所需要的基礎並不一樣.前者依賴於Sₘ定理和枚舉定理，而後者則僅依賴於Sₘ定理.因此，若一個函式類具有Sₘ性質...
- 弗里德堡-穆奇尼克定理
弗里德堡-穆奇尼克定理 弗里德堡–穆奇尼克定理（英語：Friedberg–Muchnik Theorem）是可計算性理論中關於不可解度的定理，聲稱存在一對互相不可計算的遞歸可枚舉不可解度。定理 存在遞歸可枚舉不可解度 A,B 互不可計算。相關定理 克萊尼–波斯特定理是較弱的定理，可由弗里德堡–穆奇尼克作為推論得出。
- 通用函式
通用函式定理亦稱枚舉定理。該定理指出：存在一個函式列 滿足下列條件：（1）對任何 e ，是 n 元部分遞歸函式；（2）若 為 n 元部分遞歸函式；（3）存在 n+1 元部分遞歸函式 ，使得對任何 上述的函式 被稱為 n 元部分遞歸函式的通用函式或枚舉函式(enumeration function)。遞歸函式 最早由哥德爾於1934年提出...
- 分層理論
在≥1的情形，恆存在一個枚舉類（或）的全體謂詞的枚舉謂詞。例如，對於和m==1而言,存在一個原始遞歸謂詞(,,,)，使得當任給一個一般遞歸謂詞(,,,)時，恆有自然數，使得 此即枚舉定理。在這個定理中，可將(,,,)取為屶(,,,)則有分層定理。分層定理 對每一≥0，都存在一個型（型）謂詞,它不能在其對...
- 描述集合論
(枚舉定理(enumeration theorem))。在這個定理中，我們可以把 取為 。對每個k≥0，都存在一個 (或 )謂詞，它不可在其對偶形式 ()中來表示(因此，當然不可能在 和 中來表示)（譜系定理（hierarchy theorem））。所以，上面的表(a)便是算術謂詞的譜系分類．這個譜系稱為算術譜系(arithmeticalhierarchy)。對每個k...
- 三次曲線
但如其一貫所為，牛頓遲疑於結果的發表，直到1695年，他才將以前的結果總結成專論《三次曲線枚舉》(Enumeratio linearum tertii ordinis)並作為《光學》的附錄發表(1704)。定理 兩條三次曲線有九個交點。 如果第三條三次曲線經過前兩條三次曲線的8個交點， 那么它也必定通過第九個交點。這就是著名的凱萊-...
- 相對解析分層
關於解析分層的其他性質，參見“解析枚舉定理”。此外，與算術分層不同，Δ¹₁≠Σ¹₀=π¹₀=Δ¹₀，Δ¹₁的關係稱為超算術關係。遞歸關係 遞歸關係是序列的項之間的一種關係。指序列的任一項均被其前若干項所確定的那種關係。對於數列{aₙ|n=0，1，2，…}，若當n≥0時，恆有關係...
- 下標系統
，衫”’一娜^' &c.＞樹”，一翰a則稱下標系滬為可接受的.美國數學家羅傑斯Rogers , H.證明了一個下標系必為可接受的，若且唯若必同時具枚舉性和可參數化性質，也若且唯若存在遞歸置換h，使對任何‘和n,召”’一袱打.對於一個可接受的下標系必來說，相應的枚舉定理、參數定理、遞歸定理、墊襯引理都...
- 圖靈可識別語言
下列定理揭示了遞歸可枚舉語言和圖靈可識別語言的聯繫。定理：一個語言是圖靈可識別的，若且唯若它是遞歸可枚舉的。證明：若有枚舉器E枚舉語言S，構造一個圖靈機M如下：M= 對於輸入ω 運行E，依次生成字元串s₁,s₂, ...；若遇到某個s= ω則進入接受狀態並停機。注意當ω ∉S時，M可能永不停機，但M...
- 可接受配數
可接受配數是2018年全國科學技術名詞審定委員會公布的計算機科學技術名詞。定義 給定一切部分可計算一元函式的枚舉（*），如果：① 每一個函式，如果在（*）中出現，則它在（*）中出現無窮次；而且②（*）滿足 s－m－n 定理，那么稱它是一個可接受配數。出處 《計算機科學技術名詞 》第三版。公布時間 2018年...
- 論證方法
運用講道理的方法，用經典著作中的精闢見解、古今中外名人名言及被人們公認的科學原理、定理、公式等來證明觀點。例如《談讀書》（人教版九上課文）第十段列舉“讀史使人明智，讀詩使人聰慧，演算使人思維精密，哲理使人思想深刻，倫理學使人有思想，邏輯修辭使人善辨”這六門科學知識的作用進行論證，歸納出“知識...
- 組合最最佳化
定理1 一個匹配為最大匹配的充要條件是不存在關於它的增廣鏈。如何尋找增廣鏈?採用“樹生長法”(或稱標號法)，以圖2為例，開始任取一未蓋點為樹根，如D，從樹根沿著細線生長，接著從樹梢出發沿著粗線往外生長，這樣交錯地沿著細線和粗線繼續從樹梢往外延伸，直到不能再生長(如圖4)。稱圖4是以D為根的交錯...
- 邏輯學是什麼(第3版)
8.6 定理證明 第9章 謂詞邏輯 9.1 謂詞和量詞 9.2 無效性證明 9.3 構造證明 9.4 量化否定，RAA和CP 第10章 歸納 10.1 歸納和演繹：比較與分類 .10.2 訴諸權威論證和枚舉歸納 10.3 密爾法和科學推理 10.4 訴諸類比的論證 第11章 機率 11.1 機率的三種理論 11.2 機率的規則 習題解答 譯後記 ...
- 類比(詞語)
近代的科學發展使人們認識到，單靠某一事物與已知事物之間的簡單的靜態的性質類比，那是很不充分的，還需要從事物性質的量上進行研究，這就需要把定性類比和定量類比結合起來，例如，歐姆把電流的傳導同傅利葉的熱傳導定理相類比。在熱傳導中，溫差（ΔT），熱量（Q）和物體的比熱（c）歐姆把熱量和溫差的協變關係...
- 組合論(以其個數的計算為主要目標)
幾何組合與凸和離散幾何有關，特別是多面體組合。例如，它詢問多少個凸多面體可以具有多少個面。多面體的度量性質也起著重要的作用，例如關於凸多面體剛度的Cauchy定理。也考慮特殊的多面體，如permutohedra，associahedra和Birkhoff多形體。我們應該注意到組合幾何對於離散幾何來說是一個老式的名字。拓撲組合 概念和拓撲方法...
- 邏輯的力量(第3版)
8.6 定理證明 .第9章 歸納 9.1 歸納和演繹：比較與分類 .9.2 訴諸權威論證和枚舉歸納 9.3 密爾法和科學推理 9.4 訴諸類比的論證 部分練習題解答 作者簡介 史蒂芬·雷曼（C. Stephen Layman）是西雅圖太平洋大學哲學系主任，1983年博士畢業於加州大學洛杉磯分校。他的研究領域為宗教哲學、倫理哲學和邏輯哲學。...
- 高等院校通信與信息專業規劃教材·數字邏輯
2.2 邏輯代數的定理和規則 2.2.1 邏輯代數的基本定律 2.2.2 常用公式 2.2.3 展開定理 2.2.4 邏輯代數的三個規則 2.3 邏輯函式的標準表達式 2.3.1 標準"與或"式 2.3.2 標準"或與"式 2.3.3 不完全確定的邏輯函式 2.4 邏輯函式的化簡方法 2.4.1 邏輯函式式的化簡目標 2.4.2 代數化簡法...
- 數字邏輯設計與VHDL描述(第2版)
2. 2 邏輯代數的定理和規則 2. 2. 1 邏輯代數的基本定律 2. 2. 2 常用公式 2. 2. 3 展開定理 2. 2. 4 邏輯代數的三個規則 2. 3 邏輯函式的標準表達式 2. 3. 1 標準與或式 2. 3. 2 標準或與式 2. 3. 3 不完全確定的邏輯函式 2. 4 邏輯函式的化簡方法 2. 4. 1 邏輯函式式的化簡...
