RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 1982, том 21, номер 4, страницы 410–441 (Mi al1779)

Вычисления на машинах Тьюринга в конечно-аксиоматизируемых теориях

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


Аннотация: В работе построена полная суперстабильная конечно-аксиоматизируемая теория, на основе которой строятся более сложные теории, в которых интерпретируется работа машины Тьюринга. При этом машина управляет алгеброй Линденбаума теории, а также свойствами простой модели. Таким путем доказаны две теоремы:
Теорема 1. Для каждой рекурсивно-перечислимой теории $T$ существует конечно-аксиоматизируемая теория $F$, такая, что алгебры Линденбаума $\mathscr{L}(T)$ и $\mathscr{L}(F)$ рекурсивно изоморфны.
Эта теорема анонсирована Ханфом в РЖМат, 1976, 2А 128, но доказательство еще не опубликовано.
Теорема 2. Существует полная конечно-аксиоматизируемая теория с неконструктивизируемой простой моделью.
Этим решается проблема Харрингтона из РЖМат, 1975, 8А 145.
На основе эффективности конструкции получены оценки сложности некоторых классов предложений, например:
а) $\{n\mid \Phi_n \text{ полна}\}\approx\Pi_2^\circ$,
б) $\{n\mid \Phi_n \text{ полна и имеет простую модель}\}\approx\Pi_3^\circ$,
в) $\{n\mid \Phi_n \text{ полна и имеет неконструктивизируемую простую модель}\}\approx\Pi_4^\circ$.
Здесь $\Phi_n$, $n<\omega_1$ — гёделевская нумерация всех предложений, а запись $A\approx\Sigma$, $A\subseteq\omega$, $\Sigma\subseteq \mathscr{P}(\omega)$ означает, что $A\in\Sigma$ и $A$ $m$-универсально в $\Sigma$.

УДК: 517.11

Поступило: 20.03.1979



Реферативные базы данных:


© МИАН, 2024