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.

Property Value
dbo:abstract
  • 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)
  • 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)
dbo:wikiPageID
  • 3904488 (xsd:integer)
dbo:wikiPageLength
  • 2395 (xsd:integer)
dbo:wikiPageRevisionID
  • 119639286 (xsd:integer)
dct:subject
rdfs:comment
  • 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)
  • 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)
rdfs:label
  • RE (clase de complejidad) (es)
  • RE (clase de complejidad) (es)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageRedirects of
is owl:sameAs of
is foaf:primaryTopic of