Машины в теории вычислимых функций

 
 
 
 
 
 
С. С. Марченков, И. В. Савицкий 
 
 
 
 
 
МАШИНЫ В ТЕОРИИ ВЫЧИСЛИМЫХ ФУНКЦИЙ 
 
 
Учебное пособие 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Москва    Вологда 
«Инфра-Инженерия» 
2024 
 
1 
 

УДК 519.7 
ББК 22.18 
М30 
 
 
Рецензенты: 
доктор физ.-мат. наук, профессор 
(Московский государственный университет имени М. В. Ломоносова, 
факультет вычислительной математики и кибернетики)  
Дмитрий Сергеевич Романов; 
кандидат физ.-мат. наук, доцент 
(Московский государственный университет имени М. В. Ломоносова, 
факультет вычислительной математики и кибернетики) 
Владислав Васильевич Подымов 
 
 
 
 
Марченков, С. С. 
М30   
Машины в теории вычислимых функций : учебное пособие / С. С. Марченков, И. В. Савицкий. – Москва ; Вологда : Инфра-Инженерия, 2024. – 
104 с. : ил., табл.  
ISBN 978-5-9729-2057-0 
 
Приводятся определения как хорошо известных вычислительных устройств (машины Тьюринга, машины с произвольным доступом к памяти, машины Минского, 
двуленточные нестирающие машины Тьюринга), так и некоторых машин, появившихся 
сравнительно недавно (стековые регистровые машины, регистровые машины со счетчиками, счетчиковые машины с сумматором). Для каждого типа машин излагаются 
результаты по вычислимым функциям, достаточно полно характеризующие вычислительные возможности рассматриваемого типа машин и связывающие соответствующие 
классы вычислимых функций с известными классами рекурсивных функций.  
Для студентов, аспирантов и научных сотрудников, специализирующихся в области дискретной математики и кибернетики.  
 
УДК  519.7 
ББК   22.18 
 
 
 
 
 
ISBN 978-5-9729-2057-0 
” Марченков С. С., Савицкий И. В., 2024 
 
” Издательство «Инфра-Инженерия», 2024 
 
” Оформление. Издательство «Инфра-Инженерия», 2024 
 
2 
 

Оглавление 
 
Предисловие ............................................................................................................... 4 
 
Глава 1. Машины Тьюринга 
................................................................................... 7 
† 1. Основное определение машины Тьюринга .................................................... 7 
§ 2. Класс P полиномиально вычислимых функций 
........................................... 10 
 
Глава 2. Машины с произвольным доступом к памяти ................................. 21 
§ 1. Определение RAM-машины 
........................................................................... 21 
§ 2. Сравнение вычислительных возможностей RAM-машин                                  
и машин Тьюринга ................................................................................................. 23 
 
Глава 3. Машины Минского 
................................................................................. 30 
§ 1. Определение и вычисление частично-рекурсивных функций ................... 30 
§ 2. Класс ए૛ иерархии Гжегорчика ..................................................................... 35 
 
Глава 4. Стековые регистровые машины 
.......................................................... 40 
§ 1. Основные определения ................................................................................... 40 
§ 2. Классы एࢌ 
......................................................................................................... 41 
§ 3. Вычисления на машинах SRM с ограничениями на зону 
........................... 44 
§ 4. Программы специального вида для машин SRM ........................................ 47 
 
Глава 5. Регистровые машины со счетчиками ................................................. 54 
§ 1. Основные определения ................................................................................... 54 
§ 2. Вычисление простых арифметических функций 
......................................... 56 
§ 3. Универсальность RC-машин 
.......................................................................... 60 
§ 4. Класс функций, строго вычислимых на RC-машинах ................................ 72 
 
Глава 6. Счетчиковые машины с сумматором ................................................. 80 
§ 1. Определение и вычисление простых арифметических функций 
............... 80 
§ 2. Универсальность CS-машин .......................................................................... 83 
 
Глава 7. Неуниверсальные машины ................................................................... 92 
§ 1. Двуленточные нестирающие машины Тьюринга                                            
над двубуквенным алфавитом .............................................................................. 92 
§ 2. Двуленточные нестирающие машины Тьюринга 
над однобуквенным алфавитом ............................................................................ 98 
 
Литература 
.............................................................................................................. 101 
3 
 

Предисловие 
 
