Facile à l'état des problèmes ouverts dans la théorie de la calculabilité

Question

Je cherchais intéressant et facile à énoncer des problèmes ouverts dans la calculabilité (compréhensible par des étudiants qui prennent leur premier cours de calculabilité) pour donner des exemples de problèmes ouverts (et évidemment, je veux que les étudiants soient en mesure de comprendre le problème sans avoir besoin trop de nouvelles définitions et être aussi intéressant pour eux).

J'ai trouvé cette liste mais les problèmes qu'il semble trop compliqué pour étudiants de premier cycle et aurai besoin des dépenses de temps en donnant des définitions avant d'exposer le problème. Le seul problème que je l'ai trouvé à ce jour est

  

problème Diophantine Est sur des nombres rationnels décidable?

Connaissez-vous un autre intéressant et facile à problème ouvert de l'Etat dans la théorie de la calculabilité?

Answer 1

Une question ouverte au sujet de la fameuse $ poset (D, \ leq_T) $ de degrés Turing est si elle a des automorphismes non triviaux. Cela est, est-il existe une bijection non-identité $ f \ colon D \ à D $ tel que $ a \ b leq_T $ si et seulement si $ f (a) \ leq_T f (b) $ ?.