Проблема остановки машины тьюринга

Формулировка проблемы остановки

Пусть у нас есть строка с закодированной функцией A (всё равно на каком языке, это не принципиально). Требуется создать функцию F, которая определит, будет ли функция A выполняться вечно или нет (зависнет или не зависнет).

Естественно, работа A зависит от входных данных D. Соответственно F должна принимать на вход две переменных: код функции A и входные параметры D. А возвращать F(A, D) будет логическое значение: True — A(D) остановится, False — A(D) будет работать вечно.

По сути, F(A, D) должна проанализировать строки.

Зачем решать задачу остановки?

Приведу один пример.

Всем, кто знаком с задачами криптографии, известно, какую важную роль в этой дисциплине играют простые числа Мерсенна. Человечество прилагает множество усилий по поиску этих чисел. Последнее (пока самое больше) было обнаружено 6 сентября 2008 года и насчитывало 11185272 десятичных знаков. И прямо сейчас десятки тысяч процессоров работают над поиском новых чисел.

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

Совершенные числа — это такие числа, сумма всех делителей которых равна самому числу. Например 6 делится на 1, 2 и 3; 1+2+3=6. 6 — совершенное число. 28 тоже совершенное число. Не смотря на то, что эти числа активно изучаются теоретиками и на их поиски брошены колоссальные вычислительные мощности, пока так и не понятно, сколько этих чисел, ограниченно ли их количество и существуют ли нечётные совершенные числа.

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

Программу, которая ищет совершенные числа написать очень просто. Вот пример кода на Python:

Строго говоря, искать совершенные числа можно и более рациональными способами, но все они сводятся к перебору. Просто можно перебирать не все подряд числа.

Можно написать функцию, которая ищет совершенное число среди нечётных. Сделать это очень просто:

Эта функция завершит работу только если найдётся нечётное совершенное число.

Теперь, если бы у нас была волшебная функция F, мы могли бы ей «скормить» наш не хитрый код и она выдала бы нам результат: остановится наша функция или зависнет. Если окажется, что функция зависнет, значит нечётных совершенных чисел просто не существует. Если не зависнет — можно смело начинать поиск.

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

Точно таким же способом можно было бы доказать или опровергнуть очень многие гипотезы современной математики. Например, гипотезу Биля, за которую даже назначена награда в 100000 долларов США.

Но(!) проблема остановки неразрешима.

Доказательство неразрешимости проблемы остановки

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

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

Допустим, у нас уже есть решение — функция F, которая принимает на вход некую функцию (вернее строку с текстом функции, байт-кодом или иной записью функции) и некие данные и отвечает на вопрос: «остановится ли функция-первый-аргумент, при работе с данными-вторым-аргументом, или будет работать вечно?»

Давайте создадим функцию P(x), такого вида (на C-образном языке):

Строку, которая кодирует эту функцию обозначим p. Что будет, если мы вызовем функцию F(p,p)? Возможны два исхода:

Мы получили противоречие потому, что наша начальная посылка о существовании магической функции F была не правильной.

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

Неразрешимость проблемы остановки была впервые доказана в 1936 году Аланом Матисоном Тьюрингом (Alan Mathison Turing; 1912-1954).

Проблем, подобных проблеме остановки, великое множество

Проблема остановки только одна из множества так называемых массовых проблем. Эти проблемы существуют не только в теории алгоритмов, но и в математической логике. В алгебре такой проблемой является например проблема Туэ (о равенстве конечнопорождённых и конечноопределённых полугрупп). Одна из наиболее известных математических проблем для которой доказана алгоритмическая неразрешимость — десятая проблема Гильберта (кстати, доказал это наш соотечественник Юрий Владимирович Матиясевич).

Источник

15. Машина Тьюринга. Проблема остановки. Вычислимость.

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

Программу для м. Т. можно представить в виде матрицы:

т.е. сначала мы записываем действие с ячейкой (написать что-то, не трогать ничего), потом передвижение по ленте, а потом состояние, в которое машина перейдет.

Если в машине Тьюринга T, которая кодируется, δ(i, a) = ( j, b, D), то подблок, соответствующий состоянию i и входному символу a, будет содержать j единиц, за которыми следует символ D ∈ , а за ним b ∈ <0, 1>. Если δ(i, a) не определено, то соответствующий подблок будет содержать единственный нуль.

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

Машина Тьюринга не решает проблему остановки.

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