За более чем восемь десятилетий, прошедших с момента опубликования 
основополагающих работ А.௔Тьюринга и Э.௔Поста, в теории алгоритмов опреде- 
лено большое число абстрактных вычислительных устройств – вычислительных 
машин, которые способны реализовать произвольные алгоритмические процессы и вычислять произвольные частично-рекурсивные функции. Если говорить о машинах, вычисляющих частично-рекурсивные функции, то при вве- 
дении новых машин преследуются, как правило, две основные цели: в терминах 
вводимых машин «естественным образом» описать те или иные классы ре- 
курсивных функций либо средствами известного класса рекурсивных функций 
провести «арифметизацию» вычислений на рассматриваемых машинах. Часто 
вводимые машины служат для достижения обеих целей. 
В последние годы проявляется определенный интерес к изучению «малых» классов рекурсивных функций (классов «элементарных» функций, классов функций с ограничениями на время и объем вычисления и т. п.). В результате появилась потребность в вычислительных устройствах, которые позво- 
ляют наиболее полно отразить структуру и особенности изучаемых классов 
функций. Для решения этих задач были определены вычислительные машины, 
которые сильно отличаются от «классических» машин Тьюринга по устройству внешней памяти и организации процесса вычисления. В определениях 
машин наряду с обычными вход-выходными лентами используются регистры, 
счетчики, магазины, стеки, сумматоры и некоторые другие устройства внеш- 
ней памяти. Вслед за изменениями внешней памяти определенным модификациям подвергается и внутренняя память – вплоть до ее полного отказа. 
Существующее многообразие вычислительных машин позволило не только дать новые – «машинные» – определения многих известных классов рекурсивных функций, но и решить ряд других задач, стоявших в теории рекурсивных 
функций. Среди них задачи о конечном порождении классов рекурсивных функций с помощью только операции суперпозиции, задачи о построении универсальных и квазиуниверсальных функций, задачи из математической лингвистики и некоторые другие. 
В предлагаемой книге мы хотим, с одной стороны, представить основ- 
ные вычислительные машины, которые широко используются в алгоритмической практике, начиная с 30-х годов прошлого века, а, с другой стороны, – привлечь внимание к машинам, которые появились сравнительно недавно, но уже 
сумели продемонстрировать свои возможности при решении ряда конкретных 
задач. Разумеется, мы не могли даже упомянуть все варианты вычислительных 
4 
 

машин, содержащихся в многочисленных статьях и книгах и относящихся к различным аспектам теории алгоритмов и рекурсивных функций. Мы выбрали те 
из них, которые представляются нам наиболее важными для понимания сути 
представления алгоритмических процессов в виде «машинного» выполнения 
достаточно элементарных действий. Кроме того, в ряде случаев мы продемонстрировали, как в терминах вычислительных машин можно определить известные классы рекурсивных функций. 
Пособие состоит из семи глав. В главе 1 «Машины Тьюринга» дается одно из стандартных определений машины Тьюринга. Вводится понятие (числовой) функции, вычислимой на машине Тьюринга. На основе введенного по- 
нятия определяется класс P полиномиально вычислимых функций. Класс P 
характеризуется независимым образом в подходящем формализме рекурсивных функций. 
В главе 2 «Машины с произвольным доступом к памяти» вводится поня- 
тие одного из хорошо известных универсальных вычислительных устройств – 
RAM-машины, которая по организации внешней памяти довольно сильно отличается от машины Тьюринга. Доказывается, как можно с небольшими потерями 
по времени взаимно промоделировать машины с произвольным доступом к па- 
мяти и многоленточные машины Тьюринга. 
В главе 3 «Машины Минского» определяется вариант многоленточных нестирающих машин Тьюринга – машины Минского. Рассматривается вычисление 
на машинах Минского простейших арифметических функций. Устанавливается, 
что любую частично-рекурсивную функцию можно вычислить на подходящей 
машине Минского, то есть машины Минского являются универсальными вы- 
числительными устройствами. Показано, как в терминах вычислений на ма- 
шинах Минского определить один из известных классов элементарных функций – класс ࣟଶ иерархии Гжегорчика. 
Глава 4 «Стековые регистровые машины» посвящена вычислительным 
машинам, которые введены А. П. Бельтюковым. Несомненным достоинством 
этих машин является то, что с их помощью удается дать (машинное) определение «очень малых» классов рекурсивных функций. Это, в свою очередь, позволяет получать важную информацию о существовании/несуществовании конечных базисов по суперпозиции и строить универсальные и квазиуниверсальные функции. 
В главе 5 «Регистровые машины со счетчиками» рассматриваются вычис- 
лительные устройства, которые совсем недавно появились в научной литературе. 
Особенность этих устройств заключается в организации памяти, прежде всего 
внешней. Основу этой памяти составляют счетчики, которые работают независи- 
5 
 

