比浏览器更快的访问！
7 关系: 形式语言，ELEMENTARY，迭代冪次，阿克曼函數，递归可枚举集合，R (複雜度)，RE (複雜度)。
形式语言
在数学、逻辑和计算机科学中，形式语言（Formal language）是用精确的数学或机器可处理的公式定义的语言。 如语言学中语言一样，形式语言一般有两个方面: 语法和语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论，它只研究语言的语法而不致力于它的语义。在形式语言理论中，形式语言是一个字母表上的某些有限长字符串的集合。一个形式语言可以包含无限多个字符串。.
新！!: PR (複雜度)和形式语言 · 查看更多 »
ELEMENTARY
在計算複雜度理論裡面，複雜度類ELEMENTARY是所有指數譜系裡面的複雜度類聯集： 這名稱最早是為了探討可計算函數和不可判定問題，由László Kalmár所提出；most problems in it are far from elementary。Some natural recursive problems lie outside ELEMENTARY, and are thus NONELEMENTARY。相當值得注意的，有一些原始遞歸函數問題不在ELEMENTARY內。我們已知： LOWER-ELEMENTARY \subsetneq EXPTIME \subsetneq ELEMENTARY \subsetneq PR 與ELEMENTARY僅包含有限的冪（例如，O(2^)）比較，PR使用的 超運算更一般化（例如，tetration），因此PR不包含於ELEMENTARY。 1,..., xn).
新！!: PR (複雜度)和ELEMENTARY · 查看更多 »
迭代冪次
在數學裡面，迭代冪次（亦作超-4運算），或可理解為迭代乘方、冪塔運算和超冪運算等等，是專指冪的下一個超運算級別，用以表示極大的數字。以下列舉了首四個超運算級別，其中迭代冪次為第四級，（后继函数，例如a'.
新！!: PR (複雜度)和迭代冪次 · 查看更多 »
阿克曼函數
阿克曼函數是非原始递归函数的例子；它需要兩個自然數作為輸入值，輸出一個自然數。它的輸出值增長速度非常高。.
新！!: PR (複雜度)和阿克曼函數 · 查看更多 »
递归可枚举集合
递归可枚举集合（Recursively enumerable set）是可计算性理论或更狭义的递归论中的一个概念。可数集合S被称为是递归可枚举、计算可枚举的、半可判定的或可证明的，如果.
新！!: PR (複雜度)和递归可枚举集合 · 查看更多 »
R (複雜度)
在計算複雜度理論內，R代表可以用圖靈機解決的所有決定型問題問題。，也就是所有遞歸語言的集合。R也等同於包含所有可計算函數的集合。 因為一個語言只要同時有識別者（recognizer，能在此語言的輸入為真時停止並且回傳的圖靈機）和反識別者（recognizer，能在此語言的輸入為假時停止並且回傳正確答案的圖靈機），我們就可以單純的把兩台機器擺在一起，等待其中一個回傳，來解決這個語言。所以，R這個類別等同於RE \cap coRE.
新！!: PR (複雜度)和R (複雜度) · 查看更多 »
RE (複雜度)
在可計算性理論跟計算複雜度理論內，RE（Recursively Enumerable，參考遞歸可枚舉集合）是一個決定型問題的複雜度類。裡面的問題，當答案是'yes'的時候可以使用圖靈機在有限的時間內運算。不大正式的說法是，當問題的答案是'yes'，則存在一些方法可以在有限時間內決定。不過，如果這個問題的答案是"NO"，那這個機器有可能永遠沒有辦法結束運算。RE也可以視為存在一個將問題裡面'yes'的答案一一列舉出來的圖靈機（也就是這裡所說'可枚舉的'的意思）。 co-RE則是所有RE語言其補集（complement）的總集合。某種意義上我們可以說，co-RE包含的語言，其裡面的問題要證明為錯誤，只要有限的時間；但是可能要無限的時間，才能證明這問題正確。 RE裡面的每個成員都屬於遞歸可枚舉集合，因此同時也是丟番圖集。.
新！!: PR (複雜度)和RE (複雜度) · 查看更多 »
