Вычисления на машинах Тьюринга в конечно-аксиоматизируемых теориях
М. Г. Перетятькин
Аннотация:
В работе построена полная суперстабильная конечно-аксиоматизируемая теория, на основе которой строятся более сложные теории, в которых интерпретируется работа машины Тьюринга. При этом машина управляет алгеброй Линденбаума теории, а также свойствами простой модели. Таким путем доказаны две теоремы:
Теорема 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