мо от программы машины по принципу последовательного прибавления едини- 
цы в позиционной системе счисления с достаточно большим основанием. Такая 
структура внешней памяти вместе с отсутствием внутренней памяти доставляют 
определенные трудности по части составления программ для вычисления даже 
сравнительно простых арифметических функций. Вместе с тем регистровые машины со счетчиками являются универсальными вычислительными устройства- 
ми, способными вычислять произвольные частично-рекурсивные функции. Кроме 
того, – и это представляется довольно удивительным фактом – на данных маши- 
нах можно в известном смысле вычислять невычислимые (нерекурсивные) функции. Все это делает регистровые машины со счетчиками интересным объектом 
для дальнейших исследований. 
В главе 6 «Счетчиковые машины с сумматором» вводятся дальнейшие ограничения на строение внешней памяти у регистровых машин со счетчиками. В результате рабочий регистр превращается в сумматор, в который можно добавлять 
лишь числа из конечного набора (зависящего от машины). Тем не менее, использование регистровых машин со счетчиками позволяет доказать универсальность 
счетчиковых машин с сумматором. 
В главе 7 «Неуниверсальные машины» рассмотрен вариант двуленточных 
(с входной и выходной лентами) нестирающих машин Тьюринга с несколькими 
читающими головками на входной ленте. Для случая двубуквенного алфавита доказана замкнутость класса ܥ вычислимых функций относительно операций суперпозиции и ограниченной префиксной конкатенации. Установлена принадлежность классу ܥ всех функций из класса «элементарных» функций BPC. Для однобуквенного алфавита доказано совпадение соответствующего класса вычислимых функций с классом ࣟଶ иерархии Гжегорчика. 
Книга ориентирована на широкий круг читателей: ее можно использовать 
для первоначального знакомства с машинами Тьюринга и вычислимыми функ- 
циями; ей можно пользоваться в качестве учебного пособия при изучении кур- 
сов дискретной математики и теории алгоритмов; более подготовленный читатель найдет в ней направления и темы для дальнейших исследований. 
 
 
6 
 

Глава 1 
Машины Тьюринга 
 
§ 1. Основное определение машины Тьюринга 
 
Машина Тьюринга состоит из ленты, считывающе-записывающей головки 
и управляющего устройства. Лента бесконечна влево и вправо и разбита на клет- 
ки. В каждой клетке ленты может быть записан один из символов конечного ленточного алфавита ܣ= {ܽ଴, ܽଵ, … , ܽ௞}. Обычно в алфавите ܣ выделяется так называемый «пустой» символ ܽ଴. 
Головка машины может: 
1) двигаться по ленте влево и вправо, перемещаясь из одной клетки в со- 
седнюю с ней клетку; 
2) читать символ, записанный в клетке, и записывать в обозреваемую 
клетку любой символ алфавита ܣ. 
Управляющее устройство организует перемещение головки на ленте и запись символов в клетки ленты. Оно может находиться в одном из конечного 
числа состояний ݍ଴, ݍଵ, … , ݍ௥. В множестве состояний выделяются начальное состоя- 
ние ݍଵ и заключительное состояние ݍ଴. 
Изменение положения головки на ленте, запись новых символов в клетки 
ленты и переход в другие состояния происходит согласно программе машины, 
которая состоит из команд вида 
ܽ௜ݍ௝՜ ܽ௟ܦݍ௦, 
где ്݆0 и ܦ есть один из символов движения: ܮ, ܴ, ܵ. Для любых возможных 
значений ݅, ݆ (0 ൑݅൑݇,  1 ൑݆൑ݎ) программа машины содержит ровно одну команду с левой частью ܽ௜ݍ௝. Обычно программу машины Тьюринга записывают 
в виде таблицы, строки которой помечены символами ܽ଴, ܽଵ, … , ܽ௞, а столбцы – 
символами ݍଵ, … , ݍ௥. В клетке таблицы, отвечающей строке ܽ௜ и столбцу ݍ௝, за- 
писана правая часть ܽ௟ܦݍ௦ команды. 
Работа машины Тьюринга протекает в дискретном времени ݐ= 1,2, …. 
Перед началом работы машины Тьюринга (ݐ= 0) на ленте записывается некоторое слово ܽ
᪄ в алфавите {ܽଵ, … , ܽ௞}, вся остальная часть ленты (слева и справа 
от слова ܽ
᪄) заполняется «пустым» символом ܽ଴. Головка машины Тьюринга 
устанавливается в клетку, содержащую первую букву слова ܽ
᪄, а управляющее 
устройство приводится в состояние ݍଵ. 
7 
 

