Сложность вычислений на регистровых машинах со счётчиками тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Савицкий Игорь Владимирович

• Савицкий Игорь Владимирович
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Савицкий Игорь Владимирович

Введение

Краткий обзор результатов по теме диссертации

Общая характеристика работы

Основные понятия

Формулировка основных результатов

Глава 1. Вычисления на регистровых машинах со счётчиками

§1.1. Основные понятия

§1.2. Вычисление простых арифметических функций

§1.3. Моделирование ЯС-машин с константами

§1.4. Стековые регистровые машины

§1.5. Универсальность ЯС-машин

§ 1.6. Класс функций, строго вычислимых на ЯС-машинах

Глава 2. Алгоритмические проблемы, связанные с ИС-машинами

§2.1. ЯС-машины без ограничений на переходы

§ 2.2. Нумерации и сводимость

§ 2.3. Проблема абсолютной эквивалентности

§ 2.4. Слабая проблема эквивалентности

§ 2.5. Сильная проблема эквивалентности и проблема строгой вычислимости

§ 2.6. Проблемы, связанные с определением рекурсивности вычисляемой КС-машиной функции

Глава 3. Упрощение ИС-машин и их арифметизация

§3.1. Вычисления с ограничением на число программ или счётчиков

§3.2. ЯС-машины без неравенств

§3.3. ЯС-машины с ограниченным числом сравнений

§3.4. Арифметизация ЯС-машин

Глава 4. Счётчиковые машины с сумматором

§4.1. Определение счётчиковой машины с сумматором

§ 4.2. Вычисление простых арифметических функций

§ 4.3. Моделирование СБ-машин с константами

§ 4.4. Универсальность СБ-машин

Заключение

Литература

Введение

Краткий обзор результатов по теме диссертации

Начало современной теории алгоритмов положено в середине 1930-х годов опубликованием нескольких формализаций понятия алгоритма [29, 37, 42, 48]. Одно из них принадлежит А. Тьюрингу [48] и использует понятие машины — абстрактного вычислительного устройства, действия которого в целом напоминают действия реального вычислителя. Независимо от А. Тьюринга почти такая же машина была определена Э. Постом [42]. Впоследствии различные варианты машин Тьюринга-Поста предлагались и другими математиками. Помимо машины Тьюринга-Поста наибольшую известность приобрели машины с произвольным доступом к памяти [33] и машины Минского [16].

Перечисленные машины реализуют различные способы работы с данными, но задаваемые ими алгоритмы позволяют решать один и тот же класс задач (иными словами, вычислять один и тот же класс функций). Существует тезис Чёрча-Тьюринга, который утверждает, что этот класс состоит из всех алгоритмически вычислимых функций.

С практической точки зрения множество вычислимых (рекурсивных) функций является слишком широким: в общем случае вычисление может потребовать сколь угодно много времени и ресурсов. В связи с этим появляется вопрос о сложности различных функций. Один из способов оценки сложности функций — это задание некоторого класса дискретных управляющих систем, для которого меру сложности можно ввести естественным образом, и поиск самого простого способа реализации каждой функции управляющими системами из выбранного класса. Таким образом с помощью дискретных управляющих систем можно выделять классы «достаточно простых» функций.

Среди различных классов дискретных управляющих систем можно выделить два крупных типа: схемы и уже упоминавшиеся выше абстрактные вычислительные устройства (машины).

Схема представляет собой набор из большого числа независимо работа-

ющих очень простых элементов, которые тем или иным образом структурно соединены в единую конструкцию, задающую дискретную функцию. Наиболее естественно с помощью схем задаются конечнозначные (например, булевы) функции, но возможно задание и рекурсивных функций. Так, с помощью схем определены сложностные классы предикатов АС0 и ТС0 [28]. В качестве сложности схемы обычно рассматривается число элементов в ней и некоторые другие структурные параметры. Задание функций с помощью схем отражает особенности их аппаратной реализации в технически устройствах (например, в процессоре компьютера). Помимо этого, схемы позволяют моделировать массово-параллельные вычисления с простыми вычислителями и сложной структурой связей между ними.

Абстрактное вычислительное устройство представляет собой модель вычислителя, который шаг за шагом преобразует данные, используя свою программу, и в итоге получает из входных значений значение функции. В качестве меры сложности функции берётся количество времени или памяти, необходимое для её вычисления [35, 46]. Абстрактные вычислительные устройства моделируют последовательные и слабо параллельные алгоритмы со сложными вычислителями.

Новый тип абстрактного вычислительного устройства может вводиться для нескольких целей. Во-первых, устройство может вводить принципиально новый способ работы с данными, а анализ устройства может показать универсальность этого способа. Во-вторых, оно может выделять узкие классы алгоритмов, для реализации которых можно обойтись сравнительно простыми вычислительными средствами. Кроме того, новые вычислительные устройства могут на абстрактном уровне обобщать и формализовать те приемы и методы, которые сложились в современной практике алгоритмических вычислений.

Функциональные системы

Определение классов функций с помощью дискретных управляющих систем предполагает конкретизацию большого количества деталей. В связи с этим встаёт вопрос об «устойчивости» этих классов: отражает выделенный класс действительные сложностные характеристики алгоритмов или он появляется вследствие технических деталей математического формализма? Чтобы доказать «устойчивость» класса, желательно привести для него альтернативное

определение, не привязанное к конкретной машине или конкретному семейству схем. Часто для этой цели используется аппарат функциональных систем, позволяющий получить алгебраическое описание класса. Обзор ряда результатов о взаимосвязи описаний классов с помощью дискретных управляющих систем и с помощью функциональных систем можно найти в [30].

Функциональная система представляет собой класс функций, на котором определён набор операций. Одна из стандартных задач, решаемых для функциональной системы, — это построение её порождающего множества: небольшого множества исходных функций, из которых при помощи операций системы можно получить все функции данного класса. Полученное порождающее множество вместе с набором операций однозначно задаёт рассматриваемый класс функций и называется его алгебраическим описанием. Для классов рекурсивных функций в качестве операций используются операция суперпозиции (подстановка функции на место переменной другой функции) и различные виды рекурсии.

