Geodesic
A~computable structure with non-standard computability
Matematičeskie trudy, Tome 21 (2018) no. 2, pp. 3-60.

Voir la notice de l'article provenant de la source Math-Net.Ru

We find an example of a computable admissible set whose level of computability is higher than that of the standard model of Peano arithmetic. As a byproduct, we construct a $1$ model of an undecidable submodel complete theory. 
@article{MT_2018_21_2_a0,
     author = {R. R. Avdeev and V. G. Puzarenko},
     title = {A~computable structure with non-standard computability},
     journal = {Matemati\v{c}eskie trudy},
     pages = {3--60},
     publisher = {mathdoc},
     volume = {21},
     number = {2},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MT_2018_21_2_a0/}
}
TY  - JOUR
AU  - R. R. Avdeev
AU  - V. G. Puzarenko
TI  - A~computable structure with non-standard computability
JO  - Matematičeskie trudy
PY  - 2018
SP  - 3
EP  - 60
VL  - 21
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MT_2018_21_2_a0/
LA  - ru
ID  - MT_2018_21_2_a0
ER  - 
%0 Journal Article
%A R. R. Avdeev
%A V. G. Puzarenko
%T A~computable structure with non-standard computability
%J Matematičeskie trudy
%D 2018
%P 3-60
%V 21
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MT_2018_21_2_a0/
%G ru
%F MT_2018_21_2_a0
R. R. Avdeev; V. G. Puzarenko. A~computable structure with non-standard computability. Matematičeskie trudy, Tome 21 (2018) no. 2, pp. 3-60. http://geodesic.mathdoc.fr/item/MT_2018_21_2_a0/

[1] Avdeev R. R., “O dopustimykh mnozhestvakh vida $\mathbb{HYP}(\mathfrak{M})$ nad rekursivno nasyschennymi modelyami”, Sib. matem. zhurn., 52:6 (2011), 1199–1220 | MR | Zbl

[2] Goncharov S. S., Schetnye bulevy algebry i razreshimost, Nauchnaya kniga, Novosibirsk, 1996 | MR

[3] Goncharov S. S., Ershov Yu. L., Konstruktivnye modeli, Nauchnaya kniga, Novosibirsk, 1999 | MR

[4] Emelichev V. A. i dr., Lektsii po teorii grafov, Nauka, M., 1990 | MR

[5] Ershov Yu. L., Problemy razreshimosti i konstruktivnye modeli, Nauka, M., 1980

[6] Ershov Yu. L., “$\Sigma$-opredelimost v dopustimykh mnozhestvakh”, DAN SSSR, 285:4 (1985), 792–795 | MR | Zbl

[7] Ershov Yu. L., Opredelimost i vychislimost, Nauchnaya kniga, Novosibirsk, 1996 ; Экономика, М., 2000 | MR

[8] Keisler G. Kh., Chen Ch. Ch., Teoriya modelei, Mir, M., 1977

[9] Puzarenko V. G., “O vychislimosti nad modelyami razreshimykh teorii”, Algebra i logika, 39:2 (2000), 170–197 | MR | Zbl

[10] Puzarenko V. G., “Obobschennye numeratsii i opredelimost polya $\mathbb{R}$ v dopustimykh mnozhestvakh”, Vestnik NGU. Ser. mat., mekh., informat., 3:2 (2003), 107–117 | Zbl

[11] Puzarenko V. G., “K vychislimosti na spetsialnykh modelyakh”, Sib. matem. zhurn., 46:1 (2005), 185–208 | MR | Zbl

[12] Puzarenko V. G., “Ob odnoi svodimosti na dopustimykh mnozhestvakh”, Sib. matem. zhurn., 50:2 (2009), 415–429 | MR

[13] Stukachev A. I., “O stepenyakh predstavimostei modelei. I”, Algebra i logika, 46:6 (2007), 763–788 | MR | Zbl

[14] Khisamiev A. N., “O verkhnei polureshetke Ershova $\mathrm{L}_\mathrm{E}$”, Sib. matem. zhurn., 45:1 (2004), 211–228 | MR | Zbl

[15] Barwise J., Admissible Sets and Structures, Springer-Verlag, Berlin–Göttingen–Heidelberg, 1975 | MR | Zbl

[16] Ershov Yu. L., Puzarenko V. G., Stukachev A. I., “HF-Computability”, Computability in Context: Computation and Logic in the Real World, eds. S. B. Cooper, A. Sorbi, Imperial College Press, London, 2011, 169–242 | DOI | MR | Zbl

[17] Harrison-Trainor M., Melnikov A., Miller R., Montalban A., “Computable functors and effective interpretability”, J. Symbolic Logic, 82:1 (2017), 77–97 | DOI | MR | Zbl