En théorie de la calculabilité, deux ensembles disjoints d'entiers naturels sont appelés récursivement inséparables s'ils ne peuvent pas être "séparés" par un ensemble récursifBüchi, J.R. Turing-machines and the Entscheidungsproblem. Math. Ann. 148, 201–213 (1962). https://doi.org/10.1007/BF01470748Tennenbaum, S. Inseparable sets and reducibility. Technical Note, University of Michigan, 1961. lien vers le pdf..
Définition Les entiers naturels sont l'ensemble . Étant donné deux sous-ensembles disjoints A et B de , un ensemble séparateur C est un sous-ensemble de tel que A ⊆ C et B ∩ C = ∅ (ou de manière équivalente, A ⊆ C et B ⊆ ). Par exemple, A lui-même est un ensemble séparateur pour la paire, tout comme .
Si une paire d'ensembles disjoints A et B n'a pas d'ensemble séparateur récursif, alors les deux ensembles sont récursivement inséparables.
Exemples Si A est un ensemble non récursif, alors A et son complément sont récursivement inséparables (dont l'un des deux n'est pas récursivement énumérable). Cependant, il existe de nombreux exemples d'ensembles A et B qui sont disjoints, non complémentaires, et récursivement inséparables. De plus, il est possible que A et B soient récursivement inséparables, disjoints et tous deux récursivement énumérable.
Soit φ une énumération standard des fonctions partielles calculables. Alors les ensembles } et } sont récursivement inséparables , p. . Par l'absurde, s'il existe un séparateur récursif C, alors on peut construire le programme qui commence par calculer si son propre index dans l'énumération est dans C ou , puis donne respectivement 1 ou 0 en sortie. Dans les deux cas cela contredit son appartenance à B ou A (respectivement). Soit # un codage de Gödel standard pour les formules de l'arithmétique de Peano. Alors l'ensemble } des formules prouvables et l'ensemble } des formules réfutables sont récursivement inséparables. L'inséparabilité des ensembles de formules prouvables et réfutables vaut pour de nombreuses autres théories formelles de l'arithmétique.
Références
Catégorie:Calculabilité