Открытый доступ
Доступ предоставлен
Только для подписчиков
Том 57, № 4 (2018)
- Год: 2018
- Статей: 7
- URL: https://journal-vniispk.ru/0002-5232/issue/view/14550
Article
Categoricity for Primitive Recursive and Polynomial Boolean Algebras
Аннотация
We define a class \( \mathbb{K} \)Σ of primitive recursive structures whose existential diagram is decidable with primitive recursive witnesses. It is proved that a Boolean algebra has a presentation in \( \mathbb{K} \)Σ iff it has a computable presentation with computable set of atoms. Moreover, such a Boolean algebra is primitive recursively categorical with respect to \( \mathbb{K} \)Σ iff it has finitely many atoms. The obtained results can also be carried over to Boolean algebras computable in polynomial time.
251-274
Some Absolute Properties of A-Computable Numberings
Аннотация
For an arbitrary set A of natural numbers, we prove the following statements: every finite family of A-computable sets containing a least element under inclusion has an Acomputable universal numbering; every infinite A-computable family of total functions has (up to A-equivalence) either one A-computable Friedberg numbering or infinitely many such numberings; every A-computable family of total functions which contains a limit function has no A-computable universal numberings, even with respect to Areducibility.
275-288
Generic Amplification of Recursively Enumerable Sets
Аннотация
Generic amplification is a method that allows algebraically undecidable problems to generate problems undecidable for almost all inputs. It is proved that every simple negligible set is undecidable for almost all inputs, but it cannot be obtained via amplification from any undecidable set. On the other hand, it is shown that every recursively enumerable set with nonzero asymptotic density can be obtained via amplification from a set of natural numbers.
289-294
295-308
309-319
Positive Presentations of Families in Relation to Reducibility with Respect to Enumerability
Аннотация
The objects considered here serve both as generalizations of numberings studied in [1] and as particular versions of A-numberings, where ???? is a suitable admissible set, introduced in [2] (in view of the existence of a transformation realizing the passage from e-degrees to admissible sets [3]). The key problem dealt with in the present paper is the existence of Friedberg (single-valued computable) and positive presentations of families. In [3], it was stated that the above-mentioned transformation preserves the majority of properties treated in descriptive set theory. However, it is not hard to show that it also respects the positive (negative, decidable, single-valued) presentations. Note that we will have to extend the concept of a numbering and, in the general case, consider partial maps rather than total ones. The given effect arises under the passage from a hereditarily finite superstructure to natural numbers, since a computable function (in the sense of a hereditarily finite superstructure) realizing an enumeration of the hereditarily finite superstructure for nontotal sets is necessarily a partial function.
320-323
Sessions of the Seminar “Algebra i Logika”
324-326