Łatwe do stwierdzenia otwarte problemy w teorii obliczalności

Szukałem interesujących i łatwych do stwierdzenia otwartych problemów w zakresie obliczalności (zrozumiałych dla studentów pierwszego roku z zakresu obliczeń), aby podać przykłady otwartych problemów (i oczywiście chcę, aby uczniowie byli w stanie zrozumieć problem bez potrzeby zbyt dużej ilości nowych definicje, a także być dla nich interesujące).

Znalazłem tę listę, ale problemy w niej wydają się zbyt skomplikowane dla studentów i będę musiał poświęcić sporo czasu na określenie definicji, zanim przedstawię problem. Jedyny problem, jaki do tej pory znalazłem, to

Czy można rozstrzygać problem diofantyny w stosunku do liczb racjonalnych?

Czy znasz jakiś inny interesujący i łatwy do stwierdzenia otwarty problem w teorii obliczeń?

computability

— Kaveh
źródło

Jaką ilość / rodzaj wcześniejszej wiedzy możemy założyć, np. Na temat automatów, języków formalnych, algorytmów?

— Raphael

@Raphael, możesz założyć znajomość podstawowej teorii obliczeń, np. Oni wiedzą, co obejmuje część dotycząca obliczeń w książce Sipsera „Wprowadzenie do teorii obliczeń”.

— Kaveh

teoria obliczalności jest zdecydowanie bardziej abstrakcyjna niż powiedzmy np. teoria złożoności szczególnie dla studentów. nie słyszałem o całych klasach licencjackich dla teorii obliczalności. co obejmujesz czy masz program nauczania online lub czy jest podobny do innego programu online? pomocne może być zapoznanie się z historią 10. problemu Hilberta, który pozostawał otwarty przez większość XX wieku i jest jednym z „wielkich” zagadnień w tej dziedzinie. niektórzy twierdzą z prawdziwym uzasadnieniem, że jest jednym z najważniejszych XX wieku.

— vzn

$(D, \leq_T)$ $f\colon D \to D$ $a \leq_T b$ $f(a) \leq_T f(b)$

— Carl Mummert
źródło

W jaki sposób ten problem jest interesujący dla przeciętnego studenta? Czy istnieje jakaś znana konsekwencja, która może wynikać z istnienia takiego automorfizmu? Myślę, że motywacja jest najważniejsza przy wprowadzaniu nowych koncepcji, szczególnie jeśli ma tylko pokazać uczniom „słynny otwarty problem”.

— Janoma

@Janoma: motywacją jest zbadanie (i zrozumienie) globalnej struktury stopni Turinga. Łatwo byłoby stwierdzić bez udowodnienia kilku wyników, takich jak gęstość, i wspomnieć o tym jako łatwym do stwierdzenia, ale trudnym do rozwiązania otwartym problemie.

— Carl Mummert