Статья:

Вычислимость по Тьюрингу частично рекурсивных функций и математическое решение задачи о Ханойской башне

Конференция: XLVII Студенческая международная научно-практическая конференция «Молодежный научный форум»

Секция: Физико-математические науки

Выходные данные
Петренков Д.А., Семёнов А.В. Вычислимость по Тьюрингу частично рекурсивных функций и математическое решение задачи о Ханойской башне // Молодежный научный форум: электр. сб. ст. по мат. XLVII междунар. студ. науч.-практ. конф. № 17(47). URL: https://nauchforum.ru/archive/MNF_interdisciplinarity/17(47).pdf (дата обращения: 07.02.2023)
Лауреаты определены. Конференция завершена
Эта статья набрала 54 голоса
Мне нравится
Дипломы
лауреатов
Сертификаты
участников
Дипломы
лауреатов
Сертификаты
участников
на печатьскачать .pdfподелиться

Вычислимость по Тьюрингу частично рекурсивных функций и математическое решение задачи о Ханойской башне

Петренков Денис Александрович
студент, Самарский Университет им. С.П. Королёва, РФ, г. Самара
Семёнов Артем Витальевич
студент, Самарский Университет им. С.П. Королёва, РФ, г. Самара
Куликова Ирина Геннадьевна
научный руководитель, старший преподаватель ФГБОУ ВО «Самарский государственный университет путей сообщения», РФ, г. Самара

 

Аннотация. В статье рассматривается алгебраический способ доказательства вычислимости по Тьюрингу частично рекурсивных функций, уделяется внимание конструированию машин Тьюринга и выполнению операций над ними, уточняется понятие вычислимых функций. В дополнение разбирается вариант применения рекурсивных алгоритмов и преобразования их в нерекурсивные на примере рекурсивного решения популярной головоломки «Ханойская башня».

 

Ключевые слова: машина Тьюринга; рекурсия; рекурсивная функция.

 

Введение

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

Рассмотрим пример. Пусть требуется смоделировать машину Тьюринга, способную из n расположенных подряд единиц выдавать на ленте n - 2 единицы, также расположенные подряд, если n > 2, и способную функционировать вечно, если n = 0 или n = 1.

Для успешного выполнения намеченного нам понадобится принять некоторые допущения. Далее по тексту будут иметь место следующие названия: так, за внешний алфавит мы примем двухэлементное множество А = {0, 1}. Число требуемых внутренних состояний предстоит вычислить в ходе написания программы. Принимаем допущение, что машина начинает функционировать из стандартного начального положения, которое определяется  состоянием q1, и в котором обозревается крайняя правая единица из n размещенных на ленте.

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

q11→ q20Л; q21→ q30Л.

Далее пусть машина принимает состояние q3 и обозревает третью справа ячейку из числа тех, где записано это слово (n единиц). Не внося изменения в содержательную часть обозреваемой ячейки, машина должна остановиться, или говоря иными словами, перейти в заключительное состояние q0, вне зависимости от содержимого ячейки. Тогда  команды, отвечающие за озвученные действия, могут быть представлены в следующем виде:

q30→ q00; q31→ q01.

Представим себе случай, что на ленте записана только одна единица. Тогда, выполнив первый шаг, а именно команду q11→ q20Л, машина перейдет в состоянии q2 и будет обозревать вторую справа ячейку, где записан 0. Исходя из условия, в подобной ситуации машина должна функционировать вечно. Тогда  команды, отвечающие за озвученные действия, могут быть представлены в следующем виде:

q20→ q20П,

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

q10→ q1

Представим разработанную программу (функциональную схему) смоделированной машины Тьюринга в виде таблицы:

Таблица 1.

Функциональная схема смоделированной машины Тьюринга

A\Q

q1

q2

q3

0

1

q1

q0

q2

q2

q00

q01

 

