|
Алгебра и логика, 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$.
Поступило: 20.03.1979
Образец цитирования:
М. Г. Перетятькин, “Вычисления на машинах Тьюринга в конечно-аксиоматизируемых теориях”, Алгебра и логика, 21:4 (1982), 410–441
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al1779 https://www.mathnet.ru/rus/al/v21/i4/p410
|
Статистика просмотров: |
Страница аннотации: | 77 | PDF полного текста: | 27 |
|