Наиболее известными алгебраически заданными классами являются класс примитивно-рекурсивных функций, впервые описанных Т. Скулемом в начале 1920-х годов [45], и класс частично рекурсивных функций, описанный С. К. Кли-ни в середине 1930-х годов [37]. Оба этих класса очень широки, причём класс частично рекурсивных функций совпадает с классом всех вычислимых функций.

В работе [34] А. Гжегорчик определил иерархию Еп, п Е N0 более узких классов. Каждый класс Еп содержит все функции, получаемые из функций х + 1, /п(х,у) с помощью суперпозиции и ограниченной примитивной рекурсии вида

/0) = g(x), < /О^ У + 1) = у, /(x, y)),

О^ у) < з(x, у).

Функции /п определяются с помощью некоторых рекуррентных соотношений, при этом ¡о(х,у) = х + 1, ¡\(х,у) = х + у, ¡2(х,у) = ху, ¡з(х,у) = ху.

В каждом классе Гжегорчика рост функций определённым образом ограничен (например, в Е1 линейными функциями, а в Е2 — полиномами). Объединение всех классов Еп даёт класс примитивно-рекурсивных функций, но наибольший интерес представляют начальные классы иерархии. В работе [2] А. П. Бельтюков предложил обобщение для классов Гжегорчика путём добав-

ления в набор исходных функций функции шах(х,у) и замены функции /п произвольной функцией.

Классы Гжегорчика с функциями полиномиального роста и выше тесно связаны с классами функций, вычислимых на машинах Тьюринга с ограничениями на размер используемой памяти. Например, Е2 совпадает с классом ^ьшбрасе функций, вычислимых на машинах Тьюринга с использованием линейного объёма памяти (см. [9, 43]), а класс ^рярасе функций, вычислимых с использованием полиномиального объёма памяти, можно задать как обобщённый класс Гжегорчика, содержащий функцию у- (см. [30, 47, 49]). Классы Еп, п ^ 3 могут быть охарактеризованы в терминах вычислений на машинах Тьюринга с ограничениями на память или на время [32].

Один и тот же класс функций может быть задан с помощью нескольких функциональных систем, содержащих различные наборы операций. Однако практически всегда в набор операций входит операция суперпозиции. Поэтому особый интерес представляют функциональные системы, не содержащие никаких других операций. Порождающее множество такой системы называется базисом класса по суперпозиции, и функции из этого множества отражают всю специфику класса. Простой базис по суперпозиции в каком-либо классе является одним из наиболее компактных его описаний.

В некоторых классах функций известны базисы по суперпозиции, состоящие только из простых, преимущественно арифметических функций: например, в классе Е3 иерархии Гжегорчика [11, 41] и в классе ТС0 [4, 39]. В классах Е2 [5] и АС0 [38, 40] построены более сложные (но все еще не очень громоздкие) базисы. Классы АС0 и ТС0, как упоминалось ранее, являются классами предикатов, исходно определёнными с помощью схем [28]. Эти классы естественным образом расширяются до классов функций, соответствующие определения можно найти в [39]. Отметим, что это достаточно малые классы, их предикаты вычислимы на машинах Тьюринга с использованием логарифмического объёма памяти. Тем не менее, эти классы содержат многие используемые на практике функции.

Для получения базисов по суперпозиции существуют различные техники. Нас интересует одна из них — использование машинного описания класса. Работу большинства абстрактных вычислительных устройств можно арифмети-зировать: выразить функционирование машины функциями из данного класса. Этот способ был использован С. С. Марченковым для получения базиса в клас-

се Е2 [12]. Чуть позже этот метод был обобщён на другие классы А. А. Мучником, который ввёл понятие квазиуниверсальной функции [17]. Сложность функций в таких базисах зависит от конструкции арифметизируемой машины.

Абстрактные вычислительные устройства

Абстрактные вычислительные устройства отличаются друг от друга прежде всего устройством своей памяти. Память машины можно разделить на два типа: внутреннюю и внешнюю. Внутренняя память может быть представлена состояниями машины (как у машины Тьюринга) или позицией в коде программы (как у машин с произвольным доступом к памяти). Внутренняя память машины может хранить лишь конечное число значений, но машина имеет полный доступ на её чтение и изменение.

Внешняя память машины может быть устроена самым различным образом. Её особенностью является возможность хранить неограниченное количество информации (столько, сколько потребуется для вычисления). Однако машина не может в любой момент получить доступ к любым элементам внешней памяти: взаимодействие машины с внешней памятью строго регламентировано, и обычно представляет собой последовательность простейших операций.

Наиболее известным типом абстрактных вычислительных устройств являются машины Тьюринга [36, 48]. Внешняя память машины Тьюринга представляет собой бесконечную ленту, в каждой ячейке которой записан символ из конечного алфавита. За один такт машина может считать и изменить только один символ ленты, причём каждый следующий обрабатываемый символ должен быть соседним с предыдущим. Для машины Тьюринга элементарными задачами являются посимвольная обработка слов и работа с двоичными записями чисел, а арифметические операции с числами, требуют некоторых (хотя и не чрезмерных) усилий для реализации. Как было указано ранее, с помощью машин Тьюринга можно задавать классы Гжегорчика, содержащие функции полиномиального роста.

Для анализа практических задач наиболее применима машина с произвольным доступом к памяти [33]. Эта машина имеет бесконечное число регистров, в каждом из которых может быть записано произвольное число. Основной особенностью машины является операция индексации, которая позволяет получить доступ к ячейке памяти, номер которой записан в определённом ре-

гистре. Эта операция соответствует операции получения элемента массива в обычных языках программирования, благодаря чему время вычисления функции на машине с произвольным доступом к памяти даёт хорошую оценку для времени её вычисления на реальном компьютере.

Ещё одним способом хранения информации в устройстве является использование счётчиков. У машины может быть лишь конечное число счётчиков, и каждый счётчик может хранить любое натуральное (или целое) число, а машина может производить со счётчиками те или иные арифметические операции. Этот подход слабо отвечает работе реальных компьютеров, но имеет теоретические преимущества: с помощью таких устройств можно получать машинные описания малых классов функций; кроме того, эти машины проще арифмети-зировать.

Типичным примером абстрактного вычислительного устройства на основе счётчиков являются машины Минского [16], допускающие независимое увеличение и уменьшение (на единицу) значений любых счётчиков, но располагающие довольно слабыми возможностями по считыванию с них информации (возможно лишь сравнение значений счётчиков с нулём). Они также имеют конечную внутреннюю память, на доступ к которой не налагается никаких ограничений.

