Czy istnieje „listowalna” struktura obliczalnego wymiaru? $\omega$?

Nov 29 2020

Powiedzieć, że (policzalnych, obliczalny językowej) struktury$\mathfrak{A}$ma obliczalny wymiar$\omega$ jeśli istnieje nieskończenie wiele obliczalnych kopii pliku $\mathfrak{A}$aż do obliczalnego izomorfizmu. Najprostszym przykładem takiej konstrukcji jest prawdopodobnie porządek liniowy$\mathfrak{O}=(\omega;<)$.

Teraz $\mathfrak{O}$- i wszystkie „naturalne” takie struktury, o których jestem świadomy - spełniają rodzaj warunku „produktywności”, gdzie mając obliczalną sekwencję obliczalnych kopii, możemy obliczalnie utworzyć nową obliczalną kopię, która nie jest obliczalnie izomorficzna z żadną z kopii w sekwencja. Z drugiej strony istnieje więcej sztucznych struktur o obliczalnym wymiarze$\omega$dla których w ogóle nie istnieje nieskończony zestaw obliczalnych kopii, co oczywiście ogranicza produktywność. (Zobacz tutaj, aby uzyskać szczegółowe informacje.)

Interesuje mnie, czy może wystąpić trzecie skrajne zachowanie. Powiedz, że struktura$\mathfrak{A}$można wyświetlić, jeśli istnieje pewna obliczalna sekwencja obliczalnych kopii pliku$\mathfrak{A}$ takie, że każda obliczalna kopia $\mathfrak{A}$jest obliczalnie izomorficzny z jedną z tych kopii. Listowalność wyraźnie zaprzecza obu zachowaniom, o których mowa w poprzednim akapicie.

Czy istnieje struktura listy z obliczalnym wymiarem $\omega$?

Odpowiedzi

4 DanTuretsky Nov 30 2020 at 06:39

Tak. Hirschfeldt i Khoussainov zbudowali taką strukturę. Zobacz początek sekcji 3 na stronie 1208. W rzeczywistości ich lista jest iniekcyjna (do klas równoważności modulo obliczalny izomorfizm). Co ciekawe, rozważają również koncepcję struktury produkcyjnej, chociaż nazywają ją „efektywnie nieskończonym obliczalnym wymiarem”; patrz strona 1200.