Czy „produktywny = wymiar” $\omega$”Dla struktur obliczeniowych?

Nov 29 2020

Analogicznie jak w terminologii dla zestawów , powiedzieć, że (policzalny, język obliczalny) struktura$\mathfrak{A}$jest produktywny, jeśli istnieje obliczalny sposób na poprawne rozwinięcie dowolnej obliczalnej listy obliczalnych typów izomorfizmów obliczalnych kopii$\mathfrak{A}$. To jest,$\mathfrak{A}$ jest produktywne, jeśli istnieje jakaś częściowa funkcja obliczeniowa $F$ takie, że dla wszystkich $a,b$:

Gdyby $W_a=\overline{W_b}$i każdy element $W_a$ to indeks obliczalnej kopii programu $\mathfrak{A}$, następnie $F(a,b)$ jest zdefiniowany i jest indeksem dla obliczalnej kopii programu $\mathfrak{A}$ nie jest obliczeniowo izomorficzna z żadną kopią z indeksami w formacie $W_a$.

(„$W_a=\overline{W_b}$"-bit po prostu to mówi $W_a$ jest w rzeczywistości obliczalnym, a nie tylko ce, zestawem nazw kopii $\mathfrak{A}$, i dajemy ten zestaw $F$ jako zbiór obliczalny, a nie zestaw ce).

Przypomnijmy, że obliczalnym wymiarem konstrukcji jest liczba możliwych do obliczenia kopii, jakie posiada aż do izomorfizmu. Oczywiście każda produktywna struktura musi mieć obliczalną kopię (take$W_a=\emptyset$) i musi mieć obliczalny wymiar $\omega$ (powtarzać $F$odpowiednio). Jednak odwrotność nie jest dla mnie jasna. Moje pytanie brzmi:

Czy każda obliczalna struktura ma obliczalny wymiar $\omega$ produktywny?

Wszystkie „naturalne” przykłady, które przychodzą mi do głowy, są łatwo postrzegane jako produktywne, ale nie widzę tutaj żadnej ogólnie stosowanej zasady. Istnieją różne wyniki w literaturze o podobnym „smaku”, takie jak praca Montalbana nad kopiowaniem / diagonalizacją gier, ale żaden z nich nie wydaje się mieć bezpośredniego zastosowania.

Podejrzewam, że odpowiedź na to pytanie jest „krucha” w tym sensie, że istnieje obliczalna struktura o nieskończonym obliczalnym wymiarze, która jest nieproduktywna, ale każda struktura jest obliczalnie kategoryczna na stożku lub „produktywna na stożku” w odpowiednim sensie; jest to motywowane (ogólną przewrotnością i) kombinacją twierdzenia Goncharova, że ​​istnieją obliczalne struktury o obliczalnym wymiarze ściśle między$1$ i $\omega$i twierdzenie McCoya, że ​​każda struktura jest obliczalnie kategoryczna na stożku lub ma obliczalny wymiar $\omega$ na stożku.

Odpowiedzi

2 DanTuretsky Nov 29 2020 at 13:32

Odpowiedź na twoją pierwszą odpowiedź brzmi: nie.

Moja odpowiedź opiera się na mojej konstrukcji , ale może być prostsze podejście. W tym celu bierzesz obliczalne drzewo$\omega^{<\omega}$ i uzyskaj $\Delta^0_3$transformacja drzewa i obliczalnie kategoryczna struktura w taki sposób, że nietrywialne automorfizmy struktury są zasadniczo ścieżkami przez przekształcone drzewo. Jeśli twoje drzewo startowe nie ma$\Delta^0_3$ścieżek, a następnie oznaczysz określony element struktury stałą, kopie rozszerzonej struktury modulo obliczalny izomorfizm odpowiadają skończonym podzestawom rozszerzalnych węzłów o wysokości 1 w drzewie. Gdybyś miał produktywną funkcję, jak opisujesz, pozwoliłbyś ci wyliczyć nieskończony zestaw rozszerzalnych węzłów (w przekształconym drzewie, z którego możesz wrócić do oryginalnego drzewa poprzez$\Delta^0_3$mapa). Więc jeśli zaczniesz od drzewa z nieskończenie wieloma rozszerzalnymi węzłami o wysokości 1, ale nie$\Delta^0_3$ zestaw z nich miałby wymiar $\omega$ ale nie być produktywnym.

Podzielam twoją intuicję, że to zachowanie powinno zniknąć na stożku.