С помощью машин Минского можно описать класс Е2 и другие классы Гжегорчика [7, 9, 10]. В работе [5] С. А. Волков путём арифметизации машин Минского получил сравнительно простой базис по суперпозиции в классе Е2:

х + 1, ху, х — у, [х/у-, шт(2ж,у), х-, Q(x,pl,p2,Cl,c2,t),

где функция Q получается по схеме /

Q(x,Pl,P2,Cl,C2, 0) = х,

Q(x,Pl,P2,Cl,C2,t + 1) = Q(x,Pl,P2,Cl ,С2,г) + R(p2,C2t),

<

если Q(x,pl,p2, c2,t) Л Я(р1, = 0,

Q(x,Pl,P2,Cl,C2,t + 1) = Q(x,Pl,P2,Cl ^2,^ иначе,

при этом х Л у — поразрядная конъюнкция двоичных представлений чисел х и у, а Я(х, у) — циклический сдвиг двоичного представления числа х на у разрядов вправо. Этот базис интересен тем, что определение функции Q не использует

в явном виде кодирования работы какого-либо вычислительного устройства и является намного менее громоздким, чем описания функций, которые обычно получаются при арифметизации машин.

В работе [2] А. П. Бельтюков ввёл понятие стековой регистровой машины (БЯМ). По сравнению с машинами Минского у БЯМ возможности по записи информации в счётчики (регистры стека) сужены: содержимое счётчиков можно только увеличивать на единицу, при этом содержимое всех «младших» счётчиков становится равным нулю. Кроме того, у БЯМ отсутствует внутренняя память. С другой стороны, эти машины имеют специальный рабочий регистр, в который можно записывать значение любого счётчика; также БЯМ могут сравнивать счётчики на равенство/неравенство друг с другом. Входные значения у БЯМ хранятся в специальных регистрах, доступных только для чтения.

Стековые регистровые машины позволяют получить машинное описание класса Е1 Гжегорчика и ряда других классов, а также доказать отсутствие базиса в классе одноместных функций, принадлежащих Е0 [2, 31]. БЯМ можно арифметизировать для получения базисов в некоторых классах, но при этом получаются достаточно громоздкие функции [8].

Введение диссертации (часть автореферата) на тему «Сложность вычислений на регистровых машинах со счётчиками»

Общая характеристика работы

В 2010 году профессор С. С. Марченков предложил новый тип абстрактных вычислительных устройств — регистровые машины со счётчиками (сокращённо ЯС-машины). От других типов вычислительных машин эти машины отличаются двумя особенностями. Во-первых, ЯС-машины не имеют полноценной внутренней памяти. Во-вторых (и это самое главное отличие), внешняя память ЯС-машин организована таким образом, что в процессе вычисления она изменяется «почти независимо» от программы ЯС-машины.

Внешняя память ЯС-машины состоит из рабочего регистра и произвольного количества счётчиков. Счётчики ЯС-машины изменяются независимо от программы, представляя собой цифры номера текущего такта в позиционной системе счисления с достаточно большим значением основания. ЯС-машина может сравнивать счётчики и рабочий регистр друг с другом (а также с неизменяемыми регистрами, хранящими входные значения), различая, какое из значений больше. Кроме того, машина может заносить значение любого регистра или

счётчика в рабочий регистр. У ЯС-машины может быть конечная внутренняя память (несколько программ), но если машина вышла из некоторого состояния (программы), вернуться в него она уже не сможет.

Чтобы вычисление на ЯС-машине было возможным, ей, помимо обычных входных значений, требуется подать на вход значение ёмкости счётчиков — число, ограничивающее сверху значение каждого счётчика (и являющееся основанием системы счисления, относительно которой счётчики являются цифрами номера текущего такта). При этом к вычислению предъявляется следующее требование: оно должно давать один и тот же результат при любом достаточно большом значении ёмкости счётчиков. Это требование обозначается понятием «строгая вычислимость» и означает, что значение ёмкости счётчиков не может использоваться для кодирования какой-либо дополнительной информации.

В качестве ёмкости счётчиков можно выбирать функцию, зависящую от входных значений, подаваемых машине. Рост этой функции будет естественной мерой памяти, требуемой для вычисления на машине. Таким образом, задавая разные семейства функций ёмкости счётчиков, можно получать различные сложностные классы функций, строго вычислимых на ЯС-машинах.

«Автономность» внешней памяти делает привычные приёмы программирования неприменимыми для ЯС-машин. Обычно вычисление представляет собой последовательность «активных» операций машины с данными. Вычисление ЯС-машины проходит иначе: машина ждёт, пока в счётчики сами собой не попадут нужные значения; она лишь «отлавливает» определённые моменты и сохраняет значение какого-либо счётчика в рабочем регистре.

Из-за ограничений своей внутренней памяти ЯС-машина должна производить любой циклический процесс без использования переходов к другим программам. Таким образом, несколько программ могут использоваться только для подготовки данных к основному процессу и для обработки результата.

На протяжении большей части вычисления ЯС-машина может управлять лишь одной ячейкой памяти — рабочим регистром. У ЯС-машины нет возможности «надёжно» сохранить какой-либо промежуточный результат: значение любого счётчика рано или поздно поменяется (не говоря уже о том, что машина не может изменить счётчик напрямую, а может только дождаться, пока он изменится сам собой), а рабочий регистр может хранить только одно значение, которое будет «стёрто» при занесении туда любого нового числа.

Указанные особенности позволяют утверждать, что ЯО-машины задают особый способ работы с данными, значительно отличающийся от принципов работы известных вычислительных устройств. Даже при вычислении простых арифметических функций на ЯО-машинах возникают затруднения, так как нет возможности применить какие-либо стандартные техники программирования.

Отметим, что похожая машина с автономно работающими счётчиками и понятием строгой вычислимости введена в [1], но она, в отличие от ЯО-машин, имеет полноценную внутреннюю память. Это означает наличие второй (пусть и конечной) ячейки памяти, что практически устраняет сложности в построении программ для машины.

Помимо необычного способа работы с данными, в ЯО-машинах представляет интерес возможность их арифметизации. При арифметизации большинства машин требуется определённым образом кодировать текущее состояние памяти (конфигурацию) машины и нужны громоздкие функции, которые могут отразить всё многообразие возможностей изменения машиной своей конфигурации.

В случае ЯО-машин имеется только одна ячейка памяти, которую может менять машина, все остальные же определяются по номеру текущего такта и фиксированным извне данным. Поэтому при арифметизации ЯО-машин не требуется использовать специальные функции работы с кодами конфигураций. Это даёт основание предположить, что использование ЯО-машин может дать достаточно простые базисы по суперпозиции в классах функций, которые задаются этими машинами.

Исходя из изложенных выше особенностей ЯО-машин, была предложена программа по исследованию класса функций, строго вычислимых на ЯО-машинах. Она включала сравнение сложности вычисления функций на ЯО-машинах и на некоторых других вычислительных устройствах, а также содержала ряд вопросов, которые формулировались специально для ЯО-машин: сложность решения некоторых алгоритмических проблем, связанных с вычислением функций на ЯО-машинах; влияние количества счётчиков и программ на объём получаемого класса вычислимых функций; возможность обобщений и упрощений в определении ЯО-машин; возможность использования ЯО-машин для получения результатов алгебраического характера в теории рекурсивных функций.

Следуя этой программе, перечислим основные вопросы, решению которых посвящена настоящая диссертация.

1. Охарактеризовать класс функций, которые строго вычислимы на ЯС-ма-шинах с рекурсивной ёмкостью счётчиков.

2. Описать сложностные классы функций, строго вычислимых ЯС-маши-нами при различных способах выбора ёмкости счётчиков. В частности, определить класс функций, которые строго вычислимы на ЯС-машинах без ограничений на ёмкость счётчиков.

3. Найти соотношение между сложностью вычисления функций на ЯС-ма-шинах и на ближайших к ним стековых регистровых машинах.

4. Определить сложность ряда алгоритмических проблем, которые можно сформулировать для ЯС-машин.

5. Выяснить влияние числа программ и счётчиков на объём класса функций, строго вычислимых на ЯС-машинах.

6. Исследовать различные вычислительные устройства, которые можно получить с помощью модификации ЯС-машин.

7. Применить результаты о вычислениях на ЯС-машинах для построения простых базисов по суперпозиции в «малых» классах рекурсивных функций.

Характеристика первой главы

В главе 1 исследуются вычислительные возможности ЯС-машин. Прежде всего, строятся КС-машины для строгого вычисления простых арифметических функций: х + у, х — у = шах(х — у, 0), ху, \_х/у\. Эти машины достаточно экономны: каждая из них имеет лишь одну программу. Они демонстрируют основную арифметическую технику, которая используется при программировании ЯС-машин, — синхронное увеличение счётчика и рабочего регистра.

В §1.3 показано, что в ЯС-машину можно добавить дополнительные регистры («константы»), хранящие фиксированные значения вида с • \£/Н\, где £ — значение ёмкости счётчиков текущего вычисления. Эти числа разбивают

множество значений, которые могут попасть в рабочий регистр, на несколько сегментов, что позволяет значению рабочего регистра кодировать два числа: одно число произвольной величины и одно число, ограниченное константой.

Отметим, что из доказательства теоремы 8 (§ 2.1) следует, что при вычислении функций на ЯО-машинах с константами достаточно использовать лишь одну программу. Таким образом, несколько программ ЯО-машине требуется только для того, чтобы перед вычислением сформировать некоторые (не связанные напрямую с данным вычислением) константы. Основной процесс вычисления целиком реализуется одной программой.

Центральным результатом главы 1 является моделирование вычислений БЯМ с помощью ЯО-машин. Программу БЯМ можно привести к виду, в котором она работает схоже с ЯО-машиной: на каждом такте заносит новое значение в рабочий регистр и изменяет счётчики. Кроме того, обе машины изменяют счётчики только путём увеличения некоторого счётчика на единицу и обнуления младших счётчиков. Однако ЯО-машина выбирает увеличиваемый счётчик по стандартному правилу, не зависящему от программы машины, тогда как БЯМ может увеличить произвольный счётчик. Чтобы промоделировать увеличение нужного счётчика стековой регистровой машиной, нужно хранить номер увеличиваемого счётчика в рабочем регистре (вместе со значением рабочего регистра БЯМ) и «дождаться» его увеличения. В результате для моделирования вычисления БЯМ требуется ёмкость счётчиков, в константу раз большая, чем зона моделируемой машины.

Моделирование БЯМ с помощью ЯО-машин позволяет получить целый ряд результатов о вычислении функций на ЯО-машинах. Во-первых, ЯО-машины оказываются универсальными: на них можно строго вычислить любую частично-рекурсивную функцию (с вычислимой функцией ёмкости счётчиков). Во-вторых, ЯО-машины с ограничениями на рост ёмкости счётчиков позволяют вычислять произвольные функции из определённых классов Гжегорчика. Например, линейные ёмкости счётчиков дают возможность вычислять любые функции из класса Е\ а полиномиальные ёмкости — функции из Е2. Аналогичный результат можно получить для класса ^рбрасе, а также для ряда других классов, которые могут быть представлены как обобщённые классы Гжегорчи-ка [2].

В рамках диссертации не проводится обратное моделирование: моделиро-

вание вычислений ЯС-машин с помощью БЯМ. В связи с этим многие результаты о связи классов функций, строго вычислимых ЯС-машинами с определёнными ёмкостями счётчиков, и классов Гжегорчика сформулированы как односторонние. Тем не менее (особенно с учётом §2.1 и §3.2) это моделирование не представляется проблематичным и требует лишь технической работы. Поэтому можно говорить о совпадении указанных классов.

Все результаты первой главы вплоть до последнего параграфа касаются случая, когда используемая ЯС-машиной функция ёмкости счётчиков вычислима. В связи с этим возникает следующий принципиальный вопрос: какие функции могут строго вычислять ЯС-машины, если никак не ограничивать выбор ёмкости счётчиков? Оказывается, в этом случае ЯС-машины могут строго вычислять и некоторые невычислимые функции, хотя этот класс невычислимых функций достаточно узок.

В § 1.6 класс всех функций, строго вычислимых на ЯС-машинах, характеризуется в терминах иерархии Клини-Мостовского. Так, класс всех всюду определённых предикатов, характеристические функции которых строго вычислимы на ЯС-машинах, совпадает с классом Д2 иерархии Клини-Мостовского. Класс всех функций, строго вычислимых на ЯС-машинах, можно описать с помощью классов £2, П2 и операции минимизации.

Отметим, что этот результат перекликается с известным результатом теории рекурсивных функций (см. [19, 44]): класс Д2 совпадает с классом предикатов вида р(х,Т(х)), где р(х,у) — разрешимый всюду определённый предикат, а Т(х) — всюду определённая функция такая, что для любой всюду определённой функции Т'(х) ^ Т(х) верно р(х,Т'(х)) = р(х,Т(х)). Предикат р(х,Т(х)) ещё обозначают Ншу р(Х,у). Указанное определение близко к определению строго вычислимой на ЯС-машине функции.

Можно сказать, что при вычислении без ограничений на ёмкость счётчиков ЯС-машина имеет доступ к числу (значение ёмкости счётчиков), которое «достаточно велико» независимо от того, какая именно величина будет «достаточной» для данного вычисления. Понятно, что алгоритмически определить такое число невозможно; доступ к этому числу характеризует предикаты из класса Д2. Тем не менее, доступ к этому «достаточно большому числу» не вводится в ЯС-машину искусственным образом; он предполагается самой конструкцией ЯС-машины, которая требует введения понятия строгой вычислимости.

Характеристика второй главы

В §2.1 рассматривается отдельный вопрос о возможности добавления в ЯО-машину внутренних состояний (т. е. снятия ограничений на переходы между программами) и показывается, что это можно сделать с незначительным «искажением» результата работы машины: для моделирования работы ЯО-машины с внутренними состояниями достаточно увеличить ёмкость счётчиков в константу раз. Этот результат используется в технических построениях основной части данной главы. Кроме того, доказательство этого результата демонстрирует возможность моделирования произвольной ЯО-машины с помощью ЯО-машины с константами и одной программой.

Вторая глава посвящена алгоритмическим проблемам, связанным с ЯО-машинами. При исследовании абстрактных вычислительных устройств часто рассматривают алгоритмические проблемы, касающиеся этих устройств. Сложность решения этих проблем характеризует сложность анализа данного типа устройств. Для универсальных вычислительных устройств содержательные алгоритмические проблемы обычно оказываются неразрешимыми.

Типичным примером такой проблемы является проблема останова машины Тьюринга:

Пусть на вход дана программа машины Тьюринга. Верно ли, что эта машина остановится при запуске на ленте с кодом числа 0?

Известно, что эта проблема неразрешима и т-полна в классе иерархии Клини-Мостовского (что указывает на достаточно низкую её сложность среди неразрешимых проблем).

Для ЯО-машин проблема останова бессодержательна: любая ЯО-машина всегда останавливается. Но естественно задать ряд других вопросов, связанных с работой ЯО-машины при различных значениях ёмкости счётчиков. В диссертации рассматривается ряд алгоритмических проблем подобного рода с точки зрения их положения в иерархии Клини-Мостовского. Например, проблема строгой вычислимости:

Пусть дана ЯО-машина. Верно ли, что эта машина строго вычисляет некоторую всюду определённую функцию?

Доказывается, что эта проблема т-полна в классе П3.

Помимо этого, рассматриваются алгоритмические проблемы, определённые только для части ЯО-машин. Таковой является, например, проблема ре-

курсивности строго вычислимой на ЯО-машине функции:

Пусть дана ЯО-машина, строго вычисляющая некоторую всюду определённую функцию. Является ли эта функция вычислимой?

Поскольку эти алгоритмические проблемы выражаются частичными предикатами, они не включены в какие-либо классы иерархии Клини-Мостовского. Тем не менее, их сложность можно охарактеризовать в терминах этой иерархии: так, доказывается, что «самое простое» доопределение проблемы рекурсивно-сти строго вычислимой на ЯО-машине функции т-полно в £3.

Характеристика третьей главы

Хотя ЯО-машины имеют слабые возможности по изменению данных во внешней памяти (они могут только записывать значение в рабочий регистр), их возможности по чтению данных из внешней памяти достаточно сильны: за один такт ЯО-машина может сравнить значения всех своих регистров и счётчиков и определить, какие из них больше, а какие меньше. В связи с этим представляют интерес варианты упрощения конструкции ЯО-машины, не сужающие её вычислительных возможностей.

В § 3.1 рассматривается вопрос об ограничении количества программ и счётчиков машины. С использованием универсальной ЯО-машины доказывается, что при ограничении числа счётчиков всех ЯО-машин определённой глобальной константой ЯО-машины всё ещё позволяют строго вычислять любую вычислимую функцию. Такое же утверждение доказывается и для ограничения количества программ.

Остальные параграфы третьей главы можно рассматривать как этапы арифметизации ЯО-машин. В ходе этой арифметизации строятся промежуточные «упрощённые» варианты ЯО-машин и, в конце концов, работа одного из вариантов выражается с помощью арифметических функций. Общая схема ариф-метизации ЯО-машин близка к схеме С. А. Волкова, применённой к машинам Минского [5], и позволяет получить базисы по суперпозиции в некоторых классах функций.

Наиболее близки к ЯО-машинам стековые регистровые машины. ЯО-машины получаются из БЯМ путём ограничения возможностей изменения счётчиков (счётчики БЯМ и ЯО-машин изменяются схожим образом, но БЯМ управляет изменением своих счётчиков, а ЯО-машина — нет). Вместе с тем БЯМ может

проверять лишь равенство/неравенство значений своих регистров и счётчиков, а ЯС-машина «видит», какие значения больше, а какие меньше; причём в построениях первой главы эта возможность существенно используется.

В § 3.2 показывается, что замена у ЯС-машины возможности сравнивать свои регистры и счётчики с результатом больше/меньше/равно на возможность проверять их на равенство/неравенство не влияет на вычислительные возможности ЯС-машин. Этот результат является естественным первым шагом в ариф-метизации ЯС-машин.

Помимо этого, из §1.3, §2.1 и §3.2 следует совпадение вычислительных возможностей простых ЯС-машин и ЯС-машин с константами, но без возможности различать < и > и с одной программой (при этом переход от одной машины к другой требует не более, чем линейного изменения ёмкости счётчиков). Это упрощает задачу моделирования ЯС-машин с помощью БЯМ (хотя в диссертации это моделирование не проводится).

Первым шагом в схеме арифметизации С. А. Волкова является переход к машинам Минского, которые на каждом такте используют информацию только об одном своём счётчике. Аналогичным шагом для ЯС-машин является ограничение числа сравнений, производимых на каждом такте.

В § 3.3 вводится понятие ЯС-машины с ограниченным числом сравнений. Эта машина на каждом такте производит лишь два сравнения: сравнивает какой-либо регистр или счётчик с рабочим регистром г и сравнивает два регистра/счётчика (кроме г) между собой. Если оба равенства выполняются, то машина заносит в г значение некоторого счётчика. В противном случае она не меняет значение рабочего регистра.

Указанная машина на каждом такте работает с разными регистрами и счётчиками. Для обеспечения этого необходимо задать последовательность команд этой машины, которую она выполняет циклически. Таким образом, во внутренней памяти машины хранится позиция внутри программы, но, поскольку она не управляет сменой команд, у неё всё равно нет полноценных внутренних состояний. Отметим также, что ЯС-машина с ограниченным числом сравнений имеет регистры-константы.

Как доказано в §3.3, ЯС-машина с ограниченным числом сравнений позволяет вычислять те же функции, что и простая ЯС-машина.

Наконец, в § 3.4 проводится арифметизация ЯС-машин с ограниченным

числом сравнений. Для обеспечения циклического процесса вычисления используется функция Ql(x,T,a,b,c,d,t) из класса Е0, задаваемая с использованием примитивной рекурсии и имеющая достаточно простой вид.

Переменная х этой функции должна кодировать значения входных регистров и констант ЯО-машины, переменная Т — ёмкость счётчиков, переменные а,Ь,с^ — номера регистров/счётчиков программы ЯО-машины. Переменная t обозначает номер текущего такта. Для указанного кодирования достаточно использовать функции х + 1, х + у, ху. С помощью некоторых технических ухищрений можно уменьшить число переменных и перейти от функции Ql(x,T,a,b,c,d,t) к Q2(x,T,t). Выпишем эту функцию:

Q2(x,T, 0) = 0,

Q2(x,T,t + 1) = (х + + 3}т ]т,

< если Q2(x,T,t) = (x + + 2}т]т

