PR (complexity)
http://dbpedia.org/resource/PR_(complexity) an entity of type: WikicatComplexityClasses
En teoria de la complexitat, la classe de complexitat PR és el conjunt de totes les funcions recursives primitives o, equivalentment el conjunt de tots els llenguatges formals que es poden decidir per aquestes funcions. La funció d'Ackermann és un exemple de funció que no és funció recursiva primitiva, mostrant que la classe PR és estrictament continguda a R. PR conté estrictament la classe ELEMENTARY. PR no conté els problemes PR-complet.
rdf:langString
PR은 모든 원시 재귀 함수를 모은 복잡도 종류이다. 동치인 정의로, 단순한 자기 참조 함수로 판정할 수 있는 모든 형식 언어의 집합이라고 할 수도 있다. 단순한 자기 참조 함수에는 덧셈, 곱셈, 거듭제곱, 반복된 거듭제곱 따위가 들어 있다. 아커만 함수는 자기 참조 함수이지만 단순하지는 않은 함수이다. 이런 함수가 있다는 것은 PR이 R의 진부분집합임을 뜻한다. PR에 속한 함수는 명시적으로 나열할 수 있지만, R에 속한 함수는 그렇게 할 수 없다. 만약 할 수 있다면 정지 문제가 이 될 것이기 때문이다. 이것은 PR이 "구문" 복잡도 종류이고, R은 "의미" 복잡도 종류임을 뜻한다. 단순한 자기 호출 함수를 쓰면 어떠한 순환 열거 집합도 "나열"할 수 있다. 이것은 이런 관점에서 볼 때 하는 말이다. M이 튜링 기계이고, k가 정수라 하자. 입력 (M, k)가 주어질 때, M이 k 단계 안에 멈추면 출력은 M이고, 멈추지 않으면 출력은 없다. 그러면 모든 가능한 입력 (M, k)에 대한 출력의 합집합은 멈춘 M의 집합과 정확히 같다. PR은 를 포함한다. (같지는 않다.)
rdf:langString
計算複雑性理論において、複雑性クラス PR とは、全ての原始再帰関数の集合、あるいは原始再帰関数で決定される全ての形式言語の集合である。これには、加算、乗算、冪乗、tetration などが含まれる。 原始再帰的でない関数の例としてアッカーマン関数があり、それにより PR が厳密に R に含まれることがわかる。 PR に属する関数は明示的に枚挙可能だが、R の場合は不可能である（チューリングマシンの停止問題が決定不能であるため）。すなわち、PR は構文的クラスであり、R は意味論的クラスである。 一方、任意の帰納的可算集合（REも参照）を原始再帰関数を次のように使って枚挙可能である。入力 (M, k) を与えたとき（M はチューリングマシン、k は整数）、M が k ステップ以内に停止するなら M を出力するものとする。そうでない場合は何も出力しない。すると (M, k) の考えられる全ての組合せの入力について、それらの出力の和集合は、停止する M の集合に他ならない。
rdf:langString
PR 是包含所有原始遞歸函數 – 或者換句話說，所有能被這類函數定義的形式語言，這包含了加法，乘法，指數，以及迭代冪次等等。 阿克曼函數則是一個並非 原始遞歸函數的範例，告訴我們R包含但不等同(strictly contain，或者說嚴格包含)PR。 PR 函數可以被獨立的列舉，而並非所有R裡面的函數皆可。這告訴我們'PR'有一個語意的定義，但是R則沒有。 另一方面，我們可以用下列的概念去使用原始遞歸函數"列舉"任何的遞歸可枚舉集合 (參見另一個複雜度類RE)：給定輸入 (M, k)，M是一個圖靈機而k是一個正整數，如果M會在k步以內停止則輸出M；否則就甚麼都不輸出。然後，這裡輸出的聯集，也就是(M, k)這些組合所有可能的輸出，恰好是會停止的M的集合。 PR 包含但不等於ELEMENTARY。
rdf:langString
PR Es la clase de complejidad de todas las funciones recursivas primitivas o, de forma equivalente, el conjunto de todos los lenguajes formales que pueden ser decididos por tales funciones. Esto incluye adición, multiplicación, exponenciación, tetración, etc. La función de Ackermann es un ejemplo de una función que no es primitiva recursiva, y permite demostrar que PR está estrictamente contenida en R. PR contiene estrictamente a la clase ELEMENTARY.
rdf:langString
PR is the complexity class of all primitive recursive functions—or, equivalently, the set of all formal languages that can be decided in time bounded by such a function. This includes addition, multiplication, exponentiation, tetration, etc. The Ackermann function is an example of a function that is not primitive recursive, showing that PR is strictly contained in R (Cooper 2004:88). PR strictly contains ELEMENTARY.
rdf:langString
PR é a classe de complexidade de todas as funções recursivas primitivas , ou, equivalentemente, o conjunto de todas as linguagens formais que pode ser decididas por uma tal função. Isso inclui a adição, multiplicação, potência, tetração, etc. A função de Ackermann é um exemplo de função que não é recursiva primitiva, mostrando que PR esta estritamente contida em R (Cooper, 2004:88). PR estritamente contém ELEMENTAR.
rdf:langString
rdf:langString
PR (Complexitat)
rdf:langString
PR (complejidad)
rdf:langString
PR (복잡도)
rdf:langString
PR (計算複雑性理論)
rdf:langString
PR (complexity)
rdf:langString
PR (complexidade)
rdf:langString
PR (複雜度)
xsd:integer
3106897
xsd:integer
1100504880
rdf:langString
En teoria de la complexitat, la classe de complexitat PR és el conjunt de totes les funcions recursives primitives o, equivalentment el conjunt de tots els llenguatges formals que es poden decidir per aquestes funcions. La funció d'Ackermann és un exemple de funció que no és funció recursiva primitiva, mostrant que la classe PR és estrictament continguda a R. PR conté estrictament la classe ELEMENTARY. PR no conté els problemes PR-complet.
rdf:langString
PR Es la clase de complejidad de todas las funciones recursivas primitivas o, de forma equivalente, el conjunto de todos los lenguajes formales que pueden ser decididos por tales funciones. Esto incluye adición, multiplicación, exponenciación, tetración, etc. La función de Ackermann es un ejemplo de una función que no es primitiva recursiva, y permite demostrar que PR está estrictamente contenida en R. Por otro lado, es posible "enumerar" cualquier conjunto recursivamente enumerable (véase también su clase de complejidad ) con una función primitiva recursiva en el sentido siguiente: dado una entrada (M, k), en donde M es una máquina de Turing y k es un entero, si M se detiene en k pasos o menos entonces su respuesta es M; en caso contrario no produce resultado. Entonces la unión de las respuestas, de todas las entradas posibles (M, k), es exactamente el conjunto de las máquinas M que terminan en tiempo finito. PR contiene estrictamente a la clase ELEMENTARY.
rdf:langString
PR is the complexity class of all primitive recursive functions—or, equivalently, the set of all formal languages that can be decided in time bounded by such a function. This includes addition, multiplication, exponentiation, tetration, etc. The Ackermann function is an example of a function that is not primitive recursive, showing that PR is strictly contained in R (Cooper 2004:88). On the other hand, we can "enumerate" any recursively enumerable set (see also its complexity class RE) by a primitive-recursive function in the following sense: given an input (M, k), where M is a Turing machine and k is an integer, if M halts within k steps then output M; otherwise output nothing. Then the union of the outputs, over all possible inputs (M, k), is exactly the set of M that halt. PR strictly contains ELEMENTARY. PR does not contain "PR-complete" problems (assuming, e.g., reductions that belong to ELEMENTARY). In practice, many problems that are not in PR but just beyond are -complete (Schmitz 2016).
rdf:langString
PR은 모든 원시 재귀 함수를 모은 복잡도 종류이다. 동치인 정의로, 단순한 자기 참조 함수로 판정할 수 있는 모든 형식 언어의 집합이라고 할 수도 있다. 단순한 자기 참조 함수에는 덧셈, 곱셈, 거듭제곱, 반복된 거듭제곱 따위가 들어 있다. 아커만 함수는 자기 참조 함수이지만 단순하지는 않은 함수이다. 이런 함수가 있다는 것은 PR이 R의 진부분집합임을 뜻한다. PR에 속한 함수는 명시적으로 나열할 수 있지만, R에 속한 함수는 그렇게 할 수 없다. 만약 할 수 있다면 정지 문제가 이 될 것이기 때문이다. 이것은 PR이 "구문" 복잡도 종류이고, R은 "의미" 복잡도 종류임을 뜻한다. 단순한 자기 호출 함수를 쓰면 어떠한 순환 열거 집합도 "나열"할 수 있다. 이것은 이런 관점에서 볼 때 하는 말이다. M이 튜링 기계이고, k가 정수라 하자. 입력 (M, k)가 주어질 때, M이 k 단계 안에 멈추면 출력은 M이고, 멈추지 않으면 출력은 없다. 그러면 모든 가능한 입력 (M, k)에 대한 출력의 합집합은 멈춘 M의 집합과 정확히 같다. PR은 를 포함한다. (같지는 않다.)
rdf:langString
計算複雑性理論において、複雑性クラス PR とは、全ての原始再帰関数の集合、あるいは原始再帰関数で決定される全ての形式言語の集合である。これには、加算、乗算、冪乗、tetration などが含まれる。 原始再帰的でない関数の例としてアッカーマン関数があり、それにより PR が厳密に R に含まれることがわかる。 PR に属する関数は明示的に枚挙可能だが、R の場合は不可能である（チューリングマシンの停止問題が決定不能であるため）。すなわち、PR は構文的クラスであり、R は意味論的クラスである。 一方、任意の帰納的可算集合（REも参照）を原始再帰関数を次のように使って枚挙可能である。入力 (M, k) を与えたとき（M はチューリングマシン、k は整数）、M が k ステップ以内に停止するなら M を出力するものとする。そうでない場合は何も出力しない。すると (M, k) の考えられる全ての組合せの入力について、それらの出力の和集合は、停止する M の集合に他ならない。
rdf:langString
PR é a classe de complexidade de todas as funções recursivas primitivas , ou, equivalentemente, o conjunto de todas as linguagens formais que pode ser decididas por uma tal função. Isso inclui a adição, multiplicação, potência, tetração, etc. A função de Ackermann é um exemplo de função que não é recursiva primitiva, mostrando que PR esta estritamente contida em R (Cooper, 2004:88). Por outro lado, podemos "enumerar" qualquer conjunto recursivamente enumerável (veja também a sua classe de complexidade RE) por uma função recursiva primitiva no seguinte sentido: dada uma entrada (M, k), onde M é uma máquina de Turing e k é um número inteiro, se M pára dentro de k passos, dê M como saída; caso contrário, dê nada como saída. Então, a união das saídas, através de todas as entradas possíveis (M, k), é exatamente o conjunto das M que param. PR estritamente contém ELEMENTAR.
rdf:langString
PR 是包含所有原始遞歸函數 – 或者換句話說，所有能被這類函數定義的形式語言，這包含了加法，乘法，指數，以及迭代冪次等等。 阿克曼函數則是一個並非 原始遞歸函數的範例，告訴我們R包含但不等同(strictly contain，或者說嚴格包含)PR。 PR 函數可以被獨立的列舉，而並非所有R裡面的函數皆可。這告訴我們'PR'有一個語意的定義，但是R則沒有。 另一方面，我們可以用下列的概念去使用原始遞歸函數"列舉"任何的遞歸可枚舉集合 (參見另一個複雜度類RE)：給定輸入 (M, k)，M是一個圖靈機而k是一個正整數，如果M會在k步以內停止則輸出M；否則就甚麼都不輸出。然後，這裡輸出的聯集，也就是(M, k)這些組合所有可能的輸出，恰好是會停止的M的集合。 PR 包含但不等於ELEMENTARY。
xsd:nonNegativeInteger
1857