Réductions des problèmes indécidables

Je suis désolé si cette question a une réponse triviale qui me manque. Chaque fois que j'étudie un problème qui s'est révélé indécidable, j'observe que la preuve repose sur une réduction à un autre problème qui s'est avéré indécidable. Je comprends que cela crée une sorte d'ordre sur le degré de difficulté d'un problème. Mais ma question est - a-t-il été prouvé que tous les problèmes indécidables peuvent être réduits à un autre problème indécidable. N'est-il pas possible qu'il existe un problème indécidable qui peut se révéler n'avoir aucune réduction à un autre problème indécidable (Par conséquent, pour prouver l'indécidabilité d'un tel problème, on ne peut pas utiliser des réductions). Si nous utilisons des réductions pour créer un ordre sur le degré de calculabilité, ce problème ne peut pas être attribué à un tel degré.

computability reductions undecidability swarnim_narayan
la source

Réponse courte: loin d'être triviale! Regardez la hiérarchie arithmétique .

Hendrik Jan

Qu'en est- il: si est un langage indécidable et soit le plus petit élément

. Ensuite ,

est réductible (et vice versa) à

. Si vous ajoutez en plus un élément à

(disons le plus petit élément qui n'est pas dans

), alors vous avez une réduction de 1-1.

L

$L$

x min L

$x \min L$

L

$L$

L^{'} = L ∖ {x}

$L' = L \setminus \{x\}$

L

$L$

L^{'}

$L'$

L

$L$

Pål GD

Réponses:

Comme l'a mentionné Hendrik Jan, il existe en fait différents degrés d'indécidabilité. Par exemple, le problème de décider si une machine Turing s'arrête sur toutes les entrées est plus difficile que le problème d'arrêt, dans le sens suivant: même si on donne un oracle au problème d'arrêt, nous ne pouvons pas décider si une machine Turing donnée s'arrête sur toutes les entrées .

Une technique importante utilisée pour montrer des relations comme celles-ci est la diagonalisation . En utilisant la diagonalisation, étant donné un problème nous pouvons toujours trouver un problème plus difficile, à savoir le problème d'arrêt pour les machines de Turing ayant accès à un oracleLe nouveau problème est plus difficile dans le sens suivant: une machine de Turing avec un accès oracle à ne peut pas résoudre . En ce sens, il n'y a pas de problème "le plus difficile". $P$ $P$ $P'$ $P$ $P'$

Yuval Filmus
la source

Merci pour la réponse. J'ai compris ce que tu dis. Nous pouvons construire des problèmes "plus difficiles" à partir de problèmes "durs". Mais ces schémas de construction de problèmes plus difficiles à partir de problèmes durs (par exemple, disons que la diagonalisation est l'un de ces schémas comme vous l'avez mentionné) couvrent-ils nécessairement "tous" les problèmes indécidables existants (c'est-à-dire qu'ils sont garantis pour construire l'ensemble de tous les problèmes indécidables). N'est-il pas possible que certains soient laissés de côté dans la construction et qu'ils ne puissent pas être construits à partir d'autres indécidables?

swarnim_narayan

Au contraire, nous savons que la plupart des problèmes seront laissés de côté, car il n'y a que beaucoup de problèmes définissables, mais un nombre incalculable de problèmes au total. Plus concrètement, vous vous demandez comment définir des problèmes "vraiment durs", l'analogue théorique de la récursivité des grands cardinaux. Si c'est ce qui vous intéresse, posez une nouvelle question centrée sur cet aspect.

Yuval Filmus

Un problème similaire apparaît lors de la construction de hiérarchies de fonctions récursives à croissance rapide, auquel cas il est connu que dans un certain sens, il n'y a aucun moyen de construire une belle hiérarchie exhaustive.

Yuval Filmus