и (х + ^[х{Щт]т = (х + t)[x{4t + 1}т]т,

Q2(x, T,t + 1) = Q2(x, ^ ^ иначе.

Через х[у]т обозначаем у-ю цифру числа х в позиционной системе счисления с основанием T; а через х{у}т — значение х[гш(у, 1епт(х))]т, где 1епт(х) — число цифр в числе х в системе счисления с основанием T, а гш(х, у) — функция взятия остатка от деления.

С помощью арифметизации ЯО-машин строятся базисы по суперпозиции в двух классах: базис класса Е2 составляют функции Q2(x,T,t), х + 1, х + у, ху, а базис класса ^рягасе составляют функции Q2(x,T,t), х + 1, х+у, ху, х1еП2(х).

В принципе, этот метод построения базиса можно применить и к ряду других классов функций, определяемых с помощью БЯМ и содержащих функцию ху. Для этого к функциям Q2(x,T,t), х + 1, х + у, ху нужно добавить ещё одну функцию, характеризующую рост функций из данного класса.

По сравнению с базисом Е2, построенным С. А. Волковым, базис, построенный в этой диссертации содержит более простые «вспомогательные» функции; кроме того, его функция Q зависит от меньшего числа переменных и принадлежит Е 0.

Возможность определить в классе Е2 существенно более простой базис не представляется вероятной. Все простые арифметические функции (х + у,

х — у, ху, \х/у\, \log2х\ и пр.), кроме экспоненты, принадлежат классу ТС0, который строго вложен в Е2 (см. [28, 30, 46]), поэтому в базисе класса Е2 должна присутствовать более сложная функция.

Характеристика четвёртой главы

В четвёртой главе ЯС-машины применяются для исследования счётчико-вых машин с сумматором.

Счётчиковые машины с сумматором (СБ-машины) схожи с ЯС-машинами. Отличие состоит в том, что СБ-машины вместо рабочего регистра имеют регистр-сумматор. Они не могут заносить в сумматор значения других регистров и счётчиков, но могут прибавлять к его текущему значению произвольные константы (сложение производится по модулю значения ёмкости счётчиков, что обеспечивает «немонотонность» процесса).

Конструкция СБ-машин лучше приспособлена для арифметических операций, чем конструкция ЯС-машин. Так, операция сложения СБ-машинами производится тривиально, а в случае ЯС-машин требует специальной техники. Однако воспроизвести на СБ-машинах работу каких-либо других устройств достаточно сложно: поскольку СБ-машины не могут за один такт занести произвольное значение в рабочий регистр, они не могут в любой момент «переключиться» в другой режим вычисления.

В четвёртой главе диссертации вычислительные возможности СБ-машин исследуются по схеме, схожей с исследованием вычислительных возможностей ЯС-машин в первой главе. Сначала строятся программы для вычисления простых арифметических функций. Затем в СБ-машину добавляются регистры-константы. После этого с помощью СБ-машин моделируются вычисления ЯС-машин, что позволяет СБ-машинам задавать те же классы функций, что задаются ЯС-машинами.

Основные понятия

Прежде чем формулировать результаты диссертации, приведём используемые в них определения. Часть этих определений, за исключением наиболее общепринятых, будет продублирована в основном тексте работы. Приводимые определения в основном следуют [8].

Будем использовать символ N для обозначения множества натуральных чисел {1, 2,...}, положим No = N U {0}. Там, где это не вызывает недоразумения, будем использовать обозначение x вместо х1,... ,xn. По умолчанию все рассматриваемые далее функции считаем функциями натурального аргумента (т.е. функциями из множества {f: Nn ^ No, n Е N}). Рассматриваются также частичные функции, определённые не на всём множестве N0.

Предикатами называем отображения вида р: Nn ^ {true,false}, n Е N (могут быть частичными). Характеристической функцией частичного предиката р(х) называем функцию

хДх) = <

0, если р(х) = false,

1, если р(х) = true,

не определено, если р(х) не определено.

Функцию |_х/у\ доопределяем нулём при у = 0. При помощи гт(х,у) обозначаем остаток от деления х на у (0 при у = 0). Пусть

х — у, если х ^ у, I 0, если х = 0,

х — у = \ sg х = <

0 иначе; I 1, если х > 0.

Обозначим I = {/"(х): N9 ^ М0, г = 1,п,п Е М}, где /"(х) = хг.

Операции над функциями и классы функций

Функция /(х) получается из функций д1(х),... ,дт+1(х) и попарно несовместных предикатов ^(х),... , рт(х) с помощью операции разбора случаев по предикатам, если

f (х) = {

д^х), если р1(х) = true,

дт(х), если рт(х) = true, gm+1 (х) иначе.

Считаем, что операция суперпозиции включает в себя отождествление и перестановку переменных, а также подстановку функции на место переменной

другой функции. При попадании неопределённого значения на место любого аргумента функции считаем, что значение функции не определено.

Функция I(х,у) получается из функций д(х), Н(х,у,г), 3(х,у) с помощью операции ограниченной примитивной рекурсии, если для любого набора х € N и любого у € М0 выполняются соотношения

/(х, 0) = g(x),

1(х, у +1) = Мх y, /(x,y)), 1(х^ у) < 3(х, у).

Пусть р(х, у) — частичный предикат натурального аргумента. Тогда I(х) получается путём применения операции минимизации по у к р(х,у), если

наименьшему числу у' € М0

такому, что р(х,у') истинно, а р(х,у) определено при у < у', если такое у' существует, не определено иначе.

I (х) = <

Обозначается I(х) = (ду)р(х,у).

Класс функций С называется замыканием системы функций Б относительно набора операций О, если С содержит те и только те функции, которые можно получить из функций системы Б с помощью последовательного применения операций из О. Система Б в этом случае называется полной системой в классе С относительно набора операций О.

Система функций Б называется базисом по суперпозиции в классе функций С, если С является замыканием системы Б относительно суперпозиции.

Класс Е0 иерархии Гжегорчика — это замыкание системы 0, х + 1, I относительно операций суперпозиции и ограниченной примитивной рекурсии.

Класс Е1 иерархии Гжегорчика — это замыкание системы 0, х +1, х + у, I относительно операций суперпозиции и ограниченной примитивной рекурсии.

Класс Е2 иерархии Гжегорчика — это замыкание системы 0, х + 1, х • у, I относительно операций суперпозиции и ограниченной примитивной рекурсии.

Список литературы диссертационного исследования кандидат наук Савицкий Игорь Владимирович, 2021 год

Литература

1. Бельтюков А. П. Итеративное описание класса E1 иерархии Гжегорчика // Записки научных семинаров ЛОМИ АН СССР. 1976. Т. 60. С. 3-14.

2. Бельтюков А. П. Машинное описание и иерархия начальных классов Гжегорчика // Записки научных семинаров ЛОМИ АН СССР. 1979. Т. 88. С. 30-46.

3. Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. М.: МЦНМО, 2017. 160 с.

4. Волков С. А. Порождение некоторых классов рекурсивных функций суперпозициями простых арифметических функций // Доклады Академии Наук. 2007. Т. 415, № 4. С. 439-440.

5. Волков С. А. Пример простой квазиуниверсальной функции в классе E2 иерархии Гжегорчика // Дискретная математика. 2006. Т. 18, № 4. С. 31-44.

6. Клини С. К. Математическая логика. М.: Мир, 1973. 480 с.

Пер. по изд.: Kleene S.C. Mathematical logic. New York: John Wiley & Sons, 1967.

7. Марченков С. С. Базисы по суперпозиции в классах рекурсивных функций // Математические вопросы кибернетики. Т. 3. М.: Физматлит, 1991. С. 115-139.

8. Марченков С. С. Классы элементарных рекурсивных функций. М.: Физматлит, 2017. 136 с.

9. Марченков С. С. О сложности класса E2 Гжегорчика // Дискретная математика. 2010. Т. 22, № 1. С. 5-16.

10. Марченков С. С. Об ограниченных рекурсиях // Mathematica Balkanica. 1972. Т. 2. С. 124-142.

11. Марченков С. С. Суперпозиции элементарных арифметических функций // Дискретный анализ и исследование операций. 2006. Т. 13, № 4. С. 33-48.

12. Марченков С. С. Устранение схем рекурсий в классе E2 Гжегорчика // Математические заметки. 1969. Т. 5, № 5. С. 561-568.

13. Марченков С. С., Савицкий И. В. Вычисления на счетчиковых машинах с сумматором // Вестник Московского Университета. Серия 15. Вычислительная математика и кибернетика. 2018. № 1. С. 31-39.

14. Марченков С. С., Савицкий И. В. Машины в теории вычислимых функций. М.: МАКС Пресс, 2018. 88 с.

15. Марченков С. С., Савицкий И. В. Функции, вычислимые регистровыми машинами со счётчиками // Ломоносовские чтения: научная конференция: тезисы докладов (Москва, 18-27 апреля 2016 г.). М.: МАКС Пресс, 2016. С. 86.

16. Минский М. Л. Вычисления и автоматы. М.: Мир, 1971. 368 с.

Пер. по изд.: Minsky M.L. Computation: finite and infinite machines. En-glewood Cliffs, NJ: Prentice-Hall, 1967. 334 p.

17. Мучник А. А. О двух подходах к классификации рекурсивных функций // Проблемы математической логики: сложность алгоритмов и классы вычислимых функций. М.: Мир, 1970. С. 123-138.

18. Пахомов С. В. Машинно-независимое описание некоторых машинных классов сложности // Записки научных семинаров ЛОМИ АН СССР. 1979. Т. 88. С. 176-185.

19. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972. 624 с.

Пер. по изд.: Rogers H. Theory of recursive functions and effective computabil-ity. New York: McGraw-Hill, 1967. 503 p.

20. Савицкий И. В. Арифметизация регистровых машин со счетчиками // Вестник Московского Университета. Серия 15. Вычислительная математика и кибернетика. 2020. № 3. С. 30-42.

21. Савицкий И. В. Арифметизация регистровых машин со счётчиками // Материалы XIII Международного семинара «Дискретная математика и ее приложения» имени академика О. Б. Лупанова (Москва, 17-22 июня 2019 г.). М.: Изд-во механико-математического факультета МГУ, 2019. С. 178-181.

22. Савицкий И. В. Вычисления на регистровых машинах со счетчиками // Дискретная математика. 2017. Т. 29, № 1. С. 95-113.

23. Савицкий И. В. Некоторые алгоритмические проблемы, связанные с регистровыми машинами со счётчиками // Сборник статей молодых ученых ВМК МГУ. Т. 14. М.: МАКС Пресс, 2017. С. 18-48.

24. Савицкий И. В. Регистровые машины со счётчиками // Доклады Академии Наук. 2017. № 4. С. 387-388.

25. Савицкий И. В. Регистровые машины со счётчиками // Алгебра и теория алгоритмов: Всероссийская конференция, посвященная 100-летию факультета математики и компьютерных наук Ивановского государственного университета: сборник материалов (Иваново, 21-24 марта 2018 г.). Иваново: Иван. гос. ун-т, 2018. С. 148-149.

26. Савицкий И. В. Регистровые машины со счётчиками и невычислимые функции // Тихоновские чтения: научная конференция: тезисы докладов (Москва, 23-27 октября 2017 г.). М.: МАКС Пресс, 2017. С. 61-62.

27. Савицкий И. В. Устранение неравенств в регистровых машинах со счетчиками // Вестник Московского Университета. Серия 15. Вычислительная математика и кибернетика. 2019. № 3. С. 45-51.

28. Allender E., Loui M.C., Regan K.W. Complexity Classes // Algorithms and theory of computation handbook. General concepts and techniques. Boca Raton, Fla: Taylor & Francis, 2009. P. 597-620.

29. Church A. An Unsolvable Problem of Elementary Number Theory // American Journal of Mathematics. 1936. Vol. 58, no. 2. P. 345-363.

30. Clote P. Computation Models and Function Algebras // Handbook of Com-putability Theory. Amsterdam: Elsevier Science B. V., 1999. P. 589-681.

31. Clote P. Nondeterministic stack register machines // Theoretical Computer Science. 1997. Vol. 178, no. 1. P. 37-76.

32. Cobham A. The Intrinsic Computational Difficulty of Functions // Proceedings of the 1964 International Congress for Logic, Methodology, and the Philosophy of Science. Amsterdam: North-Holland Publishing, 1965. P. 24-30.

33. Cook S. A., Reckhow R. A. Time Bounded Random Access Machines // Journal of Computer and System Sciences. 1973. Vol. 7. P. 354-375.

34. Grzegorczyk A. Some classes of recursive functions // Rozprawy Matem-atyzne. Vol. 4. Warzawa, 1953.

Русск. пер.: Гжегорчик А. Некоторые классы рекурсивных функций // Проблемы математической логики: сложность алгоритмов и классы вычислимых функций. М.: Мир, 1970. С. 9-49.

35. Hartmanis J., Stearns R. On the Computational Complexity of Algorithms // Transactions of the American Mathematical Society. 1965. Vol. 117. P. 285306.

Русск. пер.: Хартманис Д., Стирнз Р. Е. О вычислительной сложности алгоритмов // Кибернетический сборник (новая серия). Т. 4. М.: Мир, 1967. С. 57-85.

36. Jiang T., Li M., Ravikumar B. Basic Notions in Computational Complexity // Algorithms and theory of computation handbook. General concepts and techniques. Boca Raton, Fla: Taylor & Francis, 2009. P. 527-548.

37. Kleene S. C. General recursive functions of natural numbers // Mathematische Annalen. 1936. Vol. 112, no. 1. P. 727-742.

38. Mazzanti S. Bases for AC0 and Other Complexity Classes // Fundamenta Informaticae. 2015. No. 4. P. 433-460.

39. Mazzanti S. CRN Elimination and Substitution Bases for Complexity Classes // Fundamenta Informaticae. 2012. No. 1. P. 29-58.

40. Mazzanti S. New substitution bases for complexity classes // Mathematical Logic Quarterly. 2019. Vol. 66, no. 1. P. 1-14.

41. Mazzanti S. Plain Bases for Classes of Primitive Recursive Functions // Mathematical Logic Quarterly. 2002. Vol. 48, no. 1. P. 93-104.

42. Post E. L. Finite Combinatory Processes-Formulation 1 // The Journal of Symbolic Logic. 1936. Vol. 1, no. 3. P. 103-105.

43. Ritchie R. W. Classes of predictably computable functions // Transactions of the American Mathematical Society. 1963. Vol. 106. P. 139-173.

Русск. пер.: Ричи Р. В. Классы предсказуемо вычислимых функций // Проблемы математической логики: сложность алгоритмов и классы вычислимых функций. М.: Мир, 1970. С. 50-93.

44. Schoenfield J.R. Degrees of Unsolvability. Amsterdam: North-Holland, 1971. 111 p.

45. Skolem T. Begründung der elementaren Arithmetik durch die rekurrierende Denkweise ohne Anwendung scheinbarer Veränderlichen mit unendlichem Ausdehnungsbereich // Videnskapsselskapets skrifter, I. Matematisk-naturvi-denskabelig klasse. 1923. Jg. 6.

Англ. пер.: The foundations of elementary arithmetic established by means of the recursive mode of thought without the use of apparent variables ranging over infinite domains // From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931 / J. van Heijenoort. Harvard University Press, 2002. P. 302-333.

46. Stearns R. E., Hartmanis J., Lewis P.M. Hierarchies of memory limited computations // 6th Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1965). IEEE, 1965. P. 179-190.

Русск. пер.: Стирнз Р. Е., Хартманис Д., Льюис П. Иерархии вычислений с ограниченной памятью // Проблемы математической логики: сложность алгоритмов и классы вычислимых функций. М.: Мир, 1970. С. 301-319.

47. Thompson D.B. Subrecursiveness: Machine-independent notions of computa-bility in restricted time and storage // Mathematical Systems Theory. 1972. Vol. 6, no. 1. P. 3-15.

48. Turing A. M. On Computable Numbers, with an Application to the Entscheidungsproblem // Proceedings of the London Mathematical Society, Ser. 2. 1937. Vol. 42, no. 1. P. 230-265.

49. Wagner K. Bounded recursion and complexity classes // Lecture Notes in Computer Science. Vol. 74. Berlin, Heidelberg: Springer, 1979. P. 492-498.