Каждый из последующих незаключительных шагов (тактов) работы маши- 
ны Тьюринга выполняется согласно одному и тому же правилу: если в момент 
времени ݐ головка машины Тьюринга считывает символ ܽ௜, управляющее устрой- 
ство находится в состоянии ݍ௝ (്݆0) и в программе машины имеется команда 
ܽ௜ݍ௝՜ ܽ௟ܦݍ௦, то в момент времени ݐ+ 1: 
1) в обозреваемую (в момент ݐ) клетку ленты будет записан символ ܽ௟ 
(возможно, что ݈= ݅); 
2) головка сдвинется на одну клетку влево (если ܦ= ܮ), вправо (если ܦ= 
= ܴ) или останется в прежней клетке (если ܦ= ܵ); 
3) управляющее устройство перейдет в состояние ݍ௦ (и здесь возможно 
равенство ݏ= ݆). 
Машина Тьюринга заканчивает работу, если управляющее устройство попадает в заключительное состояние ݍ଴. 
Отметим, что, вообще говоря, не для всех слов ܽ
᪄ машина Тьюринга за- 
вершает свою работу. Для некоторых слов ܽ
᪄ она может работать неограничен- 
но долго, не попадая в заключительное состояние ݍ଴. В случае окончания работы машины Тьюринга результатом применения машины к слову ܽ
᪄ обычно считают слово в алфавите {ܽଵ, … , ܽ௞}, которое оказывается записанным на ленте 
в заключительный момент времени. Если же машина Тьюринга не заканчивает 
работу, то результат применения машины к слову ܽ
᪄ не определен. 
Пусть Գ = {0,1, … }. Нас, в первую очередь, будут интересовать функции 
на Գ, вычислимые на машинах Тьюринга. Чтобы их определить, необходимо, 
прежде всего, условиться о способе представления натуральных чисел на ленте 
машины Тьюринга. Существует два основных способа. 
Первый способ – это обычное представление чисел в позиционной системе 
с основанием ݉, где ݉൒2 (как правило, предпочтение отдается основанию 2). 
В этом случае предполагается, что входной алфавит машины Тьюринга содержит символы 0,1, … , ݉െ1, «пустой» символ ܽ଴ (он отличен от символа 0) и, возможно, еще некоторые символы. 
Второй способ на практике не встречается, однако он обладает некото- 
рыми теоретическими «преимуществами». Здесь число ݈א Գ представляется по- 
следовательностью из ݈+ 1 символов 1 («лишняя» единица добавляется, чтобы 
иметь возможность представить число 0). В связи с этим ленточный алфавит 
машины Тьюринга, предназначенной в этом случае для вычисления некоторой 
функции, всегда содержит символ 1 (например, ܽଵ= 1), пустой символ 0 (например, ܽ଴= 0) и, возможно, другие символы. Далее мы дадим определение функции, вычислимой на машине Тьюринга, именно для этого способа представле- 
ния натуральных чисел. 
8 
 

