problème indécidable et sa négation est indécidable

13

Beaucoup de problèmes indécidables «célèbres» sont néanmoins au moins semi-décidables, leur complément étant indécidable. Un exemple par-dessus tout peut être le problème de l'arrêt et son complément.

Cependant, quelqu'un peut-il me donner un exemple dans lequel un problème et son complément sont indécidables et non semi-décidables? J'ai pensé au langage de diagonalisation Ld, mais il ne me semble pas que le complément soit indécidable.

Dans ce cas, cela signifie-t-il qu'une machine de Turing M peut "perdre" certaines chaînes qui devraient plutôt être reconnues, car elles font partie du langage que nous essayons d'identifier?

Giulia Frascaria
la source

Réponses:

15

Considérez la langue suivante:

L2={(M1,x1,M2,x2):M1 halts on input x1 and M2 doesn't halt on input x2}.

est indécidable et non semi-décidable, et il en va de même pour son complément. Pourquoi? L'intuition est que " M 2 ne s'arrête pas à l'entrée x 2 " n'est pas semi-décidable, donc L 2 n'est pas semi-décidable; et quand on regarde le complément de L 2 , la même chose se produit pour M 1 . Cela peut être formalisé plus soigneusement en utilisant des réductions.L2M2x2L2L2M1

Plus généralement, si est un langage indécidable et non semi-décidable, alorsL

L={(x,y):xL,yL}

répond à vos exigences: est indécidable et non semi-décidable, et il en va de même pour le complément de L ' .LL

DW
la source
7

Notez que la grande majorité des problèmes correspondent au critère que vous recherchez: le problème et son complément ne sont pas semi-décidables. En effet, il n'y a que de nombreux problèmes semi-décidables, mais il y en a énormément.

Pour un exemple, que soit le problème pour les machines de Turing arrêt et laisser M la classe des machines de Turing avec un oracle pour  H . Que H 2 soit le problème de l' arrêt pour  M . Je prétends que ni H 2 ni  ¯ H 2 n'est semi-décidableHMHH2MH2H2¯

Nous pouvons montrer que n'est décidé par aucune machine dans  M : l'argument est le même que l'argument selon lequel le problème d'arrêt de la machine de Turing ordinaire  H n'est décidé par aucune machine de Turing ordinaire. Maintenant, supposons que la contradiction H 2  est semi-décidée par une machine de Turing ordinaire  T . Eh bien, avec un oracle pour  H , nous pouvons tester si T  s'arrête pour une entrée particulière, contredisant le fait qu'aucune machine dans  M ne décide de  H 2 . Donc, H 2  n'est pas semi-décidable.H2MHH2THTMH2H2

Reste à montrer que n'est pas semi-décidable. Tout d'abord, notez qu'il est semi-décidé par une machine en  M : encore une fois, l'argument est le même que H  étant semi-décidé par une machine de Turing ordinaire. ¯ H 2  ne peut pas être semi-décidée par une machine à  M parce que, si elle était, H 2 et  ¯ H 2 seraient tous les deux semi-décidé par des machines à  M , afin que les deux langues seraient décidées par des machines à  M . Mais nous savons déjà que H 2  ne se décide pas par une machine  M . Donc,H2¯MHH2¯MH2H2¯MMH2M  ne sont pas semi-décidé par une machine M. De plus, ¯ H 2 n'est pas semi-décidé par une machine de Turing ordinaire, puisqueM contient chaque machine de Turing ordinaire. (Une machine de Turing ordinaire est une machine de Turing avec un oracle pour Hqui n'utilise jamais cet oracle.)H2¯MH2¯MH

David Richerby
la source
7

Voici quelques exemples naturels:

  • Le langage de toutes les machines Turing s'arrêtant sur toutes les entrées, parfois appelé TOT. Cette langue est -complète.Π20

  • Le langage de toutes les machines Turing s'arrêtant sur une infinité d' entrées, parfois noté INF. Cette langue est également complète.Π20

  • Le langage de toutes les machines Turing s'arrêtant sur des entrées arbitrairement longues , parfois dénommé COF. Cette langue est -complète.Σ30

Π20Σ30

Yuval Filmus
la source