Итак, нам нужно будет построить Машину Тьюринга, которая добавляет единицу справа к данной строке с единицами. Задача формулируется так:
Дан алфавит из двух символов: 0 и 1. Бесконечная лента заполнена нулями и только в одном месте находится строка из нескольких единиц (число их неизвестно). Дано, что в самом начале считывающее устройство (далее - СУ) находится где-то слева от строки с единицами. Машина должна найти на ленте эту строку и добавить справа от неё ещё одну единицу.
Задание станет совершенно понятно, если вы посмотрите на рисунок:
Почему в формулировке задачи мы постановили, что СУ находится слева от строки с единицами, а не в произвольном месте ленты ? Дело в том, что, если бы мы были вынуждены искать единицы по всей ленте (то есть в обоих направлениях), задача усложнилась бы многократно! Более того, было бы крайне тяжело обойтись только двумя символами алфавита. Поэтому остановимся на гораздо более простой формулировке задачи, и попробуем разработать стратегию решения.
Естественно, что в самом начале СУ начинает двигаться вправо и сканировать содержимое клеток ленты. Если СУ видит в клетке ноль, оно оставляет всё как есть и делает один шаг вправо. Если СУ видит в клетке единицу, оно оставляет всё как есть и делает один шаг вправо. Постойте! В чём же разница между двумя действиями, которые совершает СУ в случае чтения нуля и в случае чтения единицы ? Верно - разницы в поведении СУ нет, но есть более существенная разница - в поведении самой Машины Тьюринга, вернее, программы, которая управляет СУ. Дело в том, что изначально наша Машина находится в некоем состоянии (назовём его состояние А), которое можно охарактеризовать так: ищи строку единиц справа от СУ. В тот момент, когда СУ считывает единицу, Машина переходит в состояние В, которое означает: а теперь ищи самую последнюю (самую правую) единицу в строке единиц. При этом СУ совершает те же самые действия[1], только находясь в другом состоянии.
Итак, находясь в состоянии B, машина продолжает двигаться вправо, сканируя ленту. Наконец, СУ обнаруживает в клетке ноль (это может случиться как на следующем ходу, так и через целый гугл клеток). Этот ноль означает, что строка единиц кончилась и пришло время добавить новую единицу. СУ заменяет этот ноль на единицу и останавливается. При этом, мы можем оставить машину в состоянии В, но более красивым вариантом будет перевести её в состояние С, который будет "тупиком" - это состояние будет означать остановку машины.
Задача выполнена. Теперь, чтобы построить управляющую таблицу (проще говоря - программу) Машины Тьюринга, призовём на помощь диаграмму, так называемый "конечный автомат":
На этой диаграмме изображены три только что описанных состояния. Во многом она говорит сама за себя, и в объяснении нуждаются только подписи под стрелками перехода из одного состояния в другое. Так 0 -> 0 / Right обозначает: если СУ видит в клетке 0, оно должно заменить его на 0 и сдвинуться вправо. Таким образом, 0 -> 1 / Stop значит: если в клетке 0, замени его на 1 и не двигайся.
Всё предельно просто. Теперь нам осталось только перевести диаграмму состояний в таблицу управления и Машина Тьюринга, решающая поставленную задачу, готова!
А вот и таблица:
Как видите, состояние С - это полный тупик. Машина ничего не меняет и никуда не двигается. Более того, из этого состояния нет выхода ни в какое другое.
И чтобы рассеять последние сомнения, приведём последовательность шагов и состояний, в которых будет пребывать наша Машина, решая поставленную задачу:
А теперь - сюрприз. Отнеситесь к нему серьёзно, потому что этот сюрприз - один из главных постулатов компьютерной науки. Но прежде мне хочется рассказать одну историю. Однажды я присутствовал на лекции по математическому анализу. Лектор (а он был замечательным математиком) представил студентам Великую Теорему математического анализа - теорему об эквивалентности интегралов Римана и Ньютона-Лейбница, после чего он сказал: "А теперь вы должны пойти домой. Ничто не может служить достойным продолжением лекции после теоремы, с которой вы только что познакомились". Таким образом эта самая короткая лекция в моей жизни длилась минут пятнадцать.
Так вот, после того, как вы дочитаете эту главу - отложите этот курс и не возвращайтесь к нему до завтрашнего дня. Ибо ничто не может служить достойным продолжением следующего абзаца.
Итак:
Тезис Тьюринга-Чёрча[2]
Любая задача, для которой существует алгоритм решения, может быть решена с помощью машины Тьюринга. Другими словами, машина Тьюринга может быть запрограммирована так, чтобы выполнять любой заданный алгоритм.
Если расписать этот тезис более подробно, он означает вот что:
представьте, что у вас есть сверх-эффективный алгоритм решения некоей очень сложной задачи. Представьте теперь, что вы располагаете поистине неограниченными средствами, которые позволяют вам обзавестись тысячами суперкомпьютеров с поистине необъятными ресурсами скорости и памяти. Вы запускаете свой алгоритм на этом монстрообразном конгломерате и ждёте - сто, двести, тысячу лет - столько, сколько понадобится (вам точно известно, что задача имеет решение, а ваша жизнь, равно как и ресурсы, не ограничена ничем).
И что же ?
А вот что:
та же самая задача с тем же самым (или даже гораздо менее эффективным) алгоритмом решения может быть столь же успешно решена с помощью примитивнейшей Машины Тьюринга с одной единственной лентой, поделённой на клеточки, и допотопным считывающим устройством.
Иными словами, если задача может быть решена с помощью Машины Тьюринга, то она может быть решена с помощью любого компьютера, с любыми ресурсами, на любом, сколь угодно сложном языке программирования.
Ага, - скажет тут читатель, - а зачем тогда огород городить? Зачем выдумывать все эти бесчисленные и хитроумные языки программирования, которые описаны в этом самом курсе; зачем всё это, если простая Машина Тьюринга решает те же самые задачи с помощью одной ленты и нескольких таблиц?
Ответ на этот справедливый вопрос для нас исключительно важен именно в контексте этого самого курса. Разные языки программирования существуют только для того, чтобы помочь нам моделировать - задачу, физическую реальность или что бы то ни было - наиболее удобным для каждой конкретной ситуации способом. И только. Никогда, ни при каких обстоятельствах, ни сейчас, ни в сколь угодно далёком будущем не будет придуман язык программирования или компьютер, позволяющий решать задачи, которые невозможно решить с помощью Машины Тьюринга или с помощью одного из существующих языков и компьютеров общего назначения.
Вывод довольно неутешительный, но тем не менее множество разнообразных языков программирования, а главное - программных парадигм, существует отнюдь не зря. Вы, наверное, уже догадались, что Машина Тьюринга, хотя и равна по алгоритмической силе любым другим компьютерам и языкам, всё-таки уступает им по быстроте и удобству программирования. В этом-то и заключается ключевой вопрос: скорость, эффективность, ресурсы, удобство - все эти факторы определяют наличие сотен разнообразнейших языков программирования; они же побуждают нас изобретать всё новые и новые способы моделирования задач и алгоритмов.
И весь этот курс – об этих способах.
В самом начале мы упомянули ещё об одной машине - так называемой Универсальной Машине Тьюринга. Пришло время обратиться и к ней.
Только что рассмотренная нами Машина, Которая Умеет Добавлять Единицу, всем хороша, кроме одного - она узкоспециальна. Всё, что умеет делать эта машина, ограничивается добавлением единицы справа к строке единиц, находящейся... и так далее, и тому подобное. Нас же гораздо больше устроила бы машина общего назначения - такая, какой является современный компьютер.
Тьюринг в своей работе определил и её, и с тех пор эта машина носит название Универсальной Машины Тьюринга.
На рисунке вы видите две машины: одна из них - специального назначения (такая машина позволяет решать одну конкретную задачу), вторая - Универсальная Машина Тьюринга. Каждая из них имеет свою таблицу состояний, то есть программу. Сейчас нас интересует таблица, управляющая работой специальной машины Тьюринга.
В наши дни не найдётся, наверное, человек, который бы не знал, что любую информацию можно представить в виде последовательности нулей и единиц. Поэтому и таблицу (программу) любой машины Тьюринга можно, конечно же, представить в виде нулей и единиц (другими словами - неким конечным набором символов) на ленте конечной длины. Именно так мы и поступим с таблицей специальной машины Тьюринга, а потом просто отобразим эту последовательность на ленте Универсальной Машины Тьюринга (УМТ). Таким образом, входными данными УМТ будет программа некоей специализированной машины Тьюринга (СМТ), которая призвана решать какую-то конкретную задачу (например, складывать числа).
Какую же задачу призвана решать в таком случае УМТ ?
Ответ почти очевиден: получив программу, управляющую СМТ, УМТ должна уметь эту программу интерпретировать (то есть, понимать и выполнять) и производить над входными данными СМТ те же самые действия, которые бы производила над ними СМТ. Иначе говоря, УМТ должна симулировать работу СМТ - любой СМТ! - и выдавать точно такой же ответ, какой бы выдала СМТ.
Для того, чтобы дать УМТ те же самые входные данные, которые получает СМТ, поместим эти входные данные где-нибудь на ленте УМТ, например, сразу же после таблицы (программы), представляющей СМТ. Две эти входные последовательности - программу и данные - можно разделить каким-либо специальным (не встречающимся более нигде) символом.
Тьюринг в своей работе показал, что УМТ может быть построена. Что же такое УМТ на самом деле ? Вы, конечно же, уже догадались. Универсальная Машина Тьюринга - это прототип современного компьютера общего назначения. В самом деле - компьютер точно так же получает некую программу, которую он должен выполнить (причём программа эта может решать любую, но всякий раз строго определённую задачу), и входные данные, с которыми программа будет работать.
Компьютер общего назначения универсален в том же смысле, что и УМТ: он умеет симулировать любую другую, более специализированную машину и совершать над её входными данными те же самые действия, которые совершила бы эта самая специализированная машина.
Сейчас важно обратить внимание на то, что программа, переданная УМТ, и входные данные - это две разные сущности, несмотря на то, что находятся они на одной ленте и закодированы с помощью одного и того же алфавита. То же происходит и в компьютере - и программа и данные находятся в памяти компьютера, и закодированы они с помощью последовательности нулей и единиц. И тем не менее, это - две разные сущности. Однако, помня об этом, не будем торопиться с выводами. В этом курсе вы уже не раз встречались с данными, превращающимися в программу и наоборот. Такая игра в перевёртыши просто неизбежна, когда вы имеете дело с программированием.
[1]Не совсем верно назвать действия СУ теми же самыми. В состоянии А СУ "заменяет" 0 на 0, а в состоянии В оно "заменяет" 1 на 1. Впрочем, это как посмотреть. Можно определить несколько другой modus operandi нашей машины, введя действие под названием "ничего не меняй".
[2] Тезис назван в честь Алана Тьюринга и Алонзо Чёрча, которые одновременно и независимо друг от друга пришли к этому выводу в 1930 году.