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

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?

Considérez la langue suivante:

$$L_2 = \{(M_1,x_1,M_2,x_2) : \text{$M_1$ halts on input $x_1$ and $M_2$ doesn't halt on input $x_2$}\}.$$

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.$L_2$$M_2$$x_2$$L_2$$L_2$$M_1$

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

$$L' = \{(x,y) : x \in L, y \notin L\}$$

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 ' .$L'$$L'$

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écidable$H$$\cal{M}$$H$$H_2$$\cal{M}$$H_2$$\overline{H_2}$

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.$H_2$$\cal{M}$$H$$H_2$$T$$H$$T$$\cal{M}$$H_2$$H_2$

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,$\overline{H_2}$$\cal{M}$$H$$\overline{H_2}$$\cal{M}$$H_2$$\overline{H_2}$$\cal{M}$$\cal{M}$$H_2$$\cal{M}$  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.)$\overline{H_2}$$\cal{M}$$\overline{H_2}$$\cal{M}$$H$

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.$\Pi_2^0$

• 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.$\Pi_2^0$

• 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.$\Sigma_3^0$

$\Pi_2^0$$\Sigma_3^0$