Назовем Анализатором гипотетический алгоритм, который получает на вход пару натуральных чисел(N,X), и

§ останавливается и возвращает 1, если другой алгоритм с номером N не останавливается, получив на вход X

§ не останавливается в противном случае (если другой алгоритм с номером N останавливается, получив на вход X).

Если применить алгоритм к самому себе, то он не сможет работать, потому что должен будет остановиться тогда, когда он сам не останавливается, и не останавливаться в том случае, если он сам остановится.

Более сложное доказательство здесь Проблема вычислимости заключается в том, что есть такие «алгоритмы», результат действия которых мы не можем вычислить. Примером такого «алгоритма» является бесконечная снежинка Коха:

1. Мы рисуем треугольник

2. На следующем шаге на каждой его стороне мы рисуем еще по треугольнику

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

Источник

Проблема остановки машины Тьюринга

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

КАБАРДИНО—БАЛКАРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. Х.М. БЕРБЕКОВА

КАФЕДРА ИНФОРМАТИКИ И МАТЕМАТИЧЕСКОГО ОБЕСПЕЧЕНИЯ АВТОМАТИЗИРОВАННЫХ СИСТЕМ

Проблема остановки машины Тьюринга

Выполнил студент 2 курса МФ отделения

«Прикладная математика и информатика»

очной формы обучения А.А. Вологиров

к.т.н., доцент Л.З.-Г. Шауцукова

1. Определение машины Тьюринга

2. Работа машины Тьюринга

3. Способы задания машин Тьюринга, операции над ними

3.1 Формулировка проблемы остановки машины Тьюринга

3.2 Проблема вычислимости машины Тьюринга

4. Множество граничных конфигураций. Достаточные условия разрешимости проблемы остановки

5. Машины Тьюринга с двумя символами и не более чем тремя состояниями

Проблема остановки занимает центральное место в теории вычислимости, поскольку представляет собой первый пример задачи, которую невозможно решить алгоритмическим путем. Для многих других задач можно доказать их алгоритмическую неразрешимость, попытавшись свести задачу к проблеме остановки. Это делается по следующей схеме: пусть есть некая задача, для которой требуется установить ее неразрешимость. Тогда предположим, что она разрешима, и попытаемся, используя этот факт, написать алгоритм решения проблемы остановки. Если это удастся, то мы придем к противоречию, ведь известно, что не существует такого алгоритма. А значит, предположение было неверным и исходная задача также неразрешима.

Проблема останова заключается в том, чтобы по любой машине Тьюринга Т и слову Р в ее внешнем алфавите узнать, применима ли Т к начальной конфигурации q₁Р. Проблема останова алгоритмически неразрешима, т.к. если бы она была разрешимой, то, взяв в качестве Р слово Код(Т), мы получили бы разрешимость проблемы самоприменимости.

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

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

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

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

1. Определение машины Тьюринга

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

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

Перейдем к подробному описанию машины Тьюринга.

Для описания алгоритма МТ удобно представлять некоторое устройство, состоящее из четырех частей: ленты, считывающей головки, устройства управления и внутренней памяти. [5,6,8]

2. Считывающая головка (некоторый считывающий элемент) перемещается вдоль ленты так, что в каждый момент времени она обозревает ровно одну ячейку ленты. Головка может считывать содержимое ячейки и записывать в нее новый символ из алфавита А. В одном такте работы она может сдвигаться только на одну ячейку вправо (П), влево (Л) или оставаться на месте (Н). Обозначим множество перемещений (сдвига) головки D = <П, Л, Н>. Если в данный момент времени t головка находится в крайней клетке и сдвигается в отсутствующую клетку, то пристраивается новая пустая клетка, над которой окажется головка в момент t +1.

Совокупность всех команд называется программой машины Тьюринга. Максимальное число команд в программе равно (n +1) * m, где n +1 = A и m +1 = Q|. Считается, что заключительное состояние команды q₀ может стоять только в правой части команды, начальное состояние q₁ может стоять как в левой так и в правой части команды.

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

Итак, МТ задана, если известны четыре конечных множества: внешний алфавит A, внутренний алфавит Q, множество D перемещений головки и программа машины, представляющая собой конечное множество команд.

2. Работа машины Тьюринга

