Conjunto recursivo

En la teoría de la computabilidad , un conjunto recursivo o un conjunto decidible es un conjunto de números enteros (o elementos fácilmente codificables en números enteros) cuya función característica es una función recursiva en el sentido de la lógica matemática .

En otras palabras, un conjunto es recursivo si, y solo si, existe una máquina de Turing (un programa de computadora ) que permite determinar en un tiempo finito si algún número entero está o no. mi{\ Displaystyle E} T{\ Displaystyle T}mi{\ Displaystyle E}

∀no∈NO{\ Displaystyle \ forall n \ in \ mathbb {N}}
T(no)=OUI Si no∈mi{\ Displaystyle T (n) = SÍ \ {\ mbox {si}} \ n \ in E}
T(no)=NOONO Si no∉mi{\ Displaystyle T (n) = NO \ {\ mbox {si}} \ n \ notin E}

Este tipo de conjunto corresponde a un concepto actual de John R. Myhill , que son los conceptos que se pueden definir de forma extensa e inequívoca. La noción de conjunto recursivamente enumerable (no recursivo) es más bien un concepto constructivo , cuyo contenido se vuelve más claro y mejor y mejor comprendido con el tiempo, sin que nunca sea posible definirlo completamente.

Definición en términos de un sistema formal

En la terminología de los sistemas formales , la siguiente definición es equivalente:

mi{\ Displaystyle E}es recursivo si y solo si existe un sistema formal correcto y completo para enunciados de la forma "  está en  " y de la forma "  no está en  ".no{\ Displaystyle n}mi{\ Displaystyle E}no{\ Displaystyle n}mi{\ Displaystyle E}

Propiedades

• Un conjunto A es recursivo si y solo si A y su complemento son recursivamente enumerables .
• Si A y B son recursivos, entonces A ∩ B y A ∪ B son recursivos.

Ejemplos de

Los siguientes conjuntos son recursivos:

• cualquier conjunto finito (el conjunto vacío ∅ es un ejemplo trivial);
• el conjunto de múltiplos de un entero (números enteros, números pares, etc.);k{\ Displaystyle k}
• el conjunto de números primos;
• el conjunto de soluciones de una ecuación diofántica dada.

Los siguientes conjuntos son recursivamente enumerables pero no recursivos:

• el conjunto de ecuaciones diofánticas que tienen una solución entera;
• todos los programas que se detienen (los programas que no se ejecutan indefinidamente): consulte “  Problema de detención  ”.

Actualmente no se sabe si el conjunto múltiple de los términos de la secuencia de Syracuse del término inicial es recursivo para cualquier (implícito: entero). La conjetura de Siracusa afirma lo contrario, pero sigue sin demostrarse hasta el día de hoy. Por otro lado, es recursivamente enumerable por definición. tu0=k{\ Displaystyle u_ {0} = k}k>0{\ Displaystyle k> 0}k{\ Displaystyle k}

Notas y referencias

1. Jean-Paul Delahaye , la información, la complejidad y Chance , Hermes Ciencia Publishing,1999( ISBN  2-7462-0026-0 )pag. 74.

Ver también

Artículos relacionados

• Problema decidible
• Décimo problema de Hilbert

Enlace externo

Curso de recursividad