Логические теории одноместных функций на натуральном ряде

• Автор: Семенов, А.Л.
• Шифр специальности: 01.01.06
• Научная степень: Докторская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 93 c. : ил

Глава I Некоторые общие определения и теоремы
Глава II Монадические теории
Глава III Элементарные теории
Литература
Пусть задана функция -, определенная на натуральном ряде и принимающая значения токе в Д/. Во многих случаях при изучении свойств этой функции оказывается естественным описывать эти свойства на некотором логическом языке L • Так же как и в дрмих подобных ситуациях, например, при описании свойств группы, здесь возникает логическая теория некоторой структуры, т.е* множество всех истинных утверждений о рассматриваемой структуре, записываемых на языке L • Нас будут интересовать свойства функций, связанные с имеющимися на натуральном ряде отношением порядка ^ и операцией сложения + . Таким образом, будут изучаться теории структур /V« ^ ^ > и ( /]/; +, f > . (В силу того, что
порядок ^ можно определить через ■+ , рассмотрение структуры сводится к рассмотрению структуры +) ).
Логический язык при этом мы будем выбирать элементарным (языком первого порядка) или монадическим; в последнем, гонимо средств элементарного языка, допускаются переменные по подмножествам натурального ряда (иначе говоря, по одноместным предикатам) и кванторы по этим переменным.
Центральным для нашего исследования будет вопрос о разрешимости возникающих теорий* Дальнейшее (го сравнению с монадической теорией) расширение логических средств языка, за счет введения кванторов по одноместным функциям из AV в AV и т.д., приводит к неразрешимым логическим теориям независимо от наличия какой--либо структуры на Л/ (Простое доказательство этого известного факта будет приведено в гл. I). Точно так же заведомо неразрешима монадическая теория любой структуры на AV, в сигнатуру которой входит + (см., например, С Е R1 )•
-4'-
Итак, мы приходим к рассмотрению теорий следующих трех классов:
монадические теории структур <(/1/; обозначаемые^ ,
элементарные теории структур ( Д/; ^ ^ обозначаемые 7~$ ,
элементарные теории структур <^/\/; -+, |>* обозначаемые .
Будем использовать аналогичные обозначения 7 и
когда сигнатура вовсе не содержит $ . Элементарную теорию произвольной структуры У будем обозначать ТУ монадическую теорию
Конечно, необходимым условием разрешимости каждой из теорий
АТ/, . rf служит вычислимость функции / • Легко
показать, что это условие не является достаточным даже в случав, когда $ - характеристическая. Пример вычислимой характеристической функции /> для которой теория 7"/ неразрешима,построен в работе Г Т£] , аналогично пример для теории Л- 7*/ был приведен в гВЬ2]
Мы начнем с исторического обзора результатов (включая результаты диссертации), относящихся именно к проблеме разрешимости рассматриваемых теорий. Сначала речь будет идти о монадических теориях, потом - об элементарных.
Как известно (см. [&1]) монадическая, (а, значит, и элементарная) теория структуры ^разрешима. В силу этого разрешима всякая теория^ , где функция ^ определима вЛ'Т • Например, теория уЦ,Т$ разрешима, если есть прибавление единицы. Однако семейство определимых в /7 функций небогато.
Все функции этого семейства имеют вид ос(зс)эс -+ (Ъ (ас) ,где <*, - периодические (как и всюду в дальнейшем, мы считаем, что
периодическая функция может иметь предпериод), с* ; /У —* { 0,11,
|Ъ : 4?. (см. [-513). с другой стороны, как следует из результатов 0СЛИ Для некоторой строго монотонной функции $ теория уЦ ур разрешима, то эта функция определима в уИТ *

в качестве начального состояния управляющего устройства состояния обозначим через Тм . Будем говорить, что преобразователь т униформизует допускающий автомат <01, п, если для всякого сверхспова V/ и всякого ^ 01} Л/)-возможного сверхслова уг выполнено:
1) преобразователь АВ1 ( 01) ЛГ на ВХ°ДН0М сверхслове IV приходит в отвергающее состояние тогда и только тогда, когда ^01, Р не допускает
2) если ^ 01} Г } допускает а] , то (СЮ^/ пре~
образует в допускающий ход автомата 01 на ТлЬ
Теорема 2 (об униформизации). Существует алгоритм, который по всякому допускающему автомату строит униформизующий его преобразователь.
Доказательство. Напомним, что в соответствии с нашим определением преобразователя он представляет собой детерминированный конечный автомат (управляющее устройство), который, читая входное слово, осуществляет изменение своего внутреннего состояния (очередное состояние зависит только от предыдущего состояния и очередного входного символа), а также некоторым образом печатает отрезки выходного слова и формирует память.
Вся работа преобразователя будет следующим образом разбита на этапы. Моменты окончания 1-го, 2-го и т.д. этапов - это в точности последовательные моменты времени, в которые происходит печать непустого слова. Кроме того, первому этапу предшествует особый - нулевой этап. Отрезок входного сверхслова, читаемый на 1-ом этапе, обозначим члл . Работа преобразователя будет организована так, что для некоторого хода автомата ОС на входном сверхслове в конце (р+1)-го этапа ( с - О, К,...) печатается отрезок этого хода, соответствующий отрезку входного сверхслова 'Ьь . В силу определения преобразователя разбиение на этапы должно производиться уп-