Работа машины полностью определяется заданием в первый (начальный) момент: 1) слова на ленте, т. е. последовательности символов, записанных в клетках ленты (слово получается чтением этих символов по клеткам ленты слева направо); 2) положения головки; 3) внутреннего состояния машины. Совокупность этих трех условий (в данный момент) называется конфигурацией (в данный момент). Обычно в начальный момент внутренним состоянием машины является q₁, а головка находится либо над первой слева, либо над первой справа клеткой ленты.

Заданное слово на ленте с начальным состоянием q₁ и положение головки над первым словом называется начальной конфигурацией [8]. В противном случае говорят, что машина Тьюринга не применима к слову начальной конфигурации.

Другими словами, в начальный момент конфигурация представима в следующем виде: на ленте, состоящей из некоторого числа клеток, в каждой клетке записан один из символов внешнего алфавита A, головка находится над первой слева или первой справа клеткой ленты и внутренним состоянием машины является q₁. Получившееся в результате реализации этой команды слово на ленте и положение головки называется заключительной конфигурацией.[1,2,8]

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

Работа машины Тьюринга состоит в последовательном применении команд, причем, применение той или команды определяется текущей конфигурацией. Так в приведенном выше примере должна применится команда с левой частью q₁a₁.

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

3. Способы задания машин Тьюринга, операции над ними

Рассмотрим три основные операции, применяемые над машинами Тьюринга.[8]

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

3.1 Формулировка проблемы остановки машины Тьюринга

Имеет место быть следующая теорема: не существует алгоритма (машины Тьюринга), позволяющего по описанию произвольного алгоритма и его исходных данных (и алгоритм и данные заданы символами на ленте машины Тьюринга) определить, останавливается ли этот алгоритм на этих данных или работает бесконечно.[6]

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

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

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

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

При описании универсальной машины Тьюринга мы имели кодирование для любой Tm с ленточными символами 0, 1 и B.

Кодированием была цепочка из

3. Управление теперь передается машине T0, которая может определить, останавливается с входной цепочкой или нет.

4. Если установлено, что не останавливается с входной цепочкой (т.е. не принимает ), то машина T останавливается и принимает.

Теорема 1.1. Не существует алгоритма (машины Тьюринга, которая гарантированно останавливается) для определения, остановится ли в конце концов произвольная машина Тьюринга, начиная в произвольно заданной конфигурации. [3]

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

— останавливается и возвращает 1, если другой алгоритм с номером N не останавливается, получив на вход X;

— не останавливается в противном случае (если другой алгоритм с номером N останавливается, получив на вход X);

Если применить алгоритм к самому себе, то он не сможет работать, потому что должен будет остановиться тогда, когда он сам не останавливается, и не останавливаться в том случае, если он сам остановится.

3.2 Проблема вычислимости машины Тьюринга

Проблема вычислимости заключается в том, что есть такие алгоритмы, результат действия которых мы не можем вычислить. Примером такого алгоритма является бесконечная снежинка Коха:[5]

1. Мы рисуем треугольник;

2. На следующем шаге на каждой его стороне мы рисуем еще по треугольнику;

4. И так на каждом последующем шаге мы рисуем по треугольнику на каждом из треугольников, полученных на предыдущем шаге (вот так, как это показано на картинке);

4. Множество граничных конфигураций. Достаточные условия разрешимости проблемы остановки

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

5. Машины Тьюринга с двумя символами и не более чем
тремя состояниями

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

Чтобы Z была О-машиной, должны выполняться три условия: 1, 2 и За (3б).

Теорема. Для любой из машин (2, 2) или (2, 3) проблема остановки разрешима.[7]

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

Это означает, в частности, что для машин (2, 2) п.о. разрешима

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

Мы показали, что для установления разрешимости п. о. на всем множестве начальных конфигураций достаточно исследовать лишь подмножество «граничных» конфигураций. С использованием этого факта были доказаны достаточные условия разрешимости п. о.

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

7. Павлоцкая Л. М. О машинах Тьюринга, связных относительно свойства неразрешимости проблемы остановки. //Матем. заметки, 71:5 (2002).

Размещено на Allbest.ru

Подобные документы

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

контрольная работа [82,4 K], добавлен 05.12.2010

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

контрольная работа [23,3 K], добавлен 24.04.2009

Положения машины Тьюринга. Алгоритмически неразрешимые проблемы: «остановка», эквивалентность алгоритмов, тотальность. Свойства алгоритма: дискретность, детерминированность, результативность, массовость. Выбор структуры данных. Решение на языке Haskell.

курсовая работа [957,6 K], добавлен 16.11.2013

