Файл: Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы.pdf

2. Программа 9~7 (рис. 30). Итак, к началу применения програм­

Рис. 29. для каждого состояния 17 программы 9 ! добав­ ляются еще 7 связанных с q состояний, которые именуются q, q^, qx, qu, qA qA, q'. Итак, число состояний в 8 раз

превосходит число состояний в Эи Проследим теперь за работой программы 9 ! и сравним ее с работой заданной программы D i . По­ ка головка находится внутри зоны, 9 i работает в точности так же, как 9с. Пусть впервые головка вышла на метку Д в некотором состоя­

метка сдвинута вправо и машина продолжает работать так же, как программа 9} в расширенной зоне. Допустим, что головка вышла на метку || в состоянии q (см. рис. 28, д). Поскольку метка || непод­ вижна и, следовательно, зону нельзя расширить влево, то высво­ бождение на левом конце пустой ячейки, необходимой для вычисле­ ний по программе 97, осуществляется так. Всю запись в зоне, вклю­ чая и метку Д, перемещают на одну ячейку вправо, а в освободившую­ ся пустую ячейку по соседству с меткой || помещают головку в том же состоянии q, в котором она первоначально (в поиске «свободного

118

нее по программе, как это происходит. Наткнувшись на || в состоя­ нии q головка уходит вправо (команда || q -* Яг/ц), очищает сосед­ нюю справа ячейку и, запоминая ее содержимое, уходит вправо

ка головка не переместит символ Д, а потом в состоянии q' начнет

Тем самым теорема доказана для случая правой полуленты. Программирующий алгоритм в случае левой полуленты совсем не­

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

Сначала рассмотрим случай, когда каждая ячейка ленты состоит

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

*> Впрочем, можно заметить, что и обычно в реальных ситуа­ циях символ, трактуемый как единый объект, можно рассматривать и как нечто состоящее из двух частей — верхней и нижней, например русские буквы й, ё пли символы типа а', Ь и т. п.

119

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

Рис. 32.

Перейдем к рассмотрению тыоринговых машин с многомерной

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

Р может принимать любое из указанных выше пяти значений. Можно принять следующую концепцию вычисления функции R = / (Я). В исходной конфигурации слово Н записано в строку (по горизон­ тальней строке) и, хотя промежуточная информация может распола­

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

о полуленте. Именно программу машины 9)2 с /е-мерной лентой можно перестроить в программу машины 93с' с обычной лентой, которая в определенном смысле имитирует работу машины 9Л. Однако реали­ зация этой идеи в данном случае несколько сложнее.

§ 13. ОСНОВНАЯ ГИПОТЕЗА ТЕОРИИ АЛГОРИТМОВ

13.1. Гипотеза и ее значение. Разбор предыдущих при­ меров создает впечатление о процессе, происходящем в тыо­ ринговой машине, как о чрезвычайно замедленной кино­ съемке процесса вычисления, выполняемого человеком

120

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

Мы рассмотрим здесь два вопроса, возникающих в связи

сформулировкой гипотезы:

1.В чем заключается значение этой гипотезы для тео­ рии алгоритмов?

2.В чем заключается обоснование гипотезы?

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

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

121