Подводя итоги, очевидно, что смоделированная машина Тьюринга может применяться к словам алфавита А - {0, 1}, состоящего из расположенных подряд n единиц (n > 2). Однако, с тем же успехом она может применяться к другим словам алфавита: 1011, 10011, 111011, 11011, 1100111, 1001111, 10111, 10110111, 10010111 и т.д.

Следует отметить, что сконструированная машина может быть не применима (говоря иными словами, при подаче этих слов на вход машины она функционирует вечно) к слову «1», а также к слову, состоящему из одних  только нулей. Смоделированная  машина не применима также к словам: 101, 1001, 11101, 101101, 1100101101 и т.д.

Разберем, что принято называть вычислимыми функциями. Ознакомимся с определением.

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

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

Далее, необходимо принять некие условия, например, как записывать на ленте машины Тьюринга значения х1,, х2, ..., хn  аргументов функции f(x1, x2, ..., хn), из какого конкретно положения следует начинать переработку исходного слова, а также в каком конкретно положении предстоит снимать значение функции.

Данные условия можно обеспечить таким образом. Значения х1,, х2, ..., хn  аргументов необходимо расположить на ленте в  форме следующего слова:

Предстоит также принять некоторые обозначения. Так, натуральное х обозначаем:

Принимаем условие, что  0° = 1° = ∧ — пустое слово. Тогда  слова 1° = ∧, I1 = 1, I2 = 11, I3 = 111, ... рассматриваются как «изображения» натуральных чисел 0, 1, 2, 3, ... соответственно.

Тогда, предыдущее слово можно представить так: .

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

Допустим, функция f(x1, x2, ..., хn)  определена на некотором наборе значений аргументов, тогда на ленте будет обозначено подряд f(x1, x2, ..., хn) единиц; в противном случае машина должна будет работать бесконечно. И тогда при соблюдении, всех перечисленных условий, можно утверждать, что машина Тьюринга вычисляет данную функцию.  Мы добились того, что сформулированное выше определение представлено как абсолютно верное.

Приведем пример: требуется смоделировать машину Тьюринга, вычисляющую функцию f(x) = х/2, которая не всюду определена: область  ее  определения - множество четных чисел. Учитывая определение, необходимо смоделировать машину Тьюринга, способную при подаче на ее вход четного числа выдавать на выходе половину этого числа, а при подаче нечетного - функционировать бесконечно долго.

Разберем вопрос о вычислимости по Тьюрингу частично рекурсивных функций.

Докажем следующую теорему:

Теорема. Если функция f(x,y) правильно вычислима на машине Тьюринга, то и функция φ(x)=μy[f(x,y)=0], получающаяся с помощью оператора минимизации из функции f(x,y), также правильно вычислима на машине Тьюринга.

Доказательство. Для успешного выполнения намеченного нам понадобится принять ряд обозначений. Допустим, что F – машина Тьюринга, правильно вычисляющая функцию f(x,y). С ее помощью смоделируем  машину Тьюринга, способную для заданного значения x вычислять поочередно значения f(x,0), f(x,1), f(x,2), … до искомого момента, когда впервые появится f(x,i)=0. По окончании данного события на ленте появится результат - число i, являющее собой значение функции φ(x)=i. Если выполняется условие, что для всех значений i справедлива функция f(x,i)>0, машина будет функционировать вечно, и это обстоятельство станет свидетельством того, что функция φ не определена в точке x. Пусть начальная конфигурация на машине представлена таким образом: q101x0. Представим ее в виде q101x010 и применим к ней “копирование” К2. Получим конфигурацию 01x010q101x010. Вычисляем значение f(x,0), используя возможности машины

F: 01x010qα01f(x,o).

Переходим к следующим этапам. Далее  необходимо подобрать команды, способные при условии f(x,i)>0 переводить конфигурацию 01x01iq01f(x,i)  в конфигурацию 01x01i+1q01f(x,i+1):

