УДК 517.15

С. С. Гончаров, А. Т. Нуртазин

Конструктивные модели полных разрешимых теорий, 125—142.

Дается критерий существования сильно конструктивизируемой простой модели полной разрешимой теории и доказывается, что существуют разрешимые тотально трансцендентные теории, у которых простая и универсальная модели неконструктивизируемы.

УДК 517.11:518.5

А. Н. Дёгтев

О $tt$- и $m$-степенях, 143—161.

Доказывается, что верхняя полурешетка рекурсивно-перечислимых (р.п.) $tt$-степеней не является решеткой и имеет минимальные элементы. Показано также, что простое не гиперпростое множество не может $tt$-сводиться к гипериммунному и что существует р.п. нерекурсивная $tt$-степень, в которой все р.п. множества $m$-эквивалентны. Построена новая серия р.п. $m$-степеней, состоящих из единственной 1-степени. Доказано, что если р.п. нерекурсивная $m$-степень содержит множество, которое не является цилиндром, то она содержит счётное число попарно несравнимых 1-степеней. Наконец, замечено, что под плотно простыми полурекурсивными множествами нет минимальных $m$-степеней.

УДК 519.48

Г. В. Дорофеев

Пример разрешимого, но не нильпотентного (-1,1)-кольца, 162—166.

Построен пример кольца типа (-1,1) разрешимого, но не нильпотентного. Ранее автором (РЖМат, 1972, 6А296) было доказано, что всякое разрешимое (-1,1)-кольцо локально нильпотентно. Таким образом, соотношение между разрешимостью и нильпотентностью в многообразии (-1,1)-колец в точности такое же, как и в многообразиях альтернативных и йордановых колец.

УДК 517.11:518.5

Ю. Л. Ершов, И. А. Лавров

Верхняя полурешетка $L(\gamma)$, 167—189.

Получен ряд достаточных условий неизоморфности верхних полурешеток вычислимых нумераций для конечных семейств рекурсивно-перечислимых множеств. Основой получения этих условий является теорема 1,описывающая тонкую структуру верхней полурешетки $L_{m}$ рекурсивно-перечислимых $m$-степеней, уточняющая и углубляющая ряд уже известных теорем о полурешетке $L_{m}$.

УДК 517.11:518.5

Г. Н. Кобзев

О $btt$-сводимости, 190—204.

Доказывается, что если множества $A$ и $B$ нерекурсивны, $\overline{A}$ или $\overline{B}$ иммунно, $\overline{B}$ рекурсивно-перечислимое (р.п.) множество и $A\leqslant_{btt}B$, то для подходящего нерекурсивного р.п. множества $C$ выполняется $C\leqslant_{btt(1)}A$ и $C\leqslant_{q}B$. Отсюда, используя существование полурекурсивного р.п. множества минимальной $m$-степени, доказываем существование множества минимальной $btt$-степени. Доказано также, что $r$-максимальные множества $A$ и $B$ $btt$-несравнимы, если множества $\overline{A}\cap\overline{B}$ и $(A\setminus В)\cup(B\setminus A)$ бесконечны. Замечено, что существует р.п. множество, $btt$-несравнимое с простыми множествами, а рекурсивно неотделимые р.п. множества не могут $btt$-сводиться к простым множествам.

УДК 51.01:518.5

Ю. Г. Пензин

Неразрешимость полей рациональных функций над полями характеристики 2, 205—210.

Дано решение для частного случая известной проблемы А. И. Мальцева о неразложимости полей рациональных функций над произвольными полями. А именно, доказана неразрешимость полей рациональных функций от одной переменной над конечными полями характеристики 2. В такой постановке задача была сформулирована Ю. Л. Ершовым.

УДК 517.15

М. Г. Перетятькин

Каждое рекурсивно-перечислимое расширение теории линейного порядка имеет конструктивную модель, 211—219.

Теорема. Пусть $T$ — произвольная рекурсивно-перечислимая теория сигнатуры $\sigma=\langle =, <, R_1^1, R_2^1\ldots, R_n^1\rangle$, расширяющая теорию $T_{0}$ линейного порядка сигнатуры $\sigma_{0}=\langle =,<\rangle$. Тогда $T$ имеет конструктивную модель.

Отмечается, что вместе с тем существует наследственно неразрешимое рекурсивно-перечислимое расширение теории $T_{0}$ даже в сигнатуре без дополнительных одноместных предикатов.

УДК 518.5

Л. Н. Победин

Некоторые вопросы обобщенной вычислимости, 220—231.

Рассматривается некоторая нестандартная версия машин с оракулом. Строится оракул, который в определенном смысле решает свою собственную проблему остановки. Оценивается класс функций, вычислимых с этим

УДК 518.45

Е. И. Тимошенко

Некоторые алгоритмические вопросы для метабелевых групп, 232—240.

Положительное решение проблемы тождества для конечно-порожденных метабелевых групп следует иэ их финитной аппроксимируемости. В работе приводится новый алгоритм решения этой проблемы. Кроме того, Для этих групп дается алгоритмическое решение следующей задачи: является ли данный элемент элементом конечного порядка? Отмечается, что приведенные алгоритмы примитивно-рекурсивны.