Conjunto recursivamente enumerable

Conjunto recursivamente enumerable

Se denomina recursivamente enumerable (r. e.) a un conjunto, dentro de la teoría de la computabilidad, si existe una función computable g(x) que esté definida únicamente para aquellos números naturales que pertenecen a B:

B = \{ x \in \mathbb{N} \mid g(x) = \downarrow \}

Véase también


Wikimedia foundation. 2010.

См. также в других словарях:

  • Conjunto recursivamente enumerable — En teoría de la computabilidad, un conjunto se denomina recursivamente enumerable (r. e.) si existe una función computable g(x) que esté definida únicamente para aquellos números naturales que pertenecen a B: B = x ∈ ℕ | g(x) = ↓ Ver también: ●… …   Enciclopedia Universal

  • Décimo problema de Hilbert — Saltar a navegación, búsqueda El décimo problema de Hilbert es uno de los veintitrés que David Hilbert propuso al término del siglo XIX. Su enunciado original es: Dada una ecuación diofántica con cualquier número de incógnitas y con coeficientes… …   Wikipedia Español

  • RE (clase de complejidad) — 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… …   Wikipedia Español

  • Indecidibilidad — No debe confundirse con «indecible» o «inefable». Indecidibilidad, la cualidad de lo indecidible (lo contrario de la decidibilidad y lo decidible), puede referirse a: En lógica matemática: La independencia de una sentencia de una teoría… …   Wikipedia Español

  • Número computable — En matemáticas, especialmente en ciencia computacional teórica y lógica matemática, los números computables o recursivos son los números reales que pueden ser computados con la precisión que se desee por un algoritmo finito. Se puede llegar al… …   Wikipedia Español

  • Función computable — Las funciones computables son el objeto básico de estudio de la teoría de la computabilidad y son, específicamente, las funciones que pueden ser calculadas por una máquina de Turing. Contenido 1 Introducción 2 Definición 3 Comentarios …   Wikipedia Español

  • Jerarquía de Chomsky — Noam Chomsky. En lingüística la jerarquía de Chomsky es una clasificación jerárquica de distintos tipos de gramáticas formales que generan lenguajes formales. Esta jerarquía fue descrita por Noam Chomsky en 1956. Contenido …   Wikipedia Español

  • Teoremas de incompletitud de Gödel — Kurt Gödel a los 19 años de edad, cinco años antes de la demostración de los teoremas. Los teoremas de incompletitud de Gödel son dos célebres teoremas de lógica matemática demostrados por Kurt Gödel en 1930. Ambos están relacionados con la… …   Wikipedia Español

  • Decidibilidad — Saltar a navegación, búsqueda En lógica, el término decidible se refiere a la existencia de un método efectivo para determinar si un objeto es miembro de un conjunto de fórmulas. Un sistema lógico o teoría es decidible sintácticamente si el… …   Wikipedia Español


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»