15_1 (1006343)
Текст из файла
МАШИНА ТЬЮРИНГА
1. Определение.
Машина Тьюринга является развитием конечного абстрактного автомата, в котором буквы общего алфавита входа и выхода размещаются в клетках бесконечной ленты. Считывающая головка читает значение буквы с клетки и направляет его в автомат А (см.рис.8.1), который вычисляет три функции: функцию выходной буквы, которая записывается в ту клетку, где стояла входная буква, функцию нового состояния автомата и функцию движения ленты.
Обозначая буквы алфавита машины Тьюринга в такте k через 
, состояние автомата в том же такте через 
, а движение ленты в рассматриваемом такте через 
, введем следующие обозначения вышеопределенных функций: 
Алфавит машины Тьюринга и множество состояний ее автомата считаются конечными, а значение функции движения ленты можно задать тремя значениями: движение ленты на одну клетку влево (Л), движение ленты на одну клетку вправо (П) и остановка ленты на месте (О). В примерах для удобства движение ленты относительно головки можно заменить движением головки относительно неподвижной ленты в противоположном направлении.
Кроме указанных функций конкретная машина Тьюринга определяется начальной разметкой ленты и положением головки. Первый такт работы машины задается специальной командой ПУСК, принудительно, независимо от положения головки, значения буквы в клетке и состояния автомата, задающей значения всех функций.
В основаниях математики /1/ показано, что машины Тьюринга реализуют функции, принад
лежащие классу алгоритмически вычислимых или просто вычислимых функций. Каждая конкретная машина Тьюринга задается каким-либо алгоритмом и наоборот.
2. Язык описания конкретной машины Тьюринга.
По известному алгоритму определяются значения всех функций для всех значений пар “буква алфавита-состояние”. Тройка значений 
заносится в таблицу, столбцы которой нумеруются (именуются) состояниями, а строки - буквами алфавита.
В процессе построения конкретной машины Тьюринга рекомендуется оставлять таблицу открытой как по строкам, так и по столбцам. Таблица закрывается после формирования нужного множества состояний и букв алфавита для реализации в машине заданного алгоритма.
Кроме таблицы, описывающей программу работы машины, задается начальное заполнение ленты, положение головки в начале и в конце одной реализации алгоритма и содержание команды ПУСК. На занятии не предполагается рассматривать проблему минимизации числа состояний и букв алфавита для заданного алгоритма и проблему кодирования этих величин. Указанные проблемы рассматриваются студентами при изучении абстрактных и структурных автоматов.
Однако, целесообразно при задании конкретных машин Тьюринга обращать внимание студентов на необходимость выбора лучшего формального алгоритма для решения словесно поставленной задачи.
3. Машина Тьюринга для добавления единицы к целому десятичному числу.
Предположим, что целое число расположено на ленте машины в привычном порядке - младшие разряды справа.
Десятичное кодирование предполагает наличие в алфавите машины цифр от 0 до 9. Если обозначить значение цифры с номером i=0¸(l-1) числа b через 
а значение переноса, поступающего в разряд с номером 
, то значение цифры 
определится как остаток от деления суммы 
на 10, 
, а перенос в следующий разряд как целая часть того же отношения, 
. В каждом добавлении считается, что 
Алгоритм завершает свою работу тогда, когда для некоторого i оказывается 
После чего возможно повторное выполнение алгоритма.
Возможность повторного выполнения алгоритма заставляет нас заполнить все клетки слева от исходного числа нулями. Считая, что главным состоянием машины является состояние добавления единицы в разряд, интерпретируем состояние 
, как состояние, в котором 
тогда состояние 
будет соответствовать случаю
Попав в состояние , машина должна вернуться к исходному положению головки относительно числа и остановиться. Движение от младшего разряда к старшему будем задавать сдвигом головки влево при неподвижной ленте, тогда возвращение в исходное положение будет производиться движением головки вправо в состоянии . Это движение должно быть ограничено. Учитывая, что при движении головки вправо она проходит клетки с записанными в них нулями, в качестве ограничителя может быть использована любая отличная от нуля цифра. Ограничитель должен находиться справа от младшего разряда числа. Начальное и конечное положение головки - над ограничителем. Заполнение клеток справа от ограничителя в рассматриваемой машине безразлично.
В таблице 1 приведена программа машины Тьюринга для десятичного счетчика. Начальная команда имеет вид “ПУСК-1, S0, Л.
Таблица 1
| ak | Sa | S1 |
| 0 | 1,S1,П | 0,S1,П |
| 1 | 2,S1,П | 1,S1,0 |
| 2 | 3,S1,П | - “ - |
| 3 | 4,S1,П | - “ - |
| 4 | 5,S1,П | - “ - |
| 5 | 6,S1,П | - “ - |
| 6 | 7,S1,П | - “ - |
| 7 | 8,S1,П | - “ - |
| 8 | 9,S1,П | - “ - |
| 9 | 0,S1,Л | - “ - |
Таблица 2
| 0 |
| S1 |
| 1 |
| S0 |
| 2 |
| S0 |
| 3 |
| S0 |
| 4 |
| S1 |
| 5 |
| S1 |
| 6 |
| S1 |
В таблице 2 показан пример добавления 1 к числу 499. В этом примере точками над цифрами указано положение головки.
4. Умножение целого десятичного числа на 3.
Так же как в предыдущем случае число на ленте будем располагать слева направо. В отличие от предыдущего случая число на ленте следует ограничить и справа (для начальной остановки) и слева (для указания границы числа). В качестве ограничителя в алфавит можно ввести специальный символ, например # .
Формальный алгоритм определяет цифру 
по цифре 
и переносу 
и формулой 
а перенос в следующий разряд задается выражением 
, i=0¸(l-1), 
Очевидно, что каждому из возможных значений переноса должно соответствовать свое состояние машины 
при 
При умножении может потребоваться перенос левого ограничителя влево на один разряд. Эта процедура может быть выполнена с помощью состояния 
, а возврат головки на левый ограничитель выполняется в состоянии 
В таблице 3 показана программа машины Тьюринга умножения десятичного числа на 3. Начальная команда - ПУСК-#, S0, Л. Заполнение клеток ленты за пределами ограничителей безразлично.
Таблица 3
| ak | S0 | S1 | S1S2 | S3 | S4 |
| 0 | 0,S0,Л | 1,S0,Л | 2,S0,Л | #,S4,П | 0,S4,П |
| 1 | 3,S0,Л | 4,S0,Л | 5,S0,Л | #,S4,П | 1,S4,П |
| 2 | 6,S0,Л | 7,S0,Л | 8,S0,Л | #,S4,П | 2,S4,П |
| 3 | 9,S0,Л | 0,S1,Л | 1,S1,Л | #,S4,П | 3,S4,П |
| 4 | 2,S1,Л | 3,S1,Л | 4,S1,Л | #,S4,П | 4,S4,П |
| 5 | 5,S1,Л | 6,S1,Л | 7,S1,Л | #,S4,П | 5,S4,П |
| 6 | 8,S1,Л | 9,S1,Л | 9,S2,Л | #,S4,П | 6,S4,П |
| 7 | 2,S2,Л | 3,S2,Л | 4,S2,Л | #,S4,П | 7,S4,П |
| 8 | 4,S2,Л | 5,S2,Л | 6,S2,Л | #,S4,П | 8,S4,П |
| 9 | 7,S2,Л | 8,S2,Л | 9,S2,Л | #,S4,П | 9,S4,П |
| # | #,S4,П | 1,S3,Л | 2,S3,Л | #,S4,П | #,S4,0 |
В таблице 4 показан пример умножения на машине Тьюринга числа 7324 на 3. Точка над буквами показывает положение головки.
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
