Легко изложить открытые проблемы в теории вычислимости

14

Я искал интересные и легко излагаемые открытые проблемы вычислимости (понятные студентам, изучающим первый курс по вычислимости), чтобы привести примеры открытых проблем (и, очевидно, я хочу, чтобы студенты могли понять проблему, не требуя слишком много нового определения, а также быть интересным для них).

Я нашел этот список, но проблемы в нем кажутся слишком сложными для магистрантов, и прежде чем констатировать проблему, придется потратить значительное время на то, чтобы дать определения. Единственная проблема, которую я нашел до сих пор,

Разрешима ли диофантова проблема над рациональными числами?

Знаете ли вы какую-нибудь другую интересную и легко формулируемую открытую проблему в теории вычислимости?

computability Кава
источник
1
Какое количество / вид предварительных знаний мы можем предположить, например, относительно автоматов, формальных языков, алгоритмов?
Рафаэль
@ Рафаэль, вы можете предполагать знание базовой теории вычислимости, например, они знают, что описано в части вычислимости книги Сипсера «Введение в теорию вычислений».
Каве
Теория вычислимости является более абстрактной, чем, например, теория сложности, особенно для студентов. не слышал о целых классах старшекурсников для теории вычислимости. что вы покрываете? У вас есть учебный план онлайн или он похож на другой онлайн? было бы полезно взглянуть на историю 10-й проблемы Гилберта, которая оставалась открытой в течение большей части 20-го века и является одной из «больших» проблем в этой области. некоторые с реальным оправданием говорят, что это один из самых важных событий 20-го века.
ВЗН

Ответы:

4

(D,≤T)е:D→Da≤Tбе(a)≤Tе(б)

Карл Муммерт
источник
1
Чем эта проблема интересна среднему студенту? Есть ли известное следствие, которое может быть получено из существования такого автоморфизма? Я думаю, что мотивация имеет первостепенное значение при внедрении новых концепций, особенно если это только для того, чтобы показать студентам «известную открытую проблему».
Janoma
2
@Janoma: мотивация состоит в том, чтобы изучить (и понять) глобальную структуру степеней Тьюринга. Было бы легко сформулировать без доказательств некоторые результаты, такие как плотность, и упомянуть это как легкое в изложении, но трудное для решения открытой проблемы.
Карл Маммерт