Игошин Математическая логика и теория алгоритмов (1019110), страница 82
Текст из файла (страница 82)
Затем, двигаясь влево, транспонировать (с помощью В) массив 01"- с каждым соседним слева массивом, пока массив 01"- не выйдет на первое место: (В Б-)лю-3 ° 329 Теперь нужно дойти до крайнего правого массива с помошью (л — 1)-кратного применения правого сдвига Б'. (Б»)»-! ° 01'-01" 0...01"-- 01 «0...901" О. Наконец, нужно стирать последовательно справа налево все массивы елиниц, кроме первого: (ОБ-)" '. 901-'00 "~0... 00.--00 - О ...
00'О. Итак, данную функцию (правильно) вычисляет следующая машина Тьюринга: (Б+) '(В Б-) -'(Б+)"-'(О Б-)"-'. При л = 3, »л = 2 эта машина имеет вид: Б»ВБ-(Б+)2(ОБ-)2 Б+ВБ+(ОБ-)з т. е. совпадает с построенной выше машиной. При и = 2, »л = 2 эта машина имеет вид: Б'(ВБ )Б'(ОБ ) = Б'ВОБ, т.е. также совпадает с соответствующей рассмотренной выше машиной Тьюринга. В задаче Х» 12.29 Задачника подробно разобрана работа машины Тьюринга, являющейся композицией машин ВБ-В, рассмотренных ранее. Эта машина называется «циклический сдвиг» и обозначается Ц.
Слово 0 1"О!»9,01'0 она переводит в слово 0 !'9»01"0 РО. При этом нужно помнить, что машины в композиции ВБ-В работают в очередности справа налево: сначала правая В, затем Б и, наконец, левая В. В задаче Х«17.30 Задачника предлагается проверить, что машина Тьюринга, являюшаяся следуюшей композицией К2 = Б'ГВБ' ВГВБ'ВБ Б ВБ' (называется «копирование»), перерабатывает слово а,01 "0 1» в слово 01 "О!»а«0! "0 1». (à — машина удвоения, см.
задачу М 12.28 в Задачнике.) Тезис Тьюринга (основная гипотеза теория алгоритмов). Вернемся к интуитивному представлению об алгоритмах (см. 5 31). Напомним, одно из свойств алгоритма заключается в том, что он представляет собой единый способ, позволяющий для каждой задачи из некоего бесконечного множества задач за конечное число шагов найти ее решение. На понятие алгоритма можно взглянуть и с несколько иной точки зрения. Каждую задачу из бесконечного множества задач можно выразить (закодировать) некоторым словом некоторого алфавита, а решение задачи — каким-то другим словом того же алфавита.
В результате получим функцию, заданную на некотором подмножестве множества всех слов выбранного алфавита и принимающую значения в множестве всех слов того же алфавита. Решить какую- либо задачу — значит найти значение этой функции на слове, кодируюшем данную задачу. А иметь алгоритм для решения всех задач данного класса — значит иметь единый способ, позволяющий в конечное число шагов «вычислять» значения построенной функ- 330 ции для любых значений аргумента из ее области определения. Таким образом, алгоритмическая проблема — по существу, проблема о вычислении значений функции, заданной в некотором алфавите. Остается уточнить, что значит уметь вычислять значения функции.
Это значит вычислять значения функции с помощью полходящей машины Тьюринга. Для каких же функций возможно их тьюрингово вычисление? Многочисленные исследования ученых, обширный опыт показали, что такой класс функций чрезвычайно широк. Каждая функция, для вычисления значений которой существует какой-нибудь алгоритм, оказывалась вычислимой посредством некоторой машины Тьюринга. Это дало повод Тьюрингу высказать следующую гипотезу, называемую основной гипотезой теории алгоритмов, или тезисом Тьюринга: Дяя нахождения значений функции, заданной в некотором алфавите, тогда и только тогда существует какой-нибудь алгоритм, когда функция является вычислимой по Тьюрингу, т.е.
когда она может вычисляться на подходящей машине Тьюринга. Это означает, что строго математическое понятие вычислимой (по Тьюрингу) функции является по существу идеальной моделью взятого из опыта понятия алгоритма. Данный тезис есть не что иное, как аксиома, постулат, выдвигаемый нами, о взаимосвязях нашего опыта с той математической теорией, которую мы под этот опыт хотим подвести. Конечно же данный тезис в принципе не может быть доказан методами математики, потому что он не имеет внутриматематического характера (одна сторона в тезисе — понятие алгоритма — не является точным математическим понятием).
Он выдвинут исходя из опыта, и именно опыт подтверждает его состоятельность. Точно так же, например, не могут быть доказаны и математические законы механики; они открыты Ньютоном и многократно подтверждены опытом. Впрочем, не исключается принципиальная возможность того, что тезис Тьюринга будет опровергнут. Для этого должна быть указана функция, которая вычислима с помощью какого-нибудь алгоритма, но невычислима ни на какой машине Тьюринга.
Но такая возможность представляется маловероятной (в этом одно из значений гипотезы): всякий алгоритм, который будет открыт, может быть реализован на машине Тьюринга. Дополнительные косвенные доводы в подтверждение этой гипотезы будут приведены в двух последующих параграфах, где рассматриваются другие формализации интуитивного понятия алгоритма и доказывается их равносильность с понятием машины Тьюринга.
Машины Тьюринга н современные электронно-вычнслнтельные машины. Изучение машин Тьюринга и практика составления программ для них закладывают фундамент алгоритмического мышления, сущность которого состоит в том, что нужно уметь разделять тот или иной процесс вычисления или какой-либо другой дея- 33! тельности на простые составляющие шаги. В машине Тьюринга расчленение (анализ) вычислительного процесса на простейшие операции доведено до предельной возможности: распознавание единичного рассмотренного вхождения символа, перемещение точки наблюдения данного ряда символов в соседнюю точку и изменение имеющейся в памяти инфюрмации. Конечно, такое мелкое дробление вычислительного процесса, реализуемого в машине Тьюринга, значительно его удлиняет.
Но вместе с тем логическая структура процесса, расчлененного, образно выражаясь, до атомарного состояния, значительно упрощается и предстает в некотором стандартном виде, весьма удобном для теоретических исследований. (Именно такое расчленение на простейшие составляющие вычислительного процесса на машине Тьюринга дает еще один косвенный аргумент в пользу тезиса Тьюринга, обсуждавшегося в предыдущем пункте: всякая функция, вычисляемая с помощью какого-либо алгоритма, может быть вычислена на машине Тьюринга, потому что каждый шаг данного алгоритма можно расчленить на еще более мелкие операции, которые реализуются в машине Тьюринга.) Таким образом, понятие машины Тьюринга есть теоретический инструмент анализа алгоритмического процесса, а значит, анализа существа алгоритмического мышления.
В современных ЭВМ алгоритмический процесс расчленен не на столь мелкие составляющие, как в машинах Тьюринга. Наоборот, создатели ЭВМ стремятся к известному укрупнению выполняемых машиной процедур (на этом пути, конечно, есть свои ограничения). Так, для выполнения операции сложения на машине Тьюринга составляется целая программа, а в современной ЭВМ такая операция является простейшей. Далее, машина Тьюринга обладает бесконечной внешней памятью (неограниченная в обе стороны лента, разбитая на ячейки). Но ни в одной реально существующей машине бесконечной памяти быть не может.
Это говорит о том, что машины Тьюринга отображают потенциальную возможность неограниченного увеличения объема памяти современных ЭВМ. Наконец, можно провести более подробный сравнительный анализ работы современной ЭВМ и машины Тьюринга. В большинстве ЭВМ принята трехадресная система команд, обусловленная необходимостью выполнения бинарных операций, в которых участвует содержимое сразу трех ячеек памяти. Например, число из ячейки а умножается на число из ячейки Ь, и результат отправляется в ячейку с. Существуют ЭВМ двухадресные и одно- адресные.
Так, одноадресная ЭВМ работает следующим образом: вызывается (в сумматор) число из ячейки а; в сумматоре происходит, например, умножение этого числа на число из ячейки Ь; результат отправляется из сумматора в ячейку с. Машину Тьюрин- 332 га можно считать одиоадресной машиной, в которой система одиоадресных команд упрощена еше больше: на каждом шаге работы машины команда предписывает замену лишь единственного знака, хранящегося в обозреваемой ячейке, а адрес обозреваемой ячейки при переходе к следующему такту может меняться лишь иа единицу (обозрение соседней справа или слева ячейки ленты) или не меняться вовсе.
Это удлиняет процесс, но в то же время резко унифицирует его, делает стандартным, Подводя итоги, можно сказать, что современные ЭВМ есть некие реальные физические модели машин Тьюринга, огрубленные с точки зрения теории, но созданные в целях реализации конкретных вычислительных процессов. В свою очередь, понятие машины Тьюринга и теория таких машин есть теоретический фундамент и обоснование современных ЭВМ. 5 33. Рекурсивные функции Понятие машины Тьюринга — не единственный известный путь уточнения понятия алгоритма.
В настоящем и следующем параграфах будут рассмотрены еще два способа такого уточнения: рекурсивные функции и нормальные алгоритмы Маркова. Происхождение рекурсивных функций. Всякий алгоритм однозначно сопоставляет допустимым начальным данным результат. Это означает, что с каждым алгоритмом однозначно связана функция, которую он вычисляет. В предыдущем параграфе были рассмотрены примеры функций, которые вычисляются с помощью алгоритма, названного машиной Тьюринга. Возникает естественный вопрос, для всякой ли функции существует вычисляющий ее алгоритм. Учитывая сформулированный в 5 32 тезис Тьюринга, утверждающий, что функция вычислима с помощью какого-нибудь алгоритма тогда и только тогда, когда она вычислима с помощью машины Тьюринга, данный вопрос трансформируется в следующий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
