| dbo:abstract
|
- En teoria de la complexitat, la classe de complexitat R és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing, que és el conjunt de tots els llenguatges recursius. Per tant, R equival al conjunt de totes les funcions computables. La classe R és igual a RE ∩ coRE. (ca)
- En complejidad computacional, R es la clase conformada por los problemas de decisión resolubles por una máquina de Turing, vale decir, el conjunto de todos los lenguajes recursivos. R es usualmente identificado con la clase de funciones efectivamente computables, según la Tesis de Church-Turing. Esta clase es equivalente a RE ∩ coRE. (es)
- In computational complexity theory, R is the class of decision problems solvable by a Turing machine, which is the set of all recursive languages (also called decidable languages). (en)
- 計算複雑性理論において、複雑性クラス R とは、チューリングマシンで解ける決定問題の集合であり、全ての帰納言語の集合に相当する。R はしばしば、「効率的に計算可能な」関数のクラスと言われる（チャーチ＝チューリングのテーゼ）。 任意の決定問題の解法として、その問題のリコグナイザと補問題のリコグナイザを並行して動作させ、どちらかが受容状態になるまで待つ方式を採用可能である。したがって、このクラスは RE を使って と定義できる。 (ja)
- 계산 복잡도 이론에서 R은 튜링 기계로 풀 수 있는 결정 문제들의 복잡도 종류로, 모든 재귀 언어의 집합과 같다. 또한 R은 모든 전역 계산 가능 함수를 모은 집합과 같으므로 '효율적으로 계산할 수 있는' 함수의 집합으로 볼 수 있어 계산 가능성 이론에서 중요시된다. (처치-튜링 명제) 이 집합은 RE와 co-RE의 교집합과 같다. 어떤 문제의 정답과 오답이 모두 인지 가능하다면 그 문제는 결정 가능하기 때문이다. (ko)
- Na teoria da complexidade computacional, R é a classe de problemas de decisão solúveis por uma máquina de Turing, que é o conjunto de todas as linguagens recursivas. (pt)
- 在計算複雜度理論內，R代表可以用圖靈機解決的所有決定型問題問題。，也就是所有遞歸語言的集合。R也等同於包含所有可計算函數的集合。 因為一個語言只要同時有識別者（recognizer，能在此語言的輸入為真時停止並且回傳的圖靈機）和反識別者（recognizer，能在此語言的輸入為假時停止並且回傳正確答案的圖靈機），我們就可以單純的把兩台機器擺在一起，等待其中一個回傳，來解決這個語言。所以，R這個類別等同於. (zh)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 1170 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- En teoria de la complexitat, la classe de complexitat R és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing, que és el conjunt de tots els llenguatges recursius. Per tant, R equival al conjunt de totes les funcions computables. La classe R és igual a RE ∩ coRE. (ca)
- En complejidad computacional, R es la clase conformada por los problemas de decisión resolubles por una máquina de Turing, vale decir, el conjunto de todos los lenguajes recursivos. R es usualmente identificado con la clase de funciones efectivamente computables, según la Tesis de Church-Turing. Esta clase es equivalente a RE ∩ coRE. (es)
- In computational complexity theory, R is the class of decision problems solvable by a Turing machine, which is the set of all recursive languages (also called decidable languages). (en)
- 計算複雑性理論において、複雑性クラス R とは、チューリングマシンで解ける決定問題の集合であり、全ての帰納言語の集合に相当する。R はしばしば、「効率的に計算可能な」関数のクラスと言われる（チャーチ＝チューリングのテーゼ）。 任意の決定問題の解法として、その問題のリコグナイザと補問題のリコグナイザを並行して動作させ、どちらかが受容状態になるまで待つ方式を採用可能である。したがって、このクラスは RE を使って と定義できる。 (ja)
- 계산 복잡도 이론에서 R은 튜링 기계로 풀 수 있는 결정 문제들의 복잡도 종류로, 모든 재귀 언어의 집합과 같다. 또한 R은 모든 전역 계산 가능 함수를 모은 집합과 같으므로 '효율적으로 계산할 수 있는' 함수의 집합으로 볼 수 있어 계산 가능성 이론에서 중요시된다. (처치-튜링 명제) 이 집합은 RE와 co-RE의 교집합과 같다. 어떤 문제의 정답과 오답이 모두 인지 가능하다면 그 문제는 결정 가능하기 때문이다. (ko)
- Na teoria da complexidade computacional, R é a classe de problemas de decisão solúveis por uma máquina de Turing, que é o conjunto de todas as linguagens recursivas. (pt)
- 在計算複雜度理論內，R代表可以用圖靈機解決的所有決定型問題問題。，也就是所有遞歸語言的集合。R也等同於包含所有可計算函數的集合。 因為一個語言只要同時有識別者（recognizer，能在此語言的輸入為真時停止並且回傳的圖靈機）和反識別者（recognizer，能在此語言的輸入為假時停止並且回傳正確答案的圖靈機），我們就可以單純的把兩台機器擺在一起，等待其中一個回傳，來解決這個語言。所以，R這個類別等同於. (zh)
|
| rdfs:label
|
- R (Complexitat) (ca)
- R (clase de complejidad) (es)
- R (복잡도) (ko)
- R (計算複雑性理論) (ja)
- R (complexity) (en)
- R (complexidade) (pt)
- R (複雜度) (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
