Игошин Математическая логика и теория алгоритмов (1019110), страница 79
Текст из файла (страница 79)
Под алгоритмом понимается четкая система инструкций, определяюшая дискретный детерминированный процесс, ведуший от варьируемых начальных данных (входов) к искомому результату (выходу), если таковой существует, через конечное число тактов работы алгоритма; если же искомого результата не существует, то вычислительный процесс либо никогда не оканчивается, либо попадает в тупик. Отметим в заключение, что сам термин «алгоритм» (или «алгорифм») происходит от имени великого среднеазиатского ученого Мухаммеда аль-Хорезми (787 — ок.
850). В своем трактате, написанном по-арабски, латинская версия которого относится к ХП в. и начинается словами «Р1х11 а!8опгит», т.е. «Сказал альХорезми», им среди прочего была описана индийская позиционная система чисел и сформулированы правила выполнения четырех арифметических действий над числами в десятичной записи. Необходимость уточнения понятия алгоритма.
Понятие алгоритма формировалось с древнейших времен, но до конца первой трети ХХ в. математики довольствовались интуитивным представлением об этом объекте. Термин «алгоритм» употреблялся в математике лишь в связи с теми или иными конкретными алгоритмами. Ут- 316 верждение о существовании алгоритма для решения задач данного типа сопровождалось фактическим его описанием. Парадоксы, обнаруженные в основаниях математики в начале ХХ в., вызвали к жизни различные концепции и течения, призванные эти парадоксы устранить.
В 1920-е гг. вплотную встали вопросы о том, что же такое строгая выводимость и эффективное вычисление. Понятие алгоритма само должно было стать обьектом математического исследования и поэтому нуждалось в строгом определении. Кроме того, к этому вынуждало развитие физики и техники, быстро приближавшее начало века электронно-вычислительных машин. Далее, у математиков начали возникать подозрения в том, что некоторые массовые задачи, по-видимому, не имеют алгоритмического решения. Для точного доказательства несуществования какого-то объекта необходимо иметь его точное математическое определение. Совершенно аналогичная ситуация сложилась в свое время в математике, когда назрела необходимость уточнения таких понятий, как непрерывность, кривая, поверхность, длина„ площадь, объем и т.п. Первые работы по уточнению понятия алгоритма и его изучению, т. е.
по теории алгоритмов, были выполнены в 1936 — 1937 гг. математиками А.Тьюрингом, Э. Постом, Ж. Эрбраном, К. Геделем, А.А. Марковым, А.Черчем. Было выработано несколько опРеделений понятия алгоритма, но впоследствии выяснилось, что все они равносильны между собой, т.е. определяют одно и то же понятие. ф 32. Машины Тьюринга Введение понятия машины Тьюринга явилось одной из первых и весьма удачных попыток дать точный математический эквивалент для общего интуитивного представления об алгоритме.
Это понятие названо по имени английского математика, сформулировавшего его в 1937 г., за 9 лет до появления первой электронно-вычислительной машины. Определение машины Тьюринга. Машина Тьюринга есть математическая (воображаемая) машина, а не машина физическая. Она есть такой же математический объект, как функция, производная, интеграл, группа и т.д. И так же как и другие математические понятия, понятие машины Тьюринга отражает объективную Реальность, моделирует некие реальные процессы. Именно ТьюРинг предпринял попытку смоделировать действия математика (или другого человека), осуществляющего некую умственную созидательную деятельность. Такой человек, находясь в определенном «Умонастроении» (»состоянии»), просматривает некоторый текст. Затем он вносит в этот текст какие-то изменения, проникается 317 новым «умонастроением» и переходит к просмотру последующих записей.
Машина Тьюринга действует примерно также. Ее удобно представлять в виде автоматически работающего устройства. В каждый дискретный момент времени устройство, находясь в некотором состоянии, обозревает содержимое одной ячейки протягиваемой через устройство ленты и делает шаг, заключающийся в том, что устройство переходит в новое состояние, изменяет (или оставляет без изменения) содержимое обозреваемой ячейки и переходит к обозрению следующей ячейки — справа или слева. Причем шаг осуществляется на основании предписанной команды.
Совокупность всех команд представляет собой программу машины Тьюринга. Опишем теперь машину Тьюринга 9 более тщательно. Машина О располагает конечным числом знаков (символов, букв), образующих так называемый внешний алфавит А = (аь, ап ..., а„). В каждую ячейку обозреваемой ленты в каждый дискретный момент времени может быть записан только один символ из алфавита А. Ради единообразия удобно считать, что среди букв внешнего алфавита А имеется «пустая буква», и именно она записана в пустую ячейку ленты. Условимся, что «пустой буквой» или символом пустой ячейки является буква аь. Лента предполагается неограниченной в обе стороны, но в каждый момент времени на ней записано конечное число непустых букв. Далее, в каждый момент времени машина О способна находиться в одном состоянии из конечного числа внутренних состояний, совокупность которых 0 = (д„д„..., д ).
Среди состояний выделяются два — начальное д, и заключительное (или состояние остановки) дь. Находясь в состоянии дп машина начинает работать. Попав в состояние дь, машина останавливается. Работа машины О определяется программой (функциональной схемой). Программа состоит из команд. Каждая команда Т(1, 1) (1 = 1, 2, ..., т; ) = О, 1, ..., и) представляет собой выражение одного из следующих видов: д;а,— » д„а,С; д,а,-» д„а, П; д;а, » д«а,Л, (32.1) где О < й < т; О < к< и.
В выражениях первого вида символ С будем часто опускать. Как же работает машина Тьюринга? Находясь в какой-либо момент времени в незаключительном состоянии (т.е. в состоянии, отличном от д»), машина совершает шаг, который полностью определяется ее текущим состоянием д; и символом а,, воспринимаемым ею в данный момент на ленте. При этом содержание шага регламентировано соответствующей командой Т(у) д,а, » д«а,Х где Х в (С, П, Л). Шаг заключается в том, что: 1) содержимое а,.
обозреваемой на ленте ячейки стирается и на его место записывается символ а, (который может совпадать с а,); 2) машина пере- 318 ходит в новое состояние а, (оно также может совпадать с предыдущим состоянием д); 3) машина переходит к обозрению следующей правой ячейки от той, которая обозревалась только что, если Х= П, или к обозрению следующей левой ячейки, если Х= Л, или же продолжает обозревать ту же ячейку ленты, если Х = С. В следующий момент времени (если д„~ дь) машина делает шаг, регламентированный командой ТЯ, 1): щга,-ь ц„а Х и т.д.
Поскольку работа машины, по условию, полностью определяется ее состоянием д; в данный момент и содержимым ау обозреваемой в этот момент ячейки, то для каждых д; и а, (1= 1, 2, ..., т; ~ = О, 1, ..., и) программа машины должна содержать одну и только одну команду, начинающуюся символами д,а,; Поэтому программа машины Тьюринга с внешним алфавитом А = (аь, аь ..., а„) и алфавитом внутренних состояний Д = (дь, дп ..., а ) содержит т(п+ 1) команд.
Словом в алфавите А или в алфавите Д, или в алфавите А 0 Ц называется любая последовательность букв соответствующего алфавита. Под к-й конфигурацией будем понимать изображение ленты машины с информацией, сложившейся на ней к началу )с-го шага (или слово в алфавите А, записанное на ленту к началу lс-го шага)„с указанием того, какая ячейка обозревается в этот шаг и в каком состоянии находится машина. Имеют смысл лишь конечные конфигурации, т.е.
такие, в которых все ячейки ленты, за исключением, быть может, конечного числа, пусты. Конфигурация называется заключительной, если состояние, в котором при этом находится машина, заключительное. Если выбрать какую-либо незаключительную конфигурацию машины Тьюринга в качестве исходной, то работа машины будет состоять в том, чтобы последовательно (шаг за шагом) преобразовывать исходную конфигурацию в соответствии с программой машины до тех пор, пока не будет достигнута заключительная конфигурация. После этого работа машины Тьюринга считается закончившейся, а результатом работы считается достигнутая заключительная конфигурация.
Будем говорить, что непустое слово а в алфавите А ~ (аь) = (а„..., а,) воспринимается машиной в стандартном положении, если оно записано в последовательных ячейках ленты, все другие ячейки пусты, и машина обозревает крайнюю справа ячейку из тех, в которых записано слово а. Стандартное положение называется начальным (заключительным), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии д, (соответственно в состоянии остановки д,). Наконец, будем говоРить, что слово а перерабатывается машиной в слово (), если от слова а, воспринимаемого в начальном стандартном положении, машина после выполнения конечного числа команд приходит к слову В, воспринимаемому в положении остановки.
319 Применение машин Тьюринга к словам. Проиллюстрируем на примерах все введенные понятия, связанные с машинами Тьюринга. Пример 32.1. Дана машина Тьюринга с внешним алфавитом А = = (О, 1) (здесь 0 — символ пустой ячейки), алфавитом внутренних состояний (2 = (др, дь д~) и со следующей функциональной схемой (программой): д~О -> дзОП; д,О -э д,1; д,1 -+ д~1П; д,! -> д,1П. Посмотрим, в какое слово переработает эта машина слово 101, исходя из стандартного начального положения.
Будем последовательно выписывать конфигурации машины при переработке ею этого слова. Имеем стандартное начальное положение: На первом шаге действует команда: д,! -+ д,1П. В результате на машине создается следующая конфигурация: (2) На втором шаге действует команда: д,Π— > у~ОП и на машине создается конфигурация: (3) Наконец, третий шаг обусловлен командой: дзО-> де1. В результате него создается конфигурация: (4) Эта конфигурация является заключительной, потому что машина оказалась в состоянии остановки де.
Таким образом, исходное слово 101 переработано машиной в слово 10!01. Полученную последовательность конфигураций можно записать более коротким способом. Конфигурация (1) записывается в виде следующего слова в алфавите А () Д: 10д,! (содержимое обозреваемой ячейки записано справа от состояния, в котором находится в данный момент машина).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
