|
Vestnik Novosibirskogo Gosudarstvennogo Universiteta. Seriya Matematika, Mekhanika, Informatika, 2008, Volume 8, Issue 1, Pages 71–76
(Mi vngu281)
|
|
|
|
Complexity of Index Sets for Several Classes of Models
E. N. Pavlovsky Novosibirsk State University
Abstract:
When we study questions about computable characterization existence for different classes of models the approach suggested by Goncharov and Knight [1] is effective. It consists of obtaining precise estimations of index sets of such classes in corresponding hierarchy.
For the universal numeration of computable models in non-trivial computable language there were found precise estimations of the following index sets of computable models classes: models with Ehrenfeucht theory ($\Pi^1_1$), models with a theory admitting infinitely many countable models ($\Sigma^1_1$).
Received: 13.02.2008
Citation:
E. N. Pavlovsky, “Complexity of Index Sets for Several Classes of Models”, Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform., 8:1 (2008), 71–76
Linking options:
https://www.mathnet.ru/eng/vngu281 https://www.mathnet.ru/eng/vngu/v8/i1/p71
|
|