9.3. Машины Тьюринга: обсуждение

Разумеется, наше определение содержит много кон­кретных деталей, которые можно было бы изменить. На­пример, лента может быть бесконечной только в одну сторону. Можно придать машине две ленты. Можно счи­тать, что машина может либо написать новый символ, либо сдвинуться, но не то и другое вместе. Можно огра­ничить алфавит, считая, скажем, что в нём должно быть ровно 10 символов. Можно потребовать, чтобы в конце на ленте ничего не было, кроме результата работы (осталь­ные клетки должны быть пусты). Все перечисленные и многие другие изменения не меняют класса вычислимых на машинах Тьюринга функций. Конечно, есть и небе­зобидные изменения. Например, если запретить машине двигаться налево, то это радикально поменяет дело — по существу лента станет бесполезной, так как к старым записям уже нельзя будет вернуться.

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

Если машина видит пробел (входное слово пусто), она кончает работу. Если нет, она запоминает текущий сим­вол и ставит пометку (в алфавите помимо символов 0 и 1 будут ещё их «помеченные варианты» 0 и 1). Затем она движется направо до пустой клетки, после чего пишет там копию запомненного символа. Затем она движется налево до пометки; уткнувшись в пометку, отходит на­зад и запоминает следующий символ и так далее, пока не скопирует всё слово.

Имея некоторый опыт, можно за всеми этими фра­зами видеть конкретные куски программы для маши­ны Тьюринга. Например, слова «запоминает символ и движется направо» означают, что есть две группы состо­яний, одна для ситуации, когда запомнен нуль, другая — когда запомнена единица, и внутри каждой группы за­программировано движение направо до первой пустой клетки.

Имея ещё чуть больше опыта, можно понять, что в этом описании есть ошибка — не предусмотрен механизм остановки, когда всё слово будет скопировано, поскольку копии символов ничем не отличаются от символов исход­ного слова. Ясно и то, как ошибку исправить — надо в качестве копий писать специальные символы 0 и 1, а на последнем этапе все пометки удалить.

76. Покажите, что функция «обращение», переворачиваю­щая слово задом наперёд, вычислима на машине Тьюринга.

Другой пример неформального рассуждения: объ­ясним, почему можно не использовать дополнительных символов, кроме 0, 1 и пустого символа. Пусть есть ма­шина с большим алфавитом из N символов. Построим новую машину, которая будет моделировать работу ста­рой, но каждой клетке старой будет соответствовать блок из к клеток новой. Размер блока (число к) будет фиксирован так, чтобы внутри блока можно было бы за­кодировать нулями и единицами все символы большого алфавита. Исходные символы 0, 1 и пустой будем коди­ровать как 0, за которым идут (к — 1) пустых символов, 1, за которым идут (к — 1) пустых символов, и группу из к пустых символов. Для начала надо раздвинуть буквы входного слова на расстояние к, что можно сделать без дополнительных символов (дойдя до крайней буквы, ото­двигаем её, затем дойдя до следующей, отодвигаем её и крайнюю и так далее); надо только понимать, что можно идентифицировать конец слова как позицию, за которой следует более к пустых символов. Ясно, что в этом про­цессе мы должны хранить в памяти некоторый конечныйобъём информации, так что это возможно. После этого уже можно моделировать работу исходной машины по шагам, и для этого тоже достаточно конечной памяти (т.е. конечного числа состояний), так как нам важна только небольшая окрестность головки моделируемой машины. Наконец, надо сжать результат обратно.

Утверждение о том, что всякая вычислимая функ­ция вычислима на машине Тьюринга, называют тези­сом Тьюринга. Конечно, его смысл зависит от того, что понимать под словами «вычислимая функция». Если пони­мать их в расплывчато-интуитивном смысле («функция вычисляется алгоритмически, то есть по чётким, недву­смысленным, однозначным правилам» или что-то в таком роде), конечно, ни о каком доказательстве тезиса Тью­ринга не может быть речи. Можно лишь говорить, что многовековая практика человечества от Евклида до Кну­та не встретилась с примером алгоритма, который не­льзя было бы записать как программу машины Тьюринга и т. п. Впрочем, ещё один (не слишком убедительный) ар­гумент приведён ниже.

Но если понимать слово «вычислимая» в тезисе Тью­ринга как «вычислимая с помощью программы на Паска­ле» и представить себе на минуту, что синтаксис и семан­тика паскаль-программ точно определены, то тезис Тью­ринга станет уже чётким утверждением, которое может быть истинным или ложным, и которое можно доказы­вать. Конечно, такое доказательство по необходимости должно использовать формальное описание синтаксиса и семантики паскаля, и потому никем не проводилось, но для более простых вычислительных моделей это действи­тельно можно формально доказать. Впрочем, такого ро­да доказательства сродни доказательству корректности длинной программы, и потому желающих их писать и тем более читать немного.

В заключение обсуждения приведём обещанный выше аргумент в пользу того, что любая вычислимая функция вычислима на машине Тьюринга. Пусть есть функция, которую человек умеет вычислять. При этом, он, есте­ственно, должен использовать карандаш и бумагу, таккак количество информации, которое он может хранить «в уме», ограничено. Будем считать, что он пишет на отдельных листах бумаги. Помимо текущего листа, есть стопка бумаг справа и стопка слева; в любую из них мож­но положить текущий лист, завершив с ним работу, а из другой стопки взять следующий. У человека есть каран­даш и ластик. Поскольку очень мелкие буквы на листе неразличимы, число отчётливо различных состояний ли­ста конечно, так что можно считать, что в каждый мо­мент на листе записана одна буква из некоторого конеч­ного (хотя и весьма большого) алфавита. Человек тоже имеет конечную память, так что его состояние есть эле­мент некоторого конечного множества. При этом можно составить некоторую таблицу, в которой записано, чем кончится его работа над листом с данным содержимым, начатая в данном состоянии (что будет на листе, в каком состоянии будет человек и из какой пачки будет взят сле­дующий лист). Теперь уже видно, что действия человека как раз соответствуют работе машины Тьюринга с боль­шим (но конечным) алфавитом и большим (но конечным) числом внутренних состояний.