qα0→ qα+10П: 01x0100 qα+1 1f(x,o);

qα+11→ qα+20: 01x0100 qα+2 1f(x,o)-1;

qα+20→ qα+30Л: 01x010qα+3 001f(x,o)-1;

qα+30→ qα+41: 01x010qα+4 101f(x,o)-1;

qα+41→ qα+51П: 01x0110 qα+5 01f(x,o)-1;

О: 01x011q0;

-)2: 01x011q 01x011;

F: 01x011 qβ 01f(x,1);

qβ0→ qα0: 01x011 qα 01f(x,1);

Становится очевидным, что последняя команда завершает цикл  программы, и машина от конфигурации 01x011 qα 01f(x,1) принимает конфигурацию 01x012 qα 01f(x,2), далее  конфигурацию 01x013 qα 01f(x,3) и так далее, по порядку. Рассмотрим случай, когда на определенном шаге машина принимает конфигурацию 01x01i qα 01f(x,i), при которой f(x,i)=0. Это может означать, что φ(x)=i, в этом случае машина обязана выдать такой результат. Число i накоплено в «счетчике» 01i. Значит, далее следует действовать согласно предлагаемому алгоритму. Имеющаяся команда qα0→ qα+10П приведет машину к нужной конфигурации 01x01i 0qα+10. Все последующие команды станут выдавать на ленту нужную конфигурацию q001i, говоря другими словами, q001φ(x):

qα+10→ qγ0: 01x01i 0qγ0;

-)2: 01x qγ 01i 0;

ВО Б-: qδ 01i ;

δ 0→ q00: q001φ(x)

Теорема доказана.

В завершении предлагается рассмотреть возможности применения рекурсивных алгоритмов и преобразования их к нерекурсивным на примере решения задачи из информатики, основанной на красивой легенде о Ханойской башне

 

Рисунок 1. Модель Ханойской башни

 

Речь идет о некогда очень популярной головоломке XIX века. Ее изобрел французский математик Эдуард Люка в 1883 году.

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

 

Рисунок 2. Блок-схема рекурсивного алгоритма решения

 

Известно некоторое количество решению данной задачи, и, несмотря на различные алгоритмы решений, результаты их одинаковые.

Более пристальному вниманию подлежит рекурсивное решение. Рассмотрим его.

Рекурсивно решаем задачу «переложить пирамиду из n−1 кольца на 2-й стержень». Затем перекладываем наибольшее кольцо на 3-й стержень, и рекурсивно решаем задачу «переложить пирамиду из n−1 кольца на 3-й стержень».

Далее методом математической индукции делаем вывод, что наименьшее количество ходов, требуемое для решения задачи, определяется как  2n − 1, где n — число стержней.

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

Что же касается самой легенде, то согласно ей, очень давно, где то в колыбели мира в Великом храме города Бенарес, под монастырем, отмечающим середину мира, был расположен диск из бронзы. На диске установлены три  высоких алмазных стержня. Когда  то  монахи монастыря своим неповиновением заслужили негодование бога Брахмы. Тогда бог Брахма установил три высоченных стержня, возложил на единственный из них 64 диска, выполненных из чистого золота. Каждый  меньший диск располагался на большем. И возвестил, что когда все 64 диска будут перемещены на соседний стержень, башня и храм станут пылью, и со страшными ударами молнии мир погибнет. Когда же это может произойти? Применяя способ рекурсивного решения можно найти решение. Количество перекладываемых дисков, которое предстоит выполнить монахам, исчисляется как 18 446 744 073 709 551 615.

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

Заключение

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

 

Список литературы: 
1. Носов В.А. Основы теории алгоритмов и анализа их сложности, 1992. - 140 с.
2. Ханойская башня (Савин А.) [Электронный ресурс]. - URL: http://ipuzzles.ru/tower-of-hanoi/savin-tower-of-hanoi/ (дата обращения: 10.04.2019).