Existe-t-il une structure «listable» de dimension calculable $\omega$?

Question

Disons qu'une structure (dénombrable, en langage calculable)$\mathfrak{A}$a une dimension calculable$\omega$ ssi il existe une infinité de copies calculables de $\mathfrak{A}$jusqu'à l'isomorphisme calculable. L'exemple le plus simple d'une telle structure est probablement l'ordre linéaire$\mathfrak{O}=(\omega;<)$.

Maintenant $\mathfrak{O}$- et toutes les structures "naturelles" de ce type que je connais - satisfont à une sorte de condition de "productivité", où étant donné une séquence calculable de copies calculables, nous pouvons produire de manière informatique une nouvelle copie calculable non isomorphe de manière calculable à l'une des copies dans le séquence. D'autre part, il existe plus de structures artificielles avec une dimension calculable$\omega$pour lequel il n'existe aucun ensemble infini de copies calculables, ce qui empêche bien entendu la productivité. (Voir ici pour plus de détails.)

Je suis intéressé à savoir si un troisième comportement extrême peut se produire. Dites qu'une structure$\mathfrak{A}$est listable ssi il existe une séquence calculable de copies calculables de$\mathfrak{A}$ de telle sorte que chaque copie calculable de $\mathfrak{A}$est calculablement isomorphe à l'une de ces copies. La listabilité contredit clairement les deux comportements mentionnés dans le paragraphe précédent.

Existe-t-il une structure listable avec une dimension calculable $\omega$?

Answer 1

Oui. Hirschfeldt et Khoussainov ont construit une telle structure. Voir le début de la section 3, en page 1208. En fait, leur liste est injective (en classes d'équivalence isomorphisme modulo calculable). Fait intéressant, ils considèrent également l'idée d'une structure productive, bien qu'ils l'appellent "dimension calculable effectivement infinie"; voir page 1200.