В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 47
Текст из файла (страница 47)
Если же л < 2, то будут стерты все единицы правого массива, звездочка и п единиц левого массива; в итоге на ленте останется т — и единиц левого массива, т.е. в этом случае машина выполняет вычитание числа единиц правого массива из числа единиц левого массива. 12.6. Машина Тьюринга определяется следующей функциональной схемой: Для следующих слов определите, в какое слово переработается каждое из них данной машиной, исходя из начального положения, при котором машина находится в состоянии д1 и обозревается указываемая ячейка: а) 11111 (обозревается ячейка 2, считая слева); б) 111 (обозревается ячейка 1); в) 1111111111 (обозревается ячейка 4); г) 111111 (обозревается ячейка 2); 227 д) 111111111111111 (обозревается ячейка 6). Какова общая закономерность работы машины? 12.7.
Для машины Тьюринга из задачи 12.6 запишите функциональную схему (программу): а) в виде сокращенной таблицы; б) в виде сокращенной последовательности команд. 12.8. Проверьте, что машина Тьюринга с внешним алфавитом А = (ае, Ц и программой (записанной в виде сокращенной таблицы) каждое слово длиной л в алфавите А = (Ц перерабатывает в слово длиной г, где г — остаток от деления п на 3. Чтобы понять действие данного алгоритма, примените его к словам 111, 1111, 11111. 12.9. Машина Тьюринга с внешним алфавитом А = (ае, Ц определяется следующей программой: Остановится ли когда-нибудь эта машина, если она начнет перерабатывать следующее слово (в начальный момент, в состоянии дь машина обозревает ячейку, в которой записана самая левая буква перерабатываемого слова): а) 111аеаа1; б) 11а,ае11а01; в) 111111; г) 1аоаоаоа01' д) 11аеа011; е) 1; ж) 1а01ао1ао1; з) 111; и) 1ае1ае1; к) 11ае11.
Если остановка происходит, то какое слово получается в результате, какая ячейка и в каком (перед остановкой) состоянии обозревается? 12.10. Остановится ли когда-нибудь машина Тьюринга, заданная следующей программой: если она начнет перерабатывать следующее слово, начав в состоянии д, обозревать ячейку, в которой записана самая левая буква перерабатываемого слова: а) 1111а,1„б) 11111; в) 1а,1а,1? 228 Если машина остановится, то какова ее заключительная конфигурация? 12.11. Останавливается ли когда-нибудь машина Тьюринга с внешним алфавитом А = (ам Ц и функциональной схемой при переработке следующих слов (в начальный момент головка машины обозревает ячейку ленты, в которой записана самая левая буква перерабатываемого слова): а) 111ао1ао1; б) 1111; в) 1ао1ао1ао1? Если машина останавливается, то какое слово получается в результате, какая ячейка и в каком состоянии обозревается? Конструирование машин Тьюринга.
Решить задачи 12.12 — 12.31. 12.12. Известно, что на ленте записано слово из и единиц 11 ... 1; и > 1. Постройте машину Тьюринга с внешним алфавитом А = = (ао, Ц, которая отыскивала бы левую единицу этого слова (т.е. приходила бы в состояние, при котором обозревалась бы ячейка с самой левой единицей данного слова, и в этом положении останавливалась), если в начальный момент головка машины обозревает одну из ячеек с буквой данного слова.
12.13. Сконструируйте машину Тьюринга с внешним алфавитом А = (ао, Ц, которая каждое слово в алфавите А, = (Ц перерабатывает в пустое слово, исходя из стандартного начального положения. 12.14. Сконструируйте машину Тьюринга с внешним алфавитом А = (ам Ц, которая каждое слово длиной и в алфавите А, = (Ц перерабатывает в слово длиной п + 1 в том же алфавите А.
У к а з а н и е. Используйте алфавит внутренних состояний из двух букв (см. задачу 12.1). 12.15. На ленте машины Тьюринга записаны два набора единиц 1. Они разделены звездочкой е. Составьте функциональную схему машины так, чтобы она, исходя из стандартного начального положения, выбрала больший из этих наборов, а меньший стерла. Звездочка должна быть сохранена, чтобы было видно, какой из массивов выбран. Рассмотрите примеры работы этой машины применительно к словам: а) 1ь11; б) 11*1; в) 11*111; г) 111ь11; д) 11е1111; е) 1111е11. Указание. Машина может работать, например, следующим образом.
Заменить крайнюю правую единицу на а и из состояния д~ перейти в состояние д,, в котором она должна, ничего не меняя, прошагать к крайней левой единице. Здесь, перейдя в состо- 229 яние дп заменить крайнюю левую единицу на букву а. Далее, перейдя в состояние д„прошагать к крайней правой единице, ничего не меняя. Здесь снова заменить единицу на букву а и вернуться к крайней левой единице и т.д. Дальше программа имеет разветвление. Если, начиная двигаться с правого конца, машина в состоянии йо сделав шаг влево, обозревает ячейку с буквой е, то это означает, что единицы правого массива иссякли. Следовательно, левый массив больше. Тогда машина, перейдя в состояние д,, проходит ячейку с буквой е и во всех последующих ячейках слева проставляет единицы. Затем в состоянии 96 она возвращается к ячейке с ~, минует ее и следует дальше вправо, стирая содержимое ячеек (там записаны буквы а).
Дойдя до первой пустой ячейки, машина останавливается. Если же, начиная двигаться с левого конца, машина в состоянии дн сделав шаг вправо, обозревает ячейку с буквой *, то это означает, что иссякли единицы левого массива. Следовательно, большим оказывается правый массив. Привлекая новые состояния д, и дм строим программу аналогично предыдущему ответвлению. 12.16. Постройте машину Тьюринга, которая бы к натуральному числу в десятичной системе счисления прибавляла единицу. Р е ш е н и е. В качестве внешнего алфавита естественно выбрать алфавит, содержащий наименование всех цифр десятичной системы счисления.
Конечно же, необходим и пустой символ а~. Итак, А = (аа, 1, 2, 3, 4, 5, б, 7, 8, 9, 0». Состояний у машины будет два: да (это, как обычно, остановка) и д, (рабочее состояние). Итак, 0= (9ыуД. Функциональная схема (программа) машины такова: й! -э 9о(~'+ 1) (для ( = О, 1, ..., 8), 9~9 -э д,ОЛ, д~аа -+ да1. Начальное положение машины стандартное. Приведем последовательность конфигураций, получаемых при переработке этой машиной слова 2499: аю2499~9ао =~ ао24~у~90по ~ ао29~400ао ~ ао2да500аа.
Читателю предлагается проанализировать работу машины. 12.17. По аналогии с предыдущей задачей составьте функциональную схему машины Тьюринга, которая бы от натурального числа в десятичной системе счисления отнимала единицу. 12.18. Дана конечная совокупность единиц, вписанных в ячейки, взятые подряд без пропусков. Постройте функциональную схему такой машины Тьюринга, которая записывала бы в десятичной системе число этих единиц, т.е. пересчитывала бы набор единиц (дешифратор).
Р е ш е н и е. Во-первых, обратим внимание на следующее обстоятельство. Данная машина Тьюринга будет иметь дело с теми единицами, количество которых она должна сосчитать, так и с единицей как цифрой в десятичной записи получаемого числа. Чтобы различить зги единицы, для обозначения записанных на ленте единиц необходимо использовать какой-либо другой сим- 230 вол, например палочку ~. Таким образом, алфавит данной машины должен быть таким: А = (О, 1, 2, 3, 4, 5, б, 7, 8, 9, ~). Идея требуемого алгоритма такова. Начиная с правого края записанного массива папочек, машина будет стирать по одной и, перейдя на левый край массива, будет каждый раз прибавлять в десятичной системе счисления по единице в счетчике числа единиц.
Затем — возврат на правый край, стирание следующей палочки, переход на левый край, к счетчику, прибавление к нему очередной единицы и т.д., пока все палочки не будут стерты. Программа счетчика, прибавляющего к десятичной записи натурального числа единицу, нами уже рассмотрена (задача 12.16). Произведем в ее командах некоторую модификацию, чтобы включить этот счетчик составной частью в нашу новую программу. Вопервых, прибавление единицы к цифре каждого разряда числа будем производить не в состоянии йп а в состоянии д,. Во-вторых, после прибавления новой единицы к счетчику работа программы не завершается; головка должна снова двинуться на правый конец массива палочек.
Для обеспечения этого процесса машина после прибавления единицы к счетчику должна переходить не в состояние да (остановки), а в состояние 9ь В итоге получаем следующие модифицированные команды счетчика: д~! — ~ д~(1+ 1) (для 1 = О, 1, ..., 8), дг9 -э д~ОЛ, дра0 -+ дз1. Теперь новый счетчик нужно включить в общую работу машины. Работа начинается из начального стандартного положения, когда в состоянии д, обозревается крайняя правая ячейка, в которой записана палочка.
Палочка должна быть стерта, машина переведена в новое состояние дз и головка должна двинуться влево, к счетчику, чтобы произвести там прибавление единицы. Это достигается командами: д,~ -+ дзааЛ, д,~ -+ 4Л. В конце концов мы выходим из массива палочек и сразу же входим в наш счетчик в состоянии дь Если мы приходим к счетчику в первый раз и в нем либо ничего не записано (ячейка а0), либо записано число О, то счетчик запишет в него (в первую же ячейку слева от массива палочек) число 1. Если же там уже было записано какое-то число, то к нему будет прибавлена единица.
После прибавления к счетчику единицы машина переходит в состояние дь Возврат головки на правый край массива палочек обеспечивается командами: аз!' -э дз1П (для 1= О, 1, 2, —, 9), Чз! — ~ -+ д,~П. Как только будет достигнута первая справа пустая ячейка, машина должна будет вернуться назад (влево) на одну ячейку и перейти в состояние д~. 'дала -+ д~ааЛ. Если при этом в обозреваемой ячейке оказывается палочка, то происходит ее стирание, снова движение к счетчику, прибавление единицы, возврат на правый край. Если же все палочки оказались стерты и, сделав один шаг назад (влево), в состоянии д, машина обнаруживает первую цифру счетчика, то это означает, 231 что все палочки сосчитаны, задача решена и машина должна немедленно остановиться.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
