Алгебра и логика
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Алгебра и логика:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Алгебра и логика, 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
Реферативные базы данных:
Тип публикации: Статья
УДК: 517.11
Образец цитирования: М. Г. Перетятькин, “Вычисления на машинах Тьюринга в конечно-аксиоматизируемых теориях”, Алгебра и логика, 21:4 (1982), 410–441
Цитирование в формате AMSBIB
\RBibitem{Per82}
\by М.~Г.~Перетятькин
\paper Вычисления на машинах Тьюринга в конечно-аксиоматизируемых теориях
\jour Алгебра и логика
\yr 1982
\vol 21
\issue 4
\pages 410--441
\mathnet{http://mi.mathnet.ru/al1779}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=721347}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/al1779
  • https://www.mathnet.ru/rus/al/v21/i4/p410
  • Эта публикация цитируется в следующих 1 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Алгебра и логика Algebra and Logic
    Статистика просмотров:
    Страница аннотации:85
    PDF полного текста:27
    Список литературы:1
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024