Итак, число ݈ из Գ записываем на ленте машины Тьюринга в виде массива из ݈+ 1 единиц, а в остальных клетках ленты помещаем пустой символ 0. 
Если ݊> 1 и требуется представить на ленте машины Тьюринга набор чисел 
(݈ଵ, … , ݈௡), то образуем ݊ массивов из ݈ଵ+ 1, … , ݈௡+ 1 единиц соответственно и 
помещаем между соседними массивами разделительный символ 0. Такое представление набора чисел (݈ଵ, … , ݈௡) на ленте машины Тьюринга (включая слу- 
чай ݊= 1) будем называть основным кодом набора (݈ଵ, … , ݈௡). 
Пусть теперь ݂(ݔଵ, … , ݔ௡) – функция (вообще говоря, частичная) с аргу- 
ментами, принимающими значения из Գ, и значениями также в множестве Գ, 
ࣧ – машина Тьюринга с ленточным алфавитом ܣ, содержащим символы 0 и 1. 
Будем говорить, что машина ࣧ вычисляет функцию f, если для любого набо- 
ра (݈ଵ, … , ݈௡) א Գ௡ выполняются следующие условия. 
1. Если значение ݂(݈ଵ, … , ݈௡) определено, то машина ࣧ, начиная работу 
в состоянии ݍଵ на первой единице основного кода набора (݈ଵ, … , ݈௡), 
через конечное число тактов останавливается и в заключительный мо- 
мент времени на ленте машины в основном коде представлено число 
݂(݈ଵ, … , ݈௡). 
2. Если значение ݂(݈ଵ, … , ݈௡) не определено, то, начиная работу из той 
же позиции, что и в п. 1, машина ࣧ либо никогда не останавливается, 
либо останавливается, но при этом на ленте машины не представлено 
в основом коде никакое число из Գ. 
Нетрудно показать, что класс функций, вычислимых на машинах Тьюринга, не изменится, если в п. 1 определения машина Тьюринга в заключительный момент времени будет останавливаться на первой единице основного кода 
результата, а в п. 2 определения не будет реализоваться вторая возможность. 
Хорошо известно, что класс функций, вычислимых на машинах Тьюринга, 
совпадает с классом частично-рекурсивных функций (которые определяются, 
например, в формализме Клини). 
Существует большое число вариантов определения машины Тьюринга. 
Некоторые из них довольно значительно отличаются от данного выше опре- 
деления. Пока мы обратим внимание на самое простое обобщение определения, которое приводит к многоленточной машине Тьюринга. Как видно из названия, многоленточная машина Тьюринга имеет несколько (݌൒2) лент. На каждой из лент располагается своя считывающе-записывающая головка. Считыва- 
ние символов с лент и движения головок происходит независимо друг от друга. 
Команды многоленточной машины Тьюринга имеют вид 
ܽଵ… ܽ௣ݍ௝՜ ܾ௟… ܾ௣ܦଵ… ܦ௣ݍ௦, 
9 
 

где ܽଵ, … , ܽ௣ – символы, считываемые головками на соответствующих лентах, 
а ܦଵ, …, ܦ௣ – движения головок. В остальном функционирование многоленточной машины Тьюринга аналогично функционированию обычной (одноленточной) машины Тьюринга. Стоит лишь отметить, что, как правило, исходное слово 
записывается на первой ленте многоленточной машины (остальные ленты пустые) и, соответственно, результат вычисления также считывается с первой ленты. 
Вычисление на многоленточной машине Тьюринга легко промоделировать с помощью одноленточной машины. Для этого, например, можно разбить 
исходную ленту (одноленточной машины) на ݌ «решеток» – подмножеств клеток, в каждом из которых «соседние» клетки располагаются на расстоянии ݌. 
Кроме того, необходимо на каждой из решеток специальным маркером (дополнительным символом алфавита) помечать ту клетку, в которой в рассматриваемый момент времени находится соответствующая головка моделируемой машины. Более подробно описывать достаточно прозрачный процесс моделирования многоленточной машины Тьюринга посредством одноленточной машины 
Тьюринга мы не будем. Отметим лишь, что данный процесс можно выполнить 
с полиномиальным по времени «растяжением». Это означает, что найдется такой полином ݌(ݐ) с натуральными коэффициентами, зависящий от моделируемой машины, что время работы одноленточной машины над входным словом 
не превосходит ݌(ݐ), где ݐ – время работы моделируемой машины над рассматриваемым словом. 
 
§ 2. Класс P полиномиально вычислимых функций 
 
Как отмечалось, машины Тьюринга являются универсальными вычисли- 
тельными устройствами: любую частично-рекурсивную функцию можно вычислить на подходящей машине Тьюринга. Однако класс частично-рекурсивных 
функций слишком широк, и на практике часто довольствуются классами вычислимых функций гораздо меньшего объема. Один из распространенных спо- 
собов получения таких классов – ограничение (сверху) времени вычисления 
функций. Обычно берут множество ܯ всюду определенных функций (чаще 
всего монотонных) и рассматривают класс ܨ
ெ функций, вычислимых на машинах Тьюринга за время, ограниченное функциями из ܯ. На этом пути можно 
определить широкий спектр классов ܨ
ெ. В последнее время внимание иссле- 
дователей привлекает класс ܨ
ெ, где ܯ – множество всех полиномов с натуральными коэффициентами. Мы этот класс будем обозначать через P. 
Приведем более формализованное определение класса P. Пусть ܣ – конечный алфавит, ܣכ – множество всех слов в алфавите ܣ (включая пустое слово ߉), 
݂ – функция вида ܣכ ՜ ܣכ, ܶ(݊) – функция вида Գ ՜ Գ. Будем говорить, что 
10