Методика разработки программы, предназначенной для разбора предложения с помощью многоленточной машины Тьюринга. Цели и назначение данной системы, основные требования, предъявляемые к ней. Организационно-исполнительные работы по содержанию системы.

курсовая работа [386,8 K], добавлен 16.12.2010

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

курсовая работа [220,7 K], добавлен 03.03.2015

Источник

Алгоритмы. Машина Тьюринга. Альтернативные определения алгоритма. Теория вычислимости и проблема останова.

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

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

Например, решение квадратного уравнения:

Можно ввести следующее интуитивное понятие алгоритма:

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

Это, конечно, не строгое определение, но оно описывает суть понятия алгоритма.

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

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

Выделяются следующие свойства алгоритмов:

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

Не всякий способ решения задачи является алгоритмом. Скажем, алгоритм подразумевает отсутствие выбора. Например, большинство кулинарных рецептов алгоритмами не являются, поскольку используют такие фразы как “соль добавить по вкусу”. Как следствие, нарушается требование детерминированности.

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

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

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

Строгое определение алгоритма

Определение алгоритма, приведенное выше, не является строгим. Это создает некоторые трудности. В частности, с таким определением невозможно строго доказать, является ли данный класс задач решаемым при помощи алгоритма.

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

В 20-30 годах XX века, над проблемой строгого определения алгоритма работали разные математики, в частности Алан Тьюринг, Эмиль Леон Пост, Андрей Андреевич Марков, Андрей Николаевич Колмогоров, Алонзо Чёрч и другие. Их работа в итоге привела к возникновению и развитию теории алгоритмов, теории исчислимости и различных подходов к исчислению, и, кстати, программированию в целом. Одним из результатов их работы стало появление нескольких строгих определений алгоритма, введенных различным образом, но эквивалентных друг другу.

Мы подробно остановимся на определении Тьюринга, и поверхностно разберем эквивалентные определения Поста, Чёрча и Маркова.

Машина Тьюринга

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

Английский математик, логик, криптограф, возможно первый в мире “хакер”, стоял у истоков информатики и теории искуственного интеллекта. Внес существенный вклад в победу союзных войск во второй мировой войне.

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

Результатом работы машины Тьюринга так же являются слова.

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

Набор слов, к которым применим алгоритм, называется областью применимости алгоритма.

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

Описание машины Тьюринга

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

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

Хотя машина Тьюринга является абстрактной концепцией, достаточно просто представить себе подобную машину (правда, с конечной лентой), и даже существуют демонстрационные машины в таком роде:

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

Команда, в свою очередь, может иметь следующую структуру:

\[ a_k \left\lbrace \begin Л \\ Н \\ П \end\right\rbrace q_m \]

Пример

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

Будем считать, что в начальном состоянии автомат находится слева от входного слова.

Тогда, описательно, алгоритм можно сформулировать следующим образом:

Условимся, что начальное состояние \(1\) – поиск начала входного слова, \(2\) – поиск конца входного слова, \(3\) – прибавление 1.

Проследим работу этого алгоритма на примере. Первая строчка соответствует ленте, во второй обозначается положение автомата и его текущее состояние.

В состоянии 1, автомат находится над пустой ячейкой. Соответствующая команда из таблицы “ΛП1”, то есть, оставить ячейку пустой, переместиться вправо и остаться в состоянии 1:

Теперь автомат наблюдает значение “1”. Соотвествующая команда “1Н2”, то есть оставить в ячейке “1”, не перемещаться, и перейти в состояние “2”:

В состоянии “2”, автомат наблюдает значение “1”. Соответствующая команда “1П2”, то есть оставить “1”, переместиться вправо и остаться в состоянии “2”:

Аналогично, команда для состояния “2” и символа “9” – “9П2”:

Наконец, в состоянии 2 автомат наблюдает пустой символ. Команда “ΛЛ3”:

Теперь, в состоянии 3 и наблюдая символ “9”, автомат выполняет команду “0Л3”:

Наконец, выполняется команда “2Н0”:

Состояние “0” – состояние остановки. Работа алгоритма завершена.

Формальное описание

Математически, машину Тьюринга можно описать следующим образом:

Ключевым в теории алгоритмов является тезис Тьюринга.

В вольной формулировке, тезис Тьюринга формулируется следующим образом:

Тезис Тьюринга для любой алгоритмически разрешимой задачи, существует решающая эту задачу машина Тьюринга. иначе, для любого алгоритма существует эквивалентная ему машина Тьюринга.

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

