R (complexity) (original) (raw)
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.
| Property | Value |
|---|---|
| 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 | 3106763 (xsd:integer) |
| dbo:wikiPageLength | 1170 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1025078052 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Decision_problem dbr:Computable_function dbr:Computational_complexity_theory dbr:Graph_of_a_function dbr:RE_(complexity) dbc:Complexity_classes dbr:Recursive_language dbr:Bulletin_of_the_American_Mathematical_Society dbr:Indicator_function dbr:Recognizer dbr:Turing_machine dbr:Blum,_Lenore dbr:Steve_Smale |
| dbp:wikiPageUsesTemplate | dbt:ComplexityClasses dbt:CZoo dbt:Comp-sci-theory-stub |
| dcterms:subject | dbc:Complexity_classes |
| gold:hypernym | dbr:Problems |
| rdf:type | yago:WikicatComplexityClasses yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Group100031264 dbo:Disease |
| 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 | freebase:R (complexity) yago-res:R (complexity) wikidata:R (complexity) dbpedia-ca:R (complexity) dbpedia-es:R (complexity) dbpedia-ja:R (complexity) dbpedia-ko:R (complexity) dbpedia-pt:R (complexity) dbpedia-sr:R (complexity) dbpedia-zh:R (complexity) https://global.dbpedia.org/id/8tUn |
| prov:wasDerivedFrom | wikipedia-en:R_(complexity)?oldid=1025078052&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:R_(complexity) |
| is dbo:wikiPageDisambiguates of | dbr:R_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:R_(complexity_class) |
| is dbo:wikiPageWikiLink of | dbr:List_of_complexity_classes dbr:General_recursive_function dbr:PR_(complexity) dbr:ELEMENTARY dbr:RE_(complexity) dbr:R_(disambiguation) dbr:Recursive_language dbr:R_(complexity_class) |
| is foaf:primaryTopic of | wikipedia-en:R_(complexity) |