Машина Тьюринга, умножающая число на 2
Машина Тьюринга, умножающая число на 11
На ленте машины Тьюринга находится число, записанное в десятичной системе исчисления. Умножьте это.
Машина Тьюринга: поделить двоичное число с остатком
Дано трехразрядное двоичное число. Осуществить его деление на два с остатком. Число и остаток.
Машина Тьюринга: умножить на 2 число в семеричной системе счисления.
Помогите пожалуйста На ленте машины Тьюринга находится целое положительное число, записанное в.
Оставить на ленте то число, которое больше (машина Тьюринга)
Дано два числа, записанных в унарной системе счисления, разделенных пустым символом. Оставить на.
1. бежим в конец числа:
q1 n->q1 nR
q1 P->q2 PL
где n от 0 до 9
q2 0->q2 0L
q2 1->q2 2L
q2 2->q2 4L
q2 3->q2 6L
q2 4->q2 8L
3. если цифры от 5 до 9, то нужно запомнить 1 и прибавить на следующем шаге
q2 5->q3 0L
q2 6->q3 2L
q2 7->q3 4L
q2 8->q3 6L
q2 9->q3 8L
q3-состояние, когда мы умножаем на 2 и прибавляем 1 к результату
3. если цифры от 0 до 4, то после «избавления» от 1 ничего запоминать не нужно
q3 0->q2 1L
q3 1->q2 3L
q3 2->q2 5L
q3 3->q2 7L
q3 4->q2 9L
4. если цифры от 5 до 9, то после «избавления» от 1, мы снова ее запоминаем
q3 5->q3 1L
q3 6->q3 3L
q3 7->q3 5L
q3 8->q3 7L
q3 9->q3 9L
5. заканчиваем программу, когда встречаем пустой символ
q2 P->q0 N
q3 P->q0 1N
если мы все еще помним 1, а уже число закончилось, то на пустой клетке пишем 1.
Машина Тьюринга для умножения чисел
Машина Тьюринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
==Устройство машины Тьюринга==
В состав машины Тьюринга входит бесконечная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.
Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.
Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.
Содержание
Описание машины Тьюринга
Конкретная машина Тьюринга задается перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj→qi1aj1dk (если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (H)). Для каждой возможной конфигурации имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.
Пример машины Тьюринга
Приведем пример МТ для умножения чисел в унарной системе счисления. Машина работает по следующему набору правил:
| Набор правил | Набор правил |
|---|---|
| q0*→q0R | q4a→q4aR |
| q01→q0R | q4=→q4=R |
| q0×→q1×R | q41→q41R |
| q11→q2aR | q4*→q51R |
| q21→q21L | q5*→q2*L |
| q2a→q2aL | q6a→q61R |
| q2=→q2=L | q6×→q7×R |
| q2×→q3×L | q7a→q7aR |
| q31 → q4aR | q71→q2aR |
| q3a→q3aL | q7=→q8=L |
| q3*→q6*R | q8a→q81L |
| q4×→q4×R | q8×→q9H |
Умножим с помощью МТ 3 на 2 в единичной системе:
В протоколе указаны начальное и конечное состояния МТ, начальная конфигурация на ленте и расположение головки машины (подчеркнутый символ).
Полнота по Тьюрингу
Можно сказать, что Машина Тьюринга представляет собой простейшую вычислительную машину с линейной памятью, которая согласно формальным правилам преобразует входные данные с помощью последовательности элементарных действий. Элементарность действий заключается в том, что действие меняет лишь небольшой кусочек данных в памяти (в случае Машины Тьюринга — лишь одну ячейку), и число возможных действий конечно. Несмотря на простоту машины Тьюринга на ней можно вычислить все, что можно вычислить на любой другой машине, осуществляющей вычисления с помощью последовательности элементарных действий. Это свойство называется полнотой.
Один из естественных способов доказательства того, что алгоритмы вычисления, которые можно реализовать на одной машине, можно реализовать и на другой, — это имитация первой машины на второй.
Как было сказано, на Машине Тьюринга можно имитировать (с помощью задания правил перехода) все другие исполнители, каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
На Машине Тьюринга можно имитировать машину Поста, нормальные алгорифмы Маркова и любую программу для обычных компьютеров, преобразующую входные данные в выходные по какому-либо алгоритму. В свою очередь, на различных абстрактных исполнителях можно имитировать Машину Тьюринга. Исполнители, для которых это возможно, называются полными по Тьюрингу (Turing complete).
Есть программы для обычных компьютеров, имитирующие работу Машины Тьюринга. Но следует отметить, что данная имитация неполная, так как в Машине Тьюринга присутствует абстрактная бесконечная лента. Бесконечную ленту с данными невозможно в полной мере имитировать на компьютере с конечной памятью (суммарная память компьютера — оперативная память, жёсткие диски, различные внешние носители данных, регистры и кэш процессора и др. — может быть очень большой, но, тем не менее, всегда конечна).
Варианты машины Тьюринга
Модель машины Тьюринга допускает расширения. Можно рассматривать машины Тьюринга с произвольным числом лент и многомерными лентами с различными ограничениями. Однако все эти машины являются полными по Тьюрингу и моделируются обычной машиной Тьюринга
Машина Тьюринга, работающая на полубесконечной ленте
В качестве примера такого сведения рассмотрим следующую теорему: Для любой машины Тьюринга существует эквивалентная машина Тьюринга, работающая на полубесконечной ленте.
Рассмотрим доказательство, приведенное Ю.Г. Карповым в книге «Теория автоматов». Доказательство этой теоремы конструктивное, т.е. мы дадим алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Во-первых произвольно занумеруем ячейки рабочей ленты МТ, т.е. определим новое расположение информации на ленте:
Затем перенумеруем ячейки, причем будем считать, что символ “*” не содержится в словаре МТ:
Наконец, изменим машину Тьюринга, удвоив число ее состояний, и изменим сдвиг головки считывания-записи так, чтобы в одной группе состояний работа машины была бы эквивалентна ее работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе МТ встретится символ ‘*’, значит головка считывания-записи достигла границы зоны:
Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации. Очевидно, что слева от ограничивающих маркеров “*” лента в эквивалентной машине Тьюринга не используется.
Умножить двоичное число на 2 машина тьюринга
Один из важнейших вопросов современной информатики — существует ли формальный исполнитель, с помощью которого можно имитировать любого формального исполнителя. ответ на этот вопрос был получен почти одновременно двумя выдающимися учеными — А. Тьюрингом и Э. Постом. Предложенные ими исполнители отличались друг от друга, но оказалось, что они могут имитировать друг друга, а главное — имитировать работу любого формального исполнителя.
Что такое формальный исполнитель? Что значит — один формальный исполнитель имитирует работу другого формального исполнителя? Если Вы играли в компьютерные игры — на экране объекты беспрекословно подчиняются командам играющего. Каждый объект обладает набором допустимых команд. В то же время компьютер сам является исполнителем, причем не виртуальным, а реальным. Вот и получается, что один формальный исполнитель имитирует работу другого формального исполнителя.
Рассмотрим работу Машины Тьюринга.
Машина Тьюринга представляет собой бесконечную ленту, поделенную на ячейки, и каретку (считывающе-печатающее устройство), которая движется вдоль ленты.
Таким образом Машина Тьюринга формально описывается набором двух алфавитов:
A=
Q=
Каждая ячейка ленты может содержать символ из внешнего алфавита A =
Допустимые действия Машины Тьюринга таковы:
1) записать какой-либо символ внешнего алфавита в ячейку ленты (символ, бывший там до того, затирается)
2) сместиться в соседнюю ячейку
3) сменить состояние на одно из обозначенных символом внутреннего алфавита Q
Машина Тьюринга — это автомат, который управляется таблицей.
Строки в таблице соответствуют символам выбранного алфавита A, а столбцы — состояниям автомата Q =
В каждой клетке таблицы, соответствующей некоторому символу ai и некоторому состоянию qj, находится команда, состоящая из трех частей
· символ из алфавита A
· направление перемещения: «>» (вправо), «
Практическая работа № 36
«Машина Тьюринга»
Файлы-заготовки для выполнения этой практической работы
Файлы-заготовки для выполнения этой практической работы 1. Наберите программу из учебника (или из презентации), которая увеличивает двоичное число на 1 и проверьте её работу.
Будет ли правильно работать эта программа, если вначале каретка расположена справа от числа? Почему?
2. Измените программу для увеличения двоичного числа на 1 так, чтобы она работала правильно, если вначале каретка расположена справа от числа.
3. Опишите алгоритм работы программы для машины Тьюринга:
При каком начальном состоянии ленты и положении каретки эта программа зацикливается?
4. Составьте программу для машины Тьюринга, которая заменяет в двоичном числе все 0 на 1 и все 1 на 0 (из числа 10101100 получается 01010011). Каретка находится слева от числа.
5. Составьте программу для машины Тьюринга, которая умножает двоичное число на 2. Каретка находится над числом.
6. Составьте программу для машины Тьюринга, которая увеличивает троичное число на 1. Каретка находится справа от числа.
При каком начальном положении каретки эта программа зацикливается?
7. Составьте программу для машины Тьюринга, которая уменьшает двоичное число на 1. Каретка находится над числом.
При каком начальном положении каретки эта программа зацикливается?
8. Составьте программу для машины Тьюринга, которая умножает троичное число на 2. Каретка находится над числом.
9. Дана строка, состоящая только из символов «а» и «б». Составьте программу для машины Тьюринга, которая переставляет последний символ в начало строки. Каретка находится над первым символом строки.
10. *Дана строка, состоящая только из символов «а» и «б». Составьте программу для машины Тьюринга, которая сортирует символы, то есть переставляет все буквы «а» в начало строки. Каретка находится над первым символом строки. Используйте состояния, которые перечислены род таблицей.
11. *Составьте программу для машины Тьюринга, которая складывает два числа в двоичной системе, разделенные на ленте знаком «+».
12. *Составьте программы для машины Тьюринга, которые увеличивают и уменьшают на единицу число, записанное в десятичной системе счисления.
13. Составьте программы для машины Тьюринга, которые выполняют сложение и вычитание двух чисел в десятичной системе счисления.
Машина Тьюринга
Первым из всех ученых идею универсального исполнителя предложил Алан Тьюринг (1936г.). Для уточнения понятия алгоритма, им был разработан абстрактный универсальный исполнитель. Его абстрактность заключается в том, что он представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину. Термин «универсальный исполнитель» говорит о том, что данный исполнитель может имитировать любой другой исполнитель. Например, операции, которые выполняют реальные вычислительные машины можно имитировать на универсальном исполнителе. В последствие, придуманная Тьюрингом вычислительная конструкция была названа машиной Тьюринга.
Машина Тьюринга состоит из:
— бесконечной в обе стороны ленты, разделенной на ячейки;
— каретки (читающей и записывающей головки);
Программируемый автомат управляет кареткой, посылая ей команды в соответствии с заложенной в него сменяемой программой. Лента выполняет роль внешней памяти компьютера, автомат — роль процессора, а каретка служит для ввода и вывода данных.
Программа для машины Тьюринга
Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.
Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:
Внешний алфавит. Конечное множество (обозначают буквой А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а0) должна представлять собой пустой символ.
Например, алфавит машины Тьюринга, работающей с двоичными числами, задается в виде A = <0, 1, а0>.
Непрерывную цепочку символов на ленте называют словом.
Автоматом называют устройство, работающее без участия человека. Автомат в машине Тьюринга имеет несколько состояний и при определенных условиях переходит из одного состояния в другое. Множество состояний автомата называют внутренним алфавитом.
Таблица переходов. Описание поведения автомата (каретки) в зависимости от состояния и считанного символа.
Автомат машины Тьюринга в процессе своей работы управляется программой, во время каждого шага которой выполняются последовательно следующие действия:
— Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).
— Передвигаться на одну ячейку влево или вправо.
— Менять свое внутреннее состояние.
Поэтому при составлении программы для каждой пары (символ, состояние) нужно определить три параметра: символ ai из выбранного алфавита A, направление перемещения каретки («←” — влево, «→” — вправо, «точка” — нет перемещения) и новое состояние автомата qk.
Например, команда 1 «←” q2 обозначает «заменить символ на 1, переместить каретку влево на одну ячейку и перейти в состояние q2”.
Предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи.
Примеры работы машины Тьюринга
На ленте записано число в двоичной системе счисления. Каретка находится где-то над числом. Требуется увеличить число на единицу.
Чтобы решить задачу, нам нужно:
-определить алфавит машины Тьюринга А,
— определить набор состояний Q,
— составить программу (т.е. для каждой пары (аi,qi) определить команду автомата.)
Алфавит машины Тьюринга, работающей с двоичными цифрами будет включать цифры 0, 1 и пробел a0. Т.е. А=<1,0,a0>.
Определим возможные состояния:
3) если в рабочей ячейке пробел, переместить каретку влево и перейти в состояние q2
Составим таблицу переходов для q1 т.о.:
1) если в рабочей ячейке записана цифра 0, записать в нее 1 и стоп
2) если в рабочей ячейке записана цифра 1, выполнить перенос в старший разряд — записать в ячейку 0 и переместиться влево.
3) если в рабочей ячейке пробел, записать в нее 1 и стоп.
Добавим в нашу таблицу состояние q2:
Примечание: длина слова и последовательность символов значения не имеют. На рисунке приводится пример последовательности выполнения команд для конкретного случая. Если на ленте будет другое слово, то и последовательность выполнения команд будет другой. Несмотря на это, данная программа для машины Тьюринга (на рисунке – таблица слева) применима к любым словам описанного внешнего алфавита (соблюдается свойство применимости алгоритма ко всем однотипным задачам – массовость).
Вопросы: 1
1. Что такое универсальный исполнитель?
2. Опишите устройство и систему программирования машины Тьюринга.
3. Что такое состояние машины Тьюринга?
4. Сопоставьте устройство машины Тьюринга с устройством компьютера. Какие устройства машины Тьюринга выполняют те же функции, что и аналогичные устройства компьютера?
5. В чем особенность состояний q0 и q1 машины Тьюринга?
6. По какому принципу можно построить программу для машины Тьюринга, которая последовательно выполняет операции А и Б?
7. Сформулируйте тезис Чёрча — Тьюринга.
Компьютерный практикум:
(Методические материалы И.Г. Семакина. Сетевой семинар «Преподавание профильного курса информатики»)
1. Дано целое число в троичной системе счисления; нужно увеличить его на единицу. Для реализации программы использовать учебную модель машины Тьюринга.
2. К данному троичному числу прибавить 2.
3. Прибавление единицы для целых чисел в пятеричной системе счисления
4. Составьте два варианта программы для машины Тьюринга, решающей следующую задачу: целое десятичное число нужно умножить на 10. Головка автомата расположена: а) левее числа на какой-то свободной ячейке; б) правее числа на какой-то свободной ячейке.
5. На ленте машины Тьюринга слева от головки автомата расположена группа подряд стоящих звездочек. Нужно стереть все звездочки и получить на ленте число, равное первоначальному количеству звездочек. Составить программу, реализовать ее на учебной модели машины Тьюринга. Протестировать программу.
Машина Тьюринга программа (К. Поляков)
Дополнительный материал:
1. Тренажер для изучения работы машины: программа (К. Поляков) (пароль к архиву kpolyakov.narod.ru)
4. Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. Машины Тьюринга и алгоритмы Маркова. Решение задач. М.: МГУ, 2006.
1. К.Ю. Поляков, Е.А. Еремин «Элементы теории алгоритмов». Журнал «Информатика» №1, 2012 г.