| dbo:abstract
|
- En teoria de la complexitat, la classe de complexitat RE és la classe dels problemes de decisió on la resposta SI es pot verificar amb una màquina de Turing en un temps finit. Això vol dir que si la resposta a un problema és SI, llavors hi ha cert procediment que tarda un temps finit en determinar-ho, i aquest procediment mai dona SI quan la resposta verdadera és NO. Tot i això, quan la resposta verdadera és NO, no cal que el procediment acabi, pot acabar en un bucle infinit per alguna casos de NO. Aquesta mena de procediments s'anomenen semialgorismes, per distingir-los dels algorismes, que es defineixen com una solució completa a un problema. També es pot definir la classe RE com la classe de problemes de decisió pels quals una màquina de Turing pot llistar totes les instàncies que tenen sortida SI (per això es diu enumerable). Cada membre de la classe RE és un conjunt recursivament enumerable i per tant un conjunt diofàntic. De manera similar, la classe co-RE és el conjunt de tots els llenguatges que son complements dels llenguatges de RE. D'alguna manera, co-RE conté els llenguatges dels quals si pertany a la classe es pot descartar en un temps finit, però provar que hi pertanyen pot portar un temps infinit. (ca)
- En complejidad computacional, RE (abreviación de recursivamente enumerable) es la clase de complejidad conformada por aquellos problemas de decisión para los cuales una respuesta "sí" puede ser verificada por una máquina de Turing en una cantidad de tiempo finito. Informalmente, esto significa que si la respuesta es "sí", entonces existe algún procedimiento que toma tiempo finito para determinarla. Por otro lado, si la respuesta es "no", la máquina podría jamás detenerse. Equivalentemente, haciendo alusión a la palabra "enumerable", RE es la clase de los problemas de decisión para los cuales una máquina de Turing puede listar todas las instancias sí, una por una. Análogamente, co-RE es el conjunto de todos los lenguajes que son complementos de un lenguaje en RE. En un sentido, co-RE contiene lenguajes cuyos miembros pueden ser rechazados en una cantidad de tiempo finito, pero que aceptarlos podría tardar para siempre. Cada miembro de RE es un conjunto recursivamente enumerable, y así, un . (es)
- In computability theory and computational complexity theory, RE (recursively enumerable) is the class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time. Informally, it means that if the answer to a problem instance is 'yes', then there is some procedure that takes finite time to determine this, and this procedure never falsely reports 'yes' when the true answer is 'no'. However, when the true answer is 'no', the procedure is not required to halt; it may go into an "infinite loop" for some 'no' cases. Such a procedure is sometimes called a semi-algorithm, to distinguish it from an algorithm, defined as a complete solution to a decision problem. Similarly, co-RE is the set of all languages that are complements of a language in RE. In a sense, co-RE contains languages of which membership can be disproved in a finite amount of time, but proving membership might take forever. (en)
- 計算複雑性理論において、複雑性クラス RE（recursively enumerable）とは、チューリングマシン（Turing machine）で有限時間内に 'yes' という解を得られる決定問題の集合である。逆に解が 'no' であった場合、マシンが停止するかどうかも保証されない。 RE はまた、解が 'yes' であるような問題をチューリングマシンを使ってリストアップ可能な決定問題のクラスでもある。このため 'enumerable'（枚挙可能）と呼ばれる。 解が 'no' の場合に同様の性質となるクラスを Co-RE と呼ぶ。 RE の各要素は帰納的可算集合（recursively enumerable set）である。 (ja)
- RE(순환 열거)는 '예' 답변을 튜링 기계로 유한한 시간에 검증할 수 있는 판정 문제의 집합이다. (답변이 '아니오'인 경우에는 기계가 멈추지 않을 수도 있다.) RE는 튜링 기계가 모든 '예' 예제를 낱낱이 열거할 수 있는 결정 문제의 집합이기도 하다. 이 정의는 앞쪽 정의랑 동등하다. RE의 원소는 모두 순환 열거 집합의 원소이기도 하다. (ko)
- Em Teoria da Computabilidade e na Teoria da Complexidade Computacional, RE (recursivamente enumerável) é uma classe de problemas de decisão onde uma resposta "sim" pode ser verificada por uma máquina de Turing em uma quantidade finita de tempo. Informalmente, isto significa que se a resposta é "sim", então existe algum procedimento que leva um tempo finito para determinar isso. Por outro lado, se a resposta é "não", a máquina poderá nunca parar. Equivalentemente, RE é uma classe de problemas de decisão para que uma máquina de Turing pode listar todas as instâncias "sim", uma por uma (isto é o que 'enumerável' significa). Similarmente, co-RE é o conjunto de todas as linguagens que são complementos de uma linguagem em RE. De certo modo, co-RE contém linguagens em que a pertinência pode ser refutada em uma quantidade finita de tempo, mas provar a pertinência poderá levar uma eternidade. Cada membro de RE é um recursivamente enumerável e, portanto, um conjunto diofantino. (pt)
- 在可計算性理論跟計算複雜度理論內，RE（Recursively Enumerable，參考遞歸可枚舉集合）是一個決定型問題的複雜度類。裡面的問題，當答案是"yes"的時候可以使用圖靈機在有限的時間內運算。不大正式的說法是，當問題的答案是"yes"，則存在一些方法可以在有限時間內決定。不過，如果這個問題的答案是"NO"，那這個機器有可能永遠沒有辦法結束運算。RE也可以視為存在一個將問題裡面"yes"的答案一一列舉出來的圖靈機（也就是這裡所說'可枚舉的'的意思）。 co-RE則是所有RE語言其補集（complement）的總集合。某種意義上我們可以說，co-RE包含的語言，其裡面的問題要證明為錯誤，只要有限的時間；但是可能要無限的時間，才能證明這問題正確。 RE裡面的每個成員都屬於遞歸可枚舉集合，因此同時也是丟番圖集。 (zh)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 7096 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:authorlink
| |
| dbp:first
| |
| dbp:last
| |
| dbp:wikiPageUsesTemplate
| |
| dbp:year
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- 計算複雑性理論において、複雑性クラス RE（recursively enumerable）とは、チューリングマシン（Turing machine）で有限時間内に 'yes' という解を得られる決定問題の集合である。逆に解が 'no' であった場合、マシンが停止するかどうかも保証されない。 RE はまた、解が 'yes' であるような問題をチューリングマシンを使ってリストアップ可能な決定問題のクラスでもある。このため 'enumerable'（枚挙可能）と呼ばれる。 解が 'no' の場合に同様の性質となるクラスを Co-RE と呼ぶ。 RE の各要素は帰納的可算集合（recursively enumerable set）である。 (ja)
- RE(순환 열거)는 '예' 답변을 튜링 기계로 유한한 시간에 검증할 수 있는 판정 문제의 집합이다. (답변이 '아니오'인 경우에는 기계가 멈추지 않을 수도 있다.) RE는 튜링 기계가 모든 '예' 예제를 낱낱이 열거할 수 있는 결정 문제의 집합이기도 하다. 이 정의는 앞쪽 정의랑 동등하다. RE의 원소는 모두 순환 열거 집합의 원소이기도 하다. (ko)
- 在可計算性理論跟計算複雜度理論內，RE（Recursively Enumerable，參考遞歸可枚舉集合）是一個決定型問題的複雜度類。裡面的問題，當答案是"yes"的時候可以使用圖靈機在有限的時間內運算。不大正式的說法是，當問題的答案是"yes"，則存在一些方法可以在有限時間內決定。不過，如果這個問題的答案是"NO"，那這個機器有可能永遠沒有辦法結束運算。RE也可以視為存在一個將問題裡面"yes"的答案一一列舉出來的圖靈機（也就是這裡所說'可枚舉的'的意思）。 co-RE則是所有RE語言其補集（complement）的總集合。某種意義上我們可以說，co-RE包含的語言，其裡面的問題要證明為錯誤，只要有限的時間；但是可能要無限的時間，才能證明這問題正確。 RE裡面的每個成員都屬於遞歸可枚舉集合，因此同時也是丟番圖集。 (zh)
- En teoria de la complexitat, la classe de complexitat RE és la classe dels problemes de decisió on la resposta SI es pot verificar amb una màquina de Turing en un temps finit. Això vol dir que si la resposta a un problema és SI, llavors hi ha cert procediment que tarda un temps finit en determinar-ho, i aquest procediment mai dona SI quan la resposta verdadera és NO. Tot i això, quan la resposta verdadera és NO, no cal que el procediment acabi, pot acabar en un bucle infinit per alguna casos de NO. Aquesta mena de procediments s'anomenen semialgorismes, per distingir-los dels algorismes, que es defineixen com una solució completa a un problema. (ca)
- En complejidad computacional, RE (abreviación de recursivamente enumerable) es la clase de complejidad conformada por aquellos problemas de decisión para los cuales una respuesta "sí" puede ser verificada por una máquina de Turing en una cantidad de tiempo finito. Informalmente, esto significa que si la respuesta es "sí", entonces existe algún procedimiento que toma tiempo finito para determinarla. Por otro lado, si la respuesta es "no", la máquina podría jamás detenerse. Equivalentemente, haciendo alusión a la palabra "enumerable", RE es la clase de los problemas de decisión para los cuales una máquina de Turing puede listar todas las instancias sí, una por una. (es)
- In computability theory and computational complexity theory, RE (recursively enumerable) is the class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time. Informally, it means that if the answer to a problem instance is 'yes', then there is some procedure that takes finite time to determine this, and this procedure never falsely reports 'yes' when the true answer is 'no'. However, when the true answer is 'no', the procedure is not required to halt; it may go into an "infinite loop" for some 'no' cases. Such a procedure is sometimes called a semi-algorithm, to distinguish it from an algorithm, defined as a complete solution to a decision problem. (en)
- Em Teoria da Computabilidade e na Teoria da Complexidade Computacional, RE (recursivamente enumerável) é uma classe de problemas de decisão onde uma resposta "sim" pode ser verificada por uma máquina de Turing em uma quantidade finita de tempo. Informalmente, isto significa que se a resposta é "sim", então existe algum procedimento que leva um tempo finito para determinar isso. Por outro lado, se a resposta é "não", a máquina poderá nunca parar. Equivalentemente, RE é uma classe de problemas de decisão para que uma máquina de Turing pode listar todas as instâncias "sim", uma por uma (isto é o que 'enumerável' significa). (pt)
|
| rdfs:label
|
- RE (complexitat) (ca)
- RE (clase de complejidad) (es)
- RE (計算複雑性理論) (ja)
- RE (복잡도) (ko)
- RE (complexity) (en)
- RE (complexidade) (pt)
- RE (複雜度) (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
