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

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

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

Введение

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

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

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

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

q₁1→ q₂0Л; q₂1→ q₃0Л.

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

q₃0→ q₀0; q₃1→ q₀1.

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

q₂0→ q₂0П,

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

q₁0→ q₁0П

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

Таблица 1.

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

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

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

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

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

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

Далее, необходимо принять некие условия, например, как записывать на ленте машины Тьюринга значения х₁,, х₂, ..., х_n  аргументов функции f(x₁, x₂, ..., х_n), из какого конкретно положения следует начинать переработку исходного слова, а также в каком конкретно положении предстоит снимать значение функции.

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

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

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

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

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

Допустим, функция f(x₁, x₂, ..., х_n)  определена на некотором наборе значений аргументов, тогда на ленте будет обозначено подряд f(x₁, x₂, ..., х_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. Пусть начальная конфигурация на машине представлена таким образом: q₁01^x0. Представим ее в виде q₁01^x01⁰ и применим к ней “копирование” К₂. Получим конфигурацию 01^x01⁰q₁01^x01⁰. Вычисляем значение f(x,0), используя возможности машины

F: 01^x01⁰q_α01^f(x,o).

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

q_α0→ q_α+10П: 01^x01⁰0 q_α+1 1^f(x,o);

q_α+11→ q_α+20: 01^x01⁰0 q_α+2 1^f(x,o)-1;

q_α+20→ q_α+30Л: 01^x01⁰q_α+3 001^f(x,o)-1;

q_α+30→ q_α+41: 01^x01⁰q_α+4 101^f(x,o)-1;

q_α+41→ q_α+51П: 01^x01¹0 q_α+5 01^f(x,o)-1;

О: 01^x01¹q0;

(Б^-)²: 01^x01¹q 01^x01¹;

F: 01^x01¹ q_β 01^f(x,1);

q_β0→ q_α0: 01^x01¹ q_α 01^f(x,1);

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

q_α+10→ q_γ0: 01^x01ⁱ 0q_γ0;

(Б^-)²: 01^x q_γ 01ⁱ 0;

ВО Б^-: q_δ 01ⁱ ;

q _δ 0→ q₀0: q₀01^φ(x)

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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