Problèmes dont l'état de décidabilité est inconnu mais connu pour être moins difficile que le problème d'arrêt

Existe-t-il des problèmes dont la décidabilité est inconnue, mais il est certain que les problèmes sont moins difficiles que le problème d'arrêt.

computability reference-request undecidability ARi
la source

voir Un problème simple dont la décidabilité n'est pas connue en informatique théorique .

Kaveh

Réponses:

En supposant que par "moins difficile" vous voulez dire "réductible à", alors tout problème connu pour être en mais pas connu pour être en remplit cette condition. $RE$ $R$

Par exemple, prenons le problème PCP avec 4 tuiles, dont la décidabilité est ouverte. C'est un exercice facile de réduire le problème (ou tout autre problème dans RE) à HALT.

Shaull
la source

On ne sait pas que HALT peut être réduit à PCP avec 4 tuiles . Ce dernier est un problème ouvert.

Shaull

Il est mentionné (j'ai écrit que sa décidabilité n'est pas connue, cela implique qu'il n'y a pas de réduction connue de HALT).

Shaull