Компьютерные инструменты в образовании. 3, 2005 г. Косовская Татьяна Матвеевна
 Скачать 1.17 Mb.
|
|
52 Косовская Т.М. © КОМПЬЮТЕРНЫЕ ИНСТРУМЕНТЫ В ОБРАЗОВАНИИ. № 3, 2005 г. Косовская Татьяна Матвеевна МАШИНЫ ТЬЮРИНГА МАТЕМАТИЧЕСКОЕ ПОНЯТИЕ АЛГОРИТМА Понятие алгоритма прочно вошло в жизнь математиков, а особенно людей, тес- но связанных с вычислительной техникой. Зачастую мы даже не задумываемся, что же это такое, а используем как некое интуи- тивное понятие. Однако история возникно- вения этого понятия восходит к глубокой древности. Термин алгоритм или алгорифм (за- писываемый латинскими буквами как algorithm) имеет в своем составе видоизме- ненное географическое название Хорезм и обязан своим происхождением великому средневековому ученому (приблизительно 783–850 гг.) Мухаммаду ибн Муссе аль Хо- резми (то есть из Хорезма). Первоначально под алгоритмом пони- мали произвольную строго определенную последовательность действий, приводящую к решению той или иной конкретной зада- чи. Еще с античных времен известны алго- ритм Евклида нахождения наибольшего об- щего делителя двух натуральных чисел, ал- горитм деления отрезка в заданном отноше- нии с помощью циркуля и линейки, алго- ритмы умножения и деления чисел (что было очень трудно до повсеместного использова- ния позиционной системы счисления) и т. п. В начале XX века были сформулиро- ваны задачи нахождения единого процесса решения ряда родственных задач с парамет- рами. Если с нахождением такого процесса все было более или менее ясно – достаточ- но предъявить такой процесс, который ре- шает требуемую задачу, то что же делать, если процесс найти не удалось? Мы плохо искали или его не существует? Ответы на эти вопросы были особенно важны в связи с программой Д. Гильберта формализации всей математики. Первые попытки дать математическое определение алгоритма привели приблизи- тельно к следующим требованиям: – Определенность данных (вид исход- ных данных строго определен). – Дискретность (процесс разбивает- ся на отдельные шаги). – Детерминированность (результат каждого шага строго определен в зависимо- сти от данных, к которым он применен). – Элементарность шагов (переход на один шаг прост). – Направленность (что считать ре- зультатом работы алгоритма, если следую- щий шаг невозможен). – Массовость (множество возможных исходных данных потенциально бесконечно). Несмотря на недостатки этого опре- деления (например, что такое «переход на один шаг прост»?), это интуитивное опре- деление может служить для решения многих задач. Однако в современной математике и информатике активно используются алгорит- мы, не удовлетворяющие такому интуитив- ному определению, например недетермини- рованные вычисления, алгоритмы с ораку- лом, «зацикливающиеся» алгоритмы и т.п. Для математического уточнения оп- ределения алгоритма, начиная с 30-х годов Первоначально под алгоритмом понимали произвольную строго определенную последовательность действий, приводящую к решению той или иной конкретной задачи 53 Машины Тьюринга ЗАОЧНАЯ ШКОЛА СОВРЕМЕННОГО ПРОГРАММИРОВАНИЯ XX века, были введены различные матема- тические понятия алгоритма. Одним из наи- более важных для вычислительной техники оказалось понятие машины Тьюринга (или машины Тьюринга-Поста), введенное и опубликованное практически независимо Тьюрингом и Постом. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ Машина Тьюринга является матема- тическим, а не техническим понятием. Од- нако те, кому ближе «железные» объекты, могут представлять ее как вычислительное устройство, имеющее потенциально беско- нечную ленту, разделенную на ячейки (то есть в любой момент работы слева или спра- ва к конечной ленте можно добавить недо- стающую ячейку, содержащую специальный символ, называемый пустым). На этой ленте могут быть записаны слова в некотором зара- нее фиксированном алфавите. По ленте мо- жет перемещаться пишущая–читающая голов- ка, обозревающая одну из ячеек. В зависимо- сти от состояния машины и содержимого обо- зреваемой ячейки, машина может, в соответ- ствии с командой программы, изменить (или не изменять) состояние, заменить (или не заменять) содержимое обозреваемой ячейки, сдвинуть головку на одну ячейку влево, или вправо, или не сдвигать ее. С математической точки зрения, ма- шина Тьюринга задается двумя алфавитами и программой. Алфавит A = {a 1 , ... , a n } – внешний алфавит символов (содержащий, в частности, пустой символ, который здесь мы будем обозначать посредством *). Ал- фавит Q = {q 0 , q 1 , ... , q k } – внутренний ал- фавит состояний. При этом q 1 называется начальным состоянием машины Тьюринга, а q 0 – ее заключительным состоянием. Команда машины Тьюринга имеет вид q r a i ? q t S a j , где S ? {L, R, _} и обозначает, соответствен- но, сдвиг влево, вправо или отсутствие сдви- га головки. Эта команда читается следующим образом: «Если машина Тьюринга находится в состоянии q r и в обозреваемой ячейке за- писан символ a i , то этот символ заменяется на a j , головка производит сдвиг S, и маши- на Тьюринга переходит в состояние q t ». Две команды называются согласован- ными, если они либо имеют различные ле- вые части, либо полностью совпадают. Это требование обеспечивает детерминирован- ность вычисления. Программой машины Тьюринга на- зывается конечное непустое множество по- парно согласованных команд. Конфигурацией машины Тьюринга называется слово вида b 1 ... b p–1 q j b p ... b l , где b 1 ... b p–1 b p ... b l – слово в алфавите A, «переход на один шаг прост» ...те, кому ближе «железные» объекты, могут представлять ее как вычислительное устройство, имеющее потенциально бесконечную ленту, разделенную на ячейки... 54 Косовская Т.М. © КОМПЬЮТЕРНЫЕ ИНСТРУМЕНТЫ В ОБРАЗОВАНИИ. № 3, 2005 г. записанное на ленте (причем слева и спра- ва от этого слова находятся только пустые ячейки ленты, на левом и правом концах этого слова может находиться не более од- ного пустого символа), машина находится в состоянии q j и обозревает p-ый символ этого слова. Для любителей технических устройств приведенная конфигурация соответствует следующей ситуации q j Машина Тьюринга всегда начинает работу в начальной конфигурации вида q 1 X, где X – исходные данные, а заканчивает в случае, когда пришла в заключительное со- стояние q 0 Протоколом работы машины Тью- ринга называется последовательность кон- фигураций, первая из которых является на- чальной, а каждая следующая получена из предыдущей в соответствии с одной из ко- манд. Машина Тьюринга заканчивает ра- боту над данными X, если она пришла в состояние q 0 . Результатом работы машины Тьюринга будет слово, записанное на лен- те. При этом говорят, что машина Тьюрин- га применима к данным X. Если в процессе работы с данными X машина Тьюринга ни- когда не приходит в состояние q 0 или в процессе ее работы ни одна из команд про- граммы не может быть применена, то гово- рят, что машина Тьюринга не применима к данным X. КАК ЖЕ РАБОТАЕТ МАШИНА ТЬЮРИНГА? Рассмотрим несколько примеров ма- шин Тьюринга. Пример 1. Написать машину Тьюринга, вычис- ляющую сумму двух чисел, записанных в унарной системе счисления. Напомним, что вид исходных данных для любого алгоритма должен быть строго определен. Поэтому нельзя написать маши- ну Тьюринга, вычисляющую сумму двух чисел, пока не задана система счисления. Унарная система счисления – это так назы- ваемая единиричная (или палочковая) сис- тема: каково число – столько единичек (па- лочек). Начальная конфигурация машины Тьюринга будет q 1 1...1+1...1 , где количе- ство единиц в первом слагаемом равно x, а количество единиц во втором слагаемом рав- но y. Требуется, чтобы заключительной кон- фигурацией была q 0 1... 1, где количество единиц равно x + y. Для этого разработаем план работы машины Тьюринга. 1. Сотрем первую единицу. 2. Будем сдвигать головку вправо, пока не увидим знак +, который заменим на 1. 3. Будем сдвигать головку влево, пока не увидим знак * (пустой символ). 4. Сдвинем головку на один символ вправо и остановимся. Реализация каждого пункта этого пла- на требует свое собственное состояние, по- этому, записав команды, реализующие пункт плана, обязательно будем менять состояние машины Тьюринга. 1.1) q 1 1 ? q 2 * 2.1) q 2 1 ? q 2 R 1 2.2) q 2 + ? q 3 1 3.1) q 3 1 ? q 3 L 1 4.1) q 3 * ? q 0 R * Запишем протокол работы этой ма- шины Тьюринга, вычисляющей 2 + 3. q 1 11+111 (по 1.1) ? q 2 1+111 (по 2.1) ? 1 q 2 +111 (по 2.2 ) ? 1 q 3 1111 (по 3.1 ) ? q 3 11111 (по 3.1 ) ? q 3 *11111 (по 4.1 ) ? q 0 11111 В этой машине Тьюринга был исполь- зован алфавит {*,1,+}. Однако можно было бы использовать и алфавит {*,1}, при этом исходные данные разделяются знаком * , а в команде 2.2) вместо + следует поставить *. Задание 1. Написать машину Тьюринга, заменя- ющую в записи десятичной дроби знак «,» (запятая) на знак «.» (точка). ***** b 1 ... b p–1 b p b p+1 ... b l ***** ? 55 Машины Тьюринга ЗАОЧНАЯ ШКОЛА СОВРЕМЕННОГО ПРОГРАММИРОВАНИЯ Уровень 1. Определить внешний ал- фавит машины Тьюринга, исходную и зак- лючительную конфигурации. Составить план работы машины Тьюринга. Уровень 2. Написать программу ма- шины Тьюринга и протокол ее работы над числом x (при x = 2,1 и x = 123, 728). Уровень 3. Проведите исследования, сколько конфигураций в процессе работы этой машины Тьюринга появится при рабо- те над числом, имеющим вид a 1 a 2 ... a n , b 1 b 2 ... b m где a 1 a 2 ... a n b 1 b 2 ... b m – десятичные цифры. Пример 2. Написать машину Тьюринга, вычис- ляющую сумму двух чисел, записанных в двоичной системе счисления. Начальная конфигурация машины Тьюринга будет q 1 X*Y, где X и Y – двоич- ные записи натуральных чисел. Требуется, чтобы заключительной конфигурацией была q 0 Z, где Z – двоичная запись суммы. Для этого разработаем план работы машины Тьюринга. 1. «Добежим вправо» до разделяюще- го аргументы пустого символа *. 2. «Добежим вправо» до последней не- помеченной цифры числа Y. (В начальный момент все цифры не помечены.) 3. Запомним эту цифру и пометим ее. Отметим, что машина Тьюринга может за- поминать что-либо только номером состоя- ния. Пометить цифру можно, например, заменив 0 на a, а 1 на b. 4. «Добежим влево» до последней не- помеченной цифры числа X, запомним эту цифру и пометим ее. 5. «Добежим влево» до первой цифры числа X и отступим на одну клетку влево. 6. «Добежим влево» до первой циф- ры числа, полученного сложением просмот- ренных частей X и Y. Отступив на одну клетку влево, запишем сумму запомненных цифр, при этом, если складывались 1 + 1, то записываем 1 и запоминаем, что к сумме следующих двух цифр будет необходимо прибавить 1. 7. «Добежим вправо» до *, стоящей после последней цифры числа вычисленной части суммы и перейдем к выполнению п. 1 нашего плана. 8. Если одно из слов (X либо Y) ока- залось короче другого, то *, стоящую перед соответствующим словом будем запоминать для сложения как цифру 0. 9. Если оба аргумента полностью по- мечены, то сотрем помеченные цифры, пе- реведем головку в начало результирующего слова и остановимся. Как видно из этого плана, программа машины Тьюринга будет очень длинной и потребует большого количества состояний. Поэтому этот пример рассмотрим еще раз для другой модели машины Тьюринга. Пример 3. Написать программу машины Тьюрин- га, осуществляющую удвоение слова в ал- фавите {a, b}. Начальная конфигурация машины Тьюринга имеет вид q 1 X , где X – слово в алфавите {a, b}. Конечная конфигурация имеет вид q 0 X*X. План работы машины Тьюринга. 1. Запомним текущий символ слова и пометим его. Для запоминания символа a будем использовать состояние q 2 , а для за- поминания символа b – состояние q 3 . По- мечать символы будем, записывая вместо них соответственно ? и ? 2. «Добежим вправо» до *, стоящей после исходного слова. Сдвинемся на одну ячейку вправо, изменив состояние q 2 на q 4 , а состояние q 3 на q 5 «Добежим вправо» до разделяющего аргументы пустого символа *. 56 Косовская Т.М. © КОМПЬЮТЕРНЫЕ ИНСТРУМЕНТЫ В ОБРАЗОВАНИИ. № 3, 2005 г. 3. «Добежим вправо» до *, стоящей после дубля скопированной части исходно- го слова и на ее место запишем запомнен- ную букву. Изменим состояние на q 6 4. «Пробежим влево» вдоль дубля ско- пированной части исходного слова и на символе * изменим состояние на q 7 5. «Пробежим влево» вдоль не скопи- рованной части исходного слова до поме- ченного символа. Сдвинем головку на одну ячейку вправо и перейдем в состояние q 8 6. Если обозревается буква, то перей- дем в состояние q 1 и к пункту 1 нашего плана. 7. Если же обозреваемым символом является *, то это означает, что исходное слово полностью переписано, и перейдем в состояние q 9 , сдвинув головку на одну ячей- ку влево. 8. В состоянии q 9 будем двигаться вле- во, каждый раз заменяя a на ? , b на ? , пока не увидим *. 9. Перейдем в заключительное состоя- ние и сдвинем головку на одну ячейку вправо. Для большей наглядности программы в тех случаях, когда не важно, какой имен- но из символов a или b записан в обозрева- емой ячейке, будем в команде писать сим- вол s. Аналогично вместо ? или ? будем писать символ t. Пусть s ? {a, b}, t ? { ? , ? }. 1.1) q 1 a ? q 2 R ? 1.2) q 1 b ? q 3 R ? 2.1) q 2 s ? q 2 R s 2.2) q 3 s ? q 3 R s 2.3) q 2 * ? q 4 R * 2.4) q 3 * ? q 5 R * 3.1) q 4 s ? q 4 R s 3.2) q 5 s ? q 5 R s 3.3) q 4 * ? q 6 a 3.4) q 5 * ? q 6 b 4.1) q 6 s ? q 6 L s 4.2) q 6 * ? q 7 L * 5.1) q 7 s ? q 7 L s 5.2) q 7 t ? q 8 R t 6) q 8 s ? q 1 s 7) q 8 * ? q 9 L * 8.1) q 9 ? ? q 9 L a 8.2) q 9 ? ? q 9 L b 9) q 9 * ? q 0 R * Запишем протокол работы этой ма- шины Тьюринга над словом ba. q 1 ba (по 1.2) ? ? q 3 a (по 2.2) ? ? a q 3 * (по 2.4) ? ? a *q 5 * (по 3.4) ? ? a *q 6 b (по 4.1) ? ? a q 6 *b (по 4.2) ? ? q 7 a*b (по 5.1) ? q 7 ? a*b (по 5.2) ? ? q 8 a*b (по 6) ? ? q 1 a*b (по 1.1) ? ?? q 2 *b (по 2.3) ? ?? * q 4 b (по 3.1) ? ?? *b q 4 * (по 3.3) ? ?? *b q 6 a (по 4.1) ? ?? * q 6 ba (по 4.1) ? ?? q 6 *ba (по 4.2) ? ? q 7 ? ba (по 5.2) ? ?? q 8 *ba (по 7) ? ? q 9 ? *ba (по 8.1) ? q 9 ? a*ba (по 8.2) ? q 9 *ba*ba (по 9) ? q 0 ba*ba Задание 2. Написать машину Тьюринга, осуще- ствляющую инверсию слова в алфавите A = {a, b}. (То есть записывающую после- довательность букв, задающих слово, в об- ратном порядке. Например, инверсией сло- ва АНЯ будет слово ЯНА) Уровень 1. Определить внешний ал- фавит машины Тьюринга, исходную и зак- лючительную конфигурации. Составить план работы машины Тьюринга. Уровень 2. Написать программу ма- шины Тьюринга и протоколы ее работы над словами ba и babba. Уровень 3. Проведите исследования, сколько конфигураций в процессе работы этой машины Тьюринга появится при рабо- те над словом, имеющим длину записи n. МОДИФИКАЦИИ МАШИН ТЬЮРИНГА Из приведенных примеров видно, что писать программы для машин Тьюринга дос- таточно трудоемко, и на первый взгляд со- вершенно непонятно, зачем же это нужно. О том, зачем это нужно, подробно поговорим позже, когда будем рассматри- вать такие понятия, как сложность алгорит- ма (временная и ёмкостная). Сейчас только отметим, что все шаги машины Тьюринга считаются равными в смысле затрат време- ни на их выполнение. Отметим основные положения, опре- деляющие классическую машину Тьюрин- га. Одна лента. Одна головка. Команды со- гласованы. 57 Машины Тьюринга ЗАОЧНАЯ ШКОЛА СОВРЕМЕННОГО ПРОГРАММИРОВАНИЯ Убирая эти ограничения, получим различные модификации машины Тью- ринга. МНОГОЛЕНТОЧНЫЕ МАШИНЫ ТЬЮРИНГА Более точно, следовало бы напи- сать k-ленточные машины Тьюринга при фиксированном k. В этой модели пред- полагается, что имеется k лент, на каж- дой из которых может быть записано свое слово. Головка обозревает одновре- менно по одной ячейке на каждой ленте и, в зависимости от их содержимого, может изменить или не изменять содержимое каж- дой из обозреваемых ячеек, сдвинуться (или не сдвигаться) на одну ячейку влево или вправо, причем на каждой ленте сдвиг мо- жет быть разным. Команда k-ленточной машины Тью- ринга имеет вид ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? k j j k t k i i r a a S S q a a q M M M 1 1 1 где S 1 , ..., S k ? {L, R, _} и обозначают соот- ветственно сдвиги влево, вправо или отсут- ствие сдвига головки. Эта команда читается следующим образом: «Если машина Тьюринга находится в состоянии q r и в обозреваемых ячейках лент записаны соответственно символы a i 1 , ..., a i k , то эти символы заменяются соот- ветственно на a j 1 , ..., a j k , головка произво- дит сдвиги S 1 , ..., S k и машина Тьюринга переходит в состояние q t ». На многоленточной машине Тьюрин- га программы для решения многих задач выглядят гораздо проще, чем соответствую- щие программы для одноленточной маши- ны. Это связано с тем, что использование нескольких лент позволяет иметь одновре- менный доступ к нескольким (точнее, не более чем к k) различным записям. Вернемся к задаче сложения двух чи- сел, записанных в двоичной системе счисле- ния, для решения которой на одноленточ- ной машине Тьюринга был разработан план программы, но сама программа не была при- ведена из-за ее чрезмерной громоздкости. Пример 4. Написать 3-ленточную машину Тью- ринга, вычисляющую сумму двух чисел, за- писанных в двоичной системе счисления. Начальная конфигурация машины Тьюринга будет ? ? ? ? ? ? ? ? ? ? * 1 Y X q , где X и Y – двоич- ные записи натуральных чисел. Требуется, чтобы заключительной конфигурацией была ? ? ? ? ? ? ? ? ? ? Z Y X q 0 , где Z – двоичная запись суммы. Для этого разработаем план работы машины Тьюринга. 1. Установим головку машины на пос- ледние символы записей чисел X и Y. 2. Будем складывать числа «в стол- бик» поразрядно, 3. Запоминая перенос единицы в сле- дующий разряд с помощью дополнительно- го состояния. 4. Символ * перед более короткой за- писью числа будем интерпретировать как цифру 0. 5. При достижении левого края обе- их записей остановиться. 1.1) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? * * 2 1 1 2 1 1 s s R R q s s q В этой модели предполагается, что имеется k лент... 58 Косовская Т.М. © КОМПЬЮТЕРНЫЕ ИНСТРУМЕНТЫ В ОБРАЗОВАНИИ. № 3, 2005 г. 1.2) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? * * * * 2 1 2 1 s R q s q 1.3) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? * * * * 1 1 1 1 s R q s q 1.4) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? * * * * * * 2 1 L L q q 2.1) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0 0 0 * 0 0 2 2 L L L q q 2.2) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1 1 0 * 1 0 2 2 L L L q q 2.3) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1 0 1 * 0 1 2 2 L L L q q 2.4) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0 1 1 * 1 1 3 2 L L L q q 3.1) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1 0 0 * 0 0 2 3 L L L q q 3.2) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0 1 0 * 1 0 3 3 L L L q q 3.3) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0 0 1 * 0 1 3 3 L L L q q 3.4) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1 1 1 * 1 1 3 3 L L L q q 4.1) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0 0 * * 0 * 2 2 L L q q 4.2) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1 1 * * 1 * 2 2 L L q q 4.3) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0 * 0 * * 0 2 2 L L q q 4.4) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1 * 1 * * 1 2 2 L L q q 4.5) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0 0 * * 0 * 2 3 L L q q 4.6) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0 1 * * 1 * 3 3 L L q q 4.7) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0 0 * * 0 2 3 L L q q 4.8) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0 * 1 * * 1 3 3 L L q q 5.1) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? * * * * * * 0 2 R R R q q 5.2) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1 * * * * * 0 3 R R q q Протокол работы этой трехленточной машины Тьюринга для конкретных исход- ных данных желающие могут написать в качестве упражнения. Задание 3. Написать двуленточную машину Тью- ринга, осуществляющую инверсию слова в алфавите A = {a, b}. Уровень 1. Определить внешний ал- фавит машины Тьюринга, исходную и зак- лючительную конфигурации. Составить план работы машины Тьюринга. 59 Машины Тьюринга ЗАОЧНАЯ ШКОЛА СОВРЕМЕННОГО ПРОГРАММИРОВАНИЯ Уровень 2. Написать про- грамму машины Тьюринга и про- токолы ее работы над словами ba и babba. Уровень 3. Проведите иссле- дования, сколько конфигураций в процессе работы этой машины Тьюринга появится при работе над словом, имеющим длину записи n. Сравните полученное количество конфигураций с тем, которое по- лучено в задании 2. МНОГОГОЛОВЧАТЫЕ МАШИНЫ ТЬЮРИНГА Более точно, следовало бы написать m-головчатые машины Тьюринга при фик- сированном m. В этой модели предполага- ется, что имеется m головок, каждая из ко- торых может обозревать одну ячейку. В за- висимости от содержимого всех обозревае- мых ячеек машина может изменить или не изменять содержимое каждой из обозревае- мых ячеек, сдвинуться (или не сдвигаться) на одну ячейку влево или вправо. В этой модели возможны две модификации: зап- рет на то, чтобы разные головки обозревали одну и ту же ячейку, либо головкам припи- сывается приоритет и в случае, если несколь- ко головок обозревают одну и ту же ячейку, команда распространяется только на голов- ку с наивысшим приоритетом, а остальные из этих головок пропускают свой шаг. Команда m-головчатой машины Тью- ринга имеет вид q r (a i 1 , ..., a i m ) ? q t (S 1 , ..., S m )(a j 1 , ..., a j m ), где S 1 , ..., S m ? {L, R, _} и обозначают соот- ветственно сдвиги влево, вправо или отсут- ствие сдвига головки. Задание 4. Написать двухголовчатую машину Тьюринга, осуществляющую инверсию слова в алфавите A = {a, b}. Уровень 1. Определить внешний ал- фавит машины Тьюринга, исходную и зак- лючительную конфигурации. Составить план работы машины Тьюринга. Уровень 2. Написать программу ма- шины Тьюринга и протоколы ее работы над словами ba и babba. Уровень 3. Проведите исследования, сколько конфигураций в процессе работы этой машины Тьюринга появится при рабо- те над словом, имеющим длину записи n. Сравните полученное количество конфигу- раций с тем, которое получено в заданиях 2 и 3. Задание 5. Как можно сделать обобщение машин Тьюринга с k лентами и m головками? Как при этом будет выглядеть команда? Задание 6. Тем, кто прочитал и разобрался в том, что написано выше, вероятно, уже понят- но, что при выполнении действий «в стол- бик» удобно пользоваться многоленточны- ми машинами Тьюринга с количеством лент, совпадающим с количеством записей, запи- санных «в столбик». Что делать, если коли- чество таких записей меняется в зависимос- ти от исходных данных (например, решаем системы с различным количеством уравне- ний)? Что, если сделать «ленту» плоской? Как при этом будет выглядеть команда? НЕДЕТЕРМИНИРОВАННЫЕ МАШИНЫ ТЬЮРИНГА Недетерминированные машины Тью- ринга получаются, если в программе клас- ...имеется m головок, каждая из которых может обозревать одну ячейку. 60 Косовская Т.М. © КОМПЬЮТЕРНЫЕ ИНСТРУМЕНТЫ В ОБРАЗОВАНИИ. № 3, 2005 г. сической машины Тьюринга разрешить ис- пользование несогласованных команд. Как же следует выполнить такую пару команд, если, например, одна предписывает изме- нить содержимое ячейки и в том же состо- янии сдвинуться влево, а другая – не изме- няя содержимого ячейки, сдвинуться впра- во и изменить состояние? Для выполнения такой пары команд лента недетерминиро- ванной машины размножается, и на каж- дой ленте выполняется ровно одна из ко- манд. Дальнейшие вычисления на каждой ленте продолжаются независимо. Недетерминированные машины Тью- ринга, как правило, используются для про- верки истинности утверждений типа ? x P(x) (существует такой объект x, для которого справедливо утверждение P(x)). Для провер- ки истинности таких утверждений, как пра- вило, работу недетерминированной маши- ны Тьюринга разбивают на два этапа: – этап угадывания, при реализации которого лента размножается, и на каждой из них выписывается «претендент» на ре- шение; – этап проверки, при реализации ко- торого машина работает в детерминирован- ном режиме и проверяет конкретного «претендента» на то, является ли он ре- шением. Вместо одного заключительного со- стояния q 0 обычно используют два q Y и q N (Yes и No). Недетерминированная машина Тьюринга заканчивает работу в состоянии q Y, если хоть на одной из лент она пришла в состояние q Y . Если же на всех лентах недетерминированная машина Тьюринга пришла в состояние q N , то и вся машина заканчивает работу в этом состоянии q N ДЛЯ ЧЕГО ЖЕ НУЖНЫ МАШИНЫ ТЬЮРИНГА? Прочитавший эту статью новичок- программист (считающий, что он съел со- баку в программировании) может возразить, что все эти модификации – просто неко- торые достаточно бедные и неудобные язы- ки программирования. Мне, например, при- шлось слышать от одного студента, что в течение многих лет он считал, что старич- ки-программисты работают на машинах Тьюринга, а молодежь – на современных компьютерах. Как уже было сказано, точные по- нятия алгоритма, в частности, машины Тьюринга были введены для доказательства несуществования алгоритма решения тех или иных задач. Однако именно развитие вычислительной техники стимулировало развитие такого направления в математи- ке (и информатике), как теория сложнос- ти алгоритмов. Выяснилось, что для огром- ного класса задач, имеющих алгоритмы их решения, программы, реализующие эти ал- горитмы для очень многих исходных дан- ных, «зависают», то есть время их работы настолько велико, что приходится искать приближенные методы их решения, при- чем, чем больше точность решения зада- чи, тем дольше работает программа. Машины Тьюринга оказались очень удобным математическим аппаратом, по- зволяющим получать оценки как времени реализации алгоритмов (в частности, и на реальных компьютерах), так и размера па- мяти, требуемой для вычислений. Недетерминированные машины Тьюринга получаются, если ... разрешить использование несогласованных команд... 61 Машины Тьюринга ЗАОЧНАЯ ШКОЛА СОВРЕМЕННОГО ПРОГРАММИРОВАНИЯ Косовская Татьяна Матвеевна, кандидат физико-математических наук, доцент кафедры математики Государственного Морского Технического Университета. В настоящее время активно исследу- ется вопрос о соотношении классов P и NP, определенных в терминах машин Тьюринга. Класс P – это класс предикатов (то есть результатом их работы являются два значения – Да или Нет), вычислимых на машинах Тьюринга за число шагов, нахо- дящихся в полиноминальной зависимости от длины записи исходных данных. Класс NP – это класс предикатов, вычислимых на недетерминированных ма- шинах Тьюринга за число шагов, находя- щихся в полиноминальной зависимости от длины записи исходных данных. Вопрос о том, совпадают ли эти два класса или имеется строгое включение P ? NP, объявлен одной из сложнейших задач XXI века. Несмотря на абстрактность этих оп- ределений, вопрос о совпадении или несов- падении этих двух классов означает, напри- мер, возможность или невозможность быс- тро (за полином шагов) решать любую пе- реборную задачу (затратив минуты или часы, вместо годов или столетий, на ее решение). Но об этом в следующий раз. |