Альтернативные определения алгоритма

Кроме машины Тьюринга, существует несколько независимых определений, эквивалентных определению Тьюринга.

В частности, определение через машину Поста, через лямбда-исчисление Чёрча, нормальный алгоритм Маркова.

Рассмотрим эти способы.

Машина Поста

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

Машина Поста оперирует двузначным алфавитом, и внутреннее состояние автомата заменяется на строку программы.

В остальном, машина Поста аналогична машине Тьюринга: есть автомат, и есть бесконечная лента с ячейками.

Машина Поста может выполнять следующие команды:

Так же машина Поста имеет несколько запрещенных команд:

Подобные события приводят к аварийному завершению работы.

Для написания программ для машины поста можно использовать следующие обозначения:

Эта программа сотрет первую метку (1), находящуюся справа от начального положения автомата, и остановит автомат в ячейке слева от нее.

По большому счету, машина Поста является предшественником императивных языков программирования, например, C, Fortran и пр.

Машина Поста является эквивалентной машине Тьюринга. Другими словами, для любой программы для машины Тьюринга, можно записать эквивалентную программу для машины Поста, и наоборот.

Одним из важных следствий этой эквивалентности является то, что любой алфавит можно свести к двоичному коду.

Аналогично тезису Тьюринга, существует так же и тезис Поста.

Тезис Поста всякий алгоритм представим в виде машины Поста.

Нормальный алгоритм Маркова

Нормальные алгоритмы Маркова предназначены для применения к словам в различных алфавитах.

Определение всякого нормального алгоритма состоит из двух частей:

Сам алгоритм применяется к словам, то есть последовательностям символов алфавита.

При этом предполагается, что вспомогательные символы \(\to\) и \(\to\cdot\) не принадлежат алфавиту алгоритма.

Процесс применения нормального алгоритма к произвольному слову \(V\) представляет собой следующую последовательность действий:

Любой нормальный алгоритм эквивалентен некоторой машине Тьюринга, и наоборот – любая машина Тьюринга эквивалентна некоторому нормальному алгоритму.

Аналог тезиса Тьюринга для нормальных алгоритмов принято называть принципом нормализации.

Пример

Данный алгоритм преобразует двоичные числа в “единичные” (в которых записью целого неотрицательного числа N является строка из N палочек). Например, двоичное число 101 преобразуется в 5 палочек: |||||.

Рекурсивные функции

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

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

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

Примитивно рекурсивные функции

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

К базовым функциям относятся:

Для конструирования остальных функций класса используются операторы:

Частично рекурсивные функции

Класс частично рекурсивных функций включает примитивно рекурсивные функции, и, плюс к этому, все функции, которые получаются из примитивно рекурсивных с помощью оператора минимизации аргумента:

Оператор минимизации аргумента

\[ h(x_1,\ldots,x_) = \min y, \] где \[f(x_1,\ldots,x_,y)=0.\] То есть, \(h\) возвращает минимальное значение последнего аргумента функции \(f\) при котором значение \(f\) равно нулю.

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

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

Общерекурсивные функции

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

Теория вычислимости и проблема останова

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

Исследованием таких задач занимается теория вычислимости.

Примерами алгоритмически неразрешимых задач являются проблема останова и проблема распознавания выводимости. Рассмотрим их более подробно.

Проблема останова является алгоритмически неразрешимой. Докажем это.

Пусть существует универсальный алгоритм, решающий проблему останова. Рассмотрим тогда класс алгоритмов, обрабатывающий тексты описания алгоритмов.

Более общей формулировкой проблемы останова является проблема определения выводимости.

Проблема распознавания выводимости

Пусть определены некий алфавит, слова (формулы) этого алфавита, и система формальных преобразований над словами этого алфавита (т.е. построено логическое исчисление)

Существует ли для любых двух слов \(R\) и \(S\) дедуктивная цепочка, ведущая от \(R\) к \(S\) в рамках данного логического исчисления?

В 1936 году Алонзо Чёрч доказал теорему Чёрча.

Теорема Чёрча Проблема распознавания выводимости алгоритмически неразрешима.

Чёрч использовал для доказательства формализм лямбда-исчисления. В 1937 независимо от него ту же теорему доказал Тьюринг, используя формализм машины Тьюринга.

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

Вычислимая функция функция, для вычисления которой можно составить алгоритм.

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

Пример невычислимой функции

Источник