Машина тьюринга сложение двух чисел

На ряде примеров покажем, как строятся тьюринго-вы машины, реализующие некоторые простые арифметические алгоритмы.

Пример 1.Реализация в машине Тьюринга алгоритма перехода от n к n+1 в десятичной системе счисления.

Пусть дана десятичная запись натурального числа п и требуется указать десятичную запись числаn+1, т.е. вычислить функциюf(n) = п + 1.

Ясно, что здесь внешний алфавит машины должен содержать все цифры О, 1, 2, 3, 4, 5, 6, 7, 8, 9 исимвол пустой клеткиa_Q. Числоп будем записывать в десятичной системе на ленте, причем цифры будут помещаться по одной в каждой клетке подряд без пропусков.

Чтобы решить поставленную задачу, машина должна в первом такте работы стереть последнюю цифру числа л, заменить ее цифрой на единицу большей и перейти в стоп-состояние, если последняя цифра была меньше цифры 9.

Бели же последняя цифра числа n была 9, то машина должна, стерев цифру 9, записать в освободившуюся клетку цифру 0 и произвести сдвиг влево к соседнему более высокому разряду, оставаясь в том же начальном состоянии. Здесь во втором такте работы машина должна прибавить единицу к цифре более высокого разряда.

Очевидно, что в случае сдвига влево, управлявшая головка машины может выйти на пустую клетку в случае, когда цифры более высокого разряда нет. При этом машина вписывает в пустую клетку цифру 1.

Из сказанного следует, что при реализации алгоритма вычисления функцииf(n) = n + 1машина может пребывать лишь в двух состоянияхq_l иq₀.

Таким образом, машина Тьюринга, реализующая алгоритм перехода от n кn+1 в десятичной системе счисления будет иметь вид:

a₀
q₁	1 q₀	1 q₀	2 q₀	3 q₀	4 q₀	5 q₀	6 q₀	7 q₀	8 q₀	9 q₀	0 q₁

На рис. 4 и 5 выписаны соответствующие конфигурации для n = 183 и n = 399:

a₀ 399 a₀ q₁
a₀ 183 a₀ q₀	a₀ 390 a₀ q₁
a₀ 184 a₀ q₁	a₀ 300 a₀ q₁
a₀ 400 a₀ q₀

Пример 2. Алгоритм сложения натуральных чисел» Пусть на ленту подается два числа, заданных наборами палочек; например, 2 и 3. Нужно сложить эти числа.

Будем обозначать символ сложения звездочкой. Таким образом, на ленте машины будет записано слово

А0 (1) Требуется предложить функциональную схему, которая, будучи примененной, к слову (1), давала бы в результате сумму чисел 2 и 3, то есть слово а0

А0 (2) Опишем процесс работы машины для решения задачи. Пусть в начальный момент обозревается самая левая палочка. Ее нужно сдвинуть вправо, минуя все палочки и звездочку до тех пор, пока не будет достигнута первая пустая клетка. В эту пустую клетку вписывается первая палочка. Затем нужно вернуться за второй палочкой и ее перенести вправо так же, как это делалось с первой палочкой. После этой процедуры нужно вернуться к звездочке, стереть ее и остановиться. Изобразим все такты работы машины в виде соответствующих конфигураций: 1. a0 ||*

Машина тьюринга сложение двух чисел

»Я не знаю, кто я — Тьюринг, которому снится, что он машина,
или машина, которой снится, что она Тьюринг!».
Дао Программирования

Машина Тьюринга — одна из основных конструкций, которые были предложены для уточнения, или адекватной формализации, понятия алгоритма. Машиной Тьюринга m называется пятёрка (или четвёрка, как на моём сайте, нужно было для лабораторной работы =)))

( Q , T , q 0 , q z , δ ),

где:

Q — конечное множество состояний управляющего устройства;
T — конечное множество символов на ленте — внешний алфавит содержащий символ λ — пустой символ;
q 0 — начальное состояние;
q z — конечное состояние;
δ — так называемая функция перехода — отображение множества Q x T в множество подмножеств Q x T x , где L означает сдвиг головки по ленте влево, R — вправо, S — головка остается на месте (останов работы машины Тьюринга).

Машина Тьюринга работает на неограниченной с обеих сторон ленте, разделённой на ячейки, одну из которых обозревает головка. В любой момент времени все ячейки, кроме конечного числа, заняты пустыми символами. Конфигурацией машины Тьюринга m называется слово вида αq i xβ , где — α и β непустая часть ленты, q i — текущее состояние управляющего устройства, x — обозреваемый головкой символ.

Рисунок 1 — Машина Тьюринга в состоянии q i ,
конфигурация αq i xβ .

За каждый такт работы машины Тьюринга головка считывает обозреваемый символ с ленты и записывает на его место новый, при этом машина переходит в новое состяние q j или остаётся в старом, а головка передвигается на одну позицию влево или вправо, либо остаётся на месте.
Порядок работы машины Тьюринга обычно записывается в виде таблицы, где в каждый столбец первой строки заносится возможное состяние машины Тьюринга q i Є Q , а в каждую строку первого столбца заносится символ внешнего алфавита x Є T . В других ячейках записываются команды исполняемые машиной Тьюринга в состоянии q i при обозревании символа x (ячейка пуста, если предпологается, что символ x не встречается в состоянии q i ). Формат команды задаётся тройкой aKq , где а — символ печатаемый на ленте, К — направление движения головки из , q — новое состояние машины Тьюринга.

Рассмотрим программу сложения двух чисел заданных на ленте в унарной системе счисления для машины Тьюринга. Программа принимает 2 числа разделённых символом разделителя (‘*’), и записывает результат их сложения на ленте сразу за этими числами отделяя его символом ‘=’. Начальное состояние машины Тьюринга — q 0 , а головка обозревает первый символ первого числа. Конечное состояние — q z , при этом головка возвращается к исходной позиции. Программа перед своим завершением должна восстановить исходные данные на ленте.

Рисунок 2 — Пример начального состояния машины Тьюринга

Рисунок 3 — Пример конечного состояния машины Тьюринга

Итак, внешний алфавит для решения данной задачи представляет из себя множество T = < λ , 1, 0, *, =>, а программа выглядит следующим образом:

q 0	q 1	q 2	q 3	q 4	q 5 = q z
1	0 R q 1	1 R q 1	1 R q 2	1 L q 3	1 S q z
0	0 R q 0	1 L q 4
*	* R q 0	* R q 1	* L q 3	* L q 4
=	= L q 4	= R q 2	= L q 3
λ	= R q 2	1 L q 3	λ R q 5

Программа 1 — Программа сложения двух чисел в унарной системе для машины Тьюринга

Как работает данная программа ? Достаточно просто. Она находит очередной символ ‘1’ слогаемых, заменяет его на символ ‘0’ (своеобразная пометка, что этот символ уже обработан) и записывает очередной символ ‘1’ в результат. Затем головка возвращается к началу в поисках символа ‘0’. Если есть ещё символы ‘1’ до символа ‘=’, то повторяем предыдущий шаг, в противном случае — возвращаем головку в исходное состояние, восстанавливая на ленте входные данные (заменяем ‘0’ на ‘1’).

Как же относится к машине Тьюринга сегодня ? Математики считают данную математическую модель удобной для описания алгоритмов и последующей оценки их сложнсти. Считается, что алгоритм любой сложности можно записать в виде программы для машины Тьюрига, в противном случае — задача не имеет чётко формализованного алгоритма её решения. Какова же актуальность данной математической модели сегодня ? На мой взгляд — она полность отсутствует. Современное развитие вычислительной техники ушло слишком далеко, чтобы считать запись алгоритма в виде программы для машины Тьюринга приемлемой. Сам принцип работы современных вычислительных машин в корне отличаестя от идеи бесконечной ленты и «плавающей» по ней головки, и задачи, выполняемые сегодня просто, расписываются в гигантские программы для машины Тьюринга. Мне сложно согласится с мыслью о том, что данная модель позволяет эффективно записать алгоритм и оценить его сложность. К состовлению программы для машины Тьюрига я отношусь больше как к своеобразной головоломке — полезная разминка для мозгов.

Для более близкого знакомства с машиной Тьюринга, рекомендую её имитатор Algo2000 Зартидова Радика. На мой взгляд — это лучшая реализация имитатора машины Тьюринга.

Машина тьюринга сложение двух чисел

6.
Составьте программы для машины Тьюринга, которые выполняют
сложение и вычитание двух чисел в десятичной системе счисления.

ответ

Если при стирании ведущего нуля автомат «попадает» на минус — можно остановить. На ленте останется результат вычетания большего числа из меньшего (отрицательный результат).
Т.е. в ячейке в ряду «-» и колонке «О5» изменить команду: оставить «-«, остаться на месте, останов.

Условие — машина Тьюринга
Число представлено в двоичном формате в различных конечных автоматах, например, 5 представлено как (101), но в случае добавления с использованием машины Тьюринга используется унарный формат. В унарном формате число представлено либо всеми единицами, либо всеми нулями. Например, 5 будет представлен последовательностью из пяти нулей или пяти единиц. 5 = 1 1 1 1 1 или 0 0 0 0 0. Позволяет использовать нули для представления.

Для добавления 2 чисел с использованием машины Тьюринга оба эти числа приводятся в качестве входных данных для машины Тьюринга, разделенных «с».

Примеры — (2 + 3) будут заданы как 0 0 c 0 0 0:

Подход используется —
Преобразуйте 0 в первом числе в X, а затем пройдитесь по всему вводу и преобразуйте первый пробел в 0. Затем двигайтесь влево, игнорируя все 0 и «c». Пройдите позицию рядом с X, а затем повторяйте ту же процедуру до тех пор, пока мы не получим «c» вместо X при возврате. Преобразовать c в пустую и сложение завершено.

Шаг 1: конвертируйте 0 в X и переходите к шагу 2. Если символ «с», то конвертируйте его в пробел (B), двигайтесь вправо и переходите к шагу 6.

Шаг 2: Продолжайте игнорировать 0 и двигайтесь вправо. Не обращайте внимания на «c», двигайтесь вправо и переходите к шагу 3.

Шаг 3: продолжайте игнорировать 0 и двигайтесь вправо. Преобразуйте пробел (B) в 0, переместитесь влево и перейдите к шагу 4.

Шаг 4: продолжайте игнорировать 0 и двигайтесь влево. Не обращайте внимания на «c», двигайтесь влево и переходите к шагу 3.

Шаг 5: продолжайте игнорировать 0 и двигайтесь влево. Не обращайте внимания на X, двигайтесь влево и переходите к шагу 1.

Главная > Документ

Информация о документе

Дата добавления:

Размер:

Доступные форматы для скачивания:

Машина Тьюринга – математическая модель процессов преобразования информации, с ее помощью можно реализовать любой алгоритм.

Эту модель можно представить как устройство, состоящее из следующих частей:

бесконечной или полу бесконечной ленты, разделенной на ячейки,

читающе — записывающей головки,

управляющего устройства, которое за один такт работы машины а) считывает из ячейки символ, б) записывает в него новый (может быть тот же) символ, в) перемещается влево, вправо или остается на месте, г) изменяет состояние.

При составлении алгоритмов на машине Тьюринга обычно используют следующие приемы: 1) машина запоминает тот или иной символ, переходя в различные состояния, 2) отметка просмотренного символа делается с помощью символов внешнего (дополнительного) алфавита.

Будем считать, что рассматриваемые выражения и строки отделяются на ленте слева и справа пробелами и лента бесконечная в оба конца.

Алгоритмы удобно записывать в виде таблицы, где заголовками столбцов являются символы допустимого алфавита, а заголовками строк – состояния машины. В ячейках стоят конфигурации машины, соответствующие определенным символам и состояниям.

Условимся считать, q i – состояния машины, a 0 – пробел, h – заключительное состояние, п – вправо, л – влево, ! – каретка остается на месте. В начале работы каретка машины находится напротив первого слева символа.

Пример 1 . Умножение числа на 2 в десятичной системе счисления.

Машина Тьюринга: описание и примеры машин Тьюринга

Машина Тьюринга — одно из самых интригующих и захватывающих интеллектуальных открытий 20-го века. Это простая и полезная абстрактная модель вычислений (компьютерных и цифровых), которая является достаточно общей для воплощения любой компьютерной задачи. Благодаря простому описанию и проведению математического анализа она образует фундамент теоретической информатики. Это исследование привело к более глубокому познанию цифровых компьютеров и исчислений, включая понимание того, что существуют некоторые вычислительные проблемы, не решаемые на общих пользовательских ЭВМ.

Что это и кто создал

Алан Тьюринг стремился описать наиболее примитивную модель механического устройства, которая имела бы те же основные возможности, что и компьютер. Тьюринг впервые описал машину в 1936 году в статье «О вычислимых числах с приложением к проблеме разрешимости», которая появилась в Трудах Лондонского математического общества.

Машина Тьюринга является вычислительным устройством, состоящим из головки чтения/записи (или «сканера») с бумажной лентой, проходящей через него. Лента разделена на квадраты, каждый из которых несет одиночный символ — «0» или «1». Назначение механизма состоит в том, что он выступает и как средство для входа и выхода, и как рабочая память для хранения результатов промежуточных этапов вычислений.

Из чего состоит устройство

Каждая такая машина состоит из двух составляющих:

Неограниченная лента. Она является бесконечной в обе стороны и разделена на ячейки.
Автомат – управляемая программа, головка-сканер для считывания и записи данных. Она может находиться в каждый момент в одном из множества состояний.

Каждая машина связывает два конечных ряда данных: алфавит входящих символов A = и алфавит состояний Q = . Состояние q0 называют пассивным. Считается, что устройство заканчивает свою работу, когда попадает именно на него. Состояние q1 называют начальным — машина начинает свои вычисления, находясь на старте в нем. Входное слово располагается на ленте по одной букве подряд в каждой позиции. С обеих сторон от него располагаются только пустые ячейки.

Как работает механизм

Машина Тьюринга имеет принципиальное отличие от вычислительных устройств – ее запоминающее приспособление имеет бесконечную ленту, тогда как у цифровых аппаратов такое устройство имеет полосу определенной длины. Каждый класс заданий решает только одна построенная машина Тьюринга. Задачи иного вида предполагают написание нового алгоритма.

Управляющее устройство, находясь в одном состоянии, может передвигаться в любую сторону по ленте. Оно записывает в ячейки и считывает с них символы конечного алфавита. В процессе перемещения выделяется пустой элемент, который заполняет позиции, не содержащие входные данные. Алгоритм для машины Тьюринга определяет правила перехода для управляющего устройства. Они задают головке записи-чтения такие параметры: запись в ячейку нового символа, переход в новое состояние, перемещение влево или вправо по ленте.

Свойства механизма

Машина Тьюринга, как и другие вычислительные системы, имеет присущие ей особенности, и они сходны со свойствами алгоритмов:

Дискретность. Цифровая машина переходит к следующему шагу n+1 только после того, как будет выполнен предыдущий. Каждый выполненный этап назначает, каким будет n+1.
Понятность. Устройство выполняет только одно действие для одной же ячейки. Оно вписывает символ из алфавита и делает одно движение: влево или вправо.
Детерминированность. Каждой позиции в механизме соответствует единственный вариант выполнения заданной схемы, и на каждом этапе действия и последовательность их выполнения однозначны.
Результативность. Точный результат для каждого этапа определяет машина Тьюринга. Программа выполняет алгоритм и за конечное число шагов переходит в состояние q0.
Массовость. Каждое устройство определено над допустимыми словами, входящими в алфавит.

Функции машины Тьюринга

В решении алгоритмов часто требуется реализация функции. В зависимости от возможности написания цепочки для вычисления, функцию называют алгоритмически разрешимой или неразрешимой. В качестве множества натуральных или рациональных чисел, слов в конечном алфавите N для машины рассматривается последовательность множества В – слова в рамках двоичного кодового алфавита В=<0.1>. Также в результат вычисления учитывается «неопределенное» значение, которое возникает при «зависании» алгоритма. Для реализации функции важно наличие формального языка в конечном алфавите и решаемость задачи распознавания корректных описаний.

Программа для устройства

Программы для механизма Тьюринга оформляются таблицами, в которых первые строка и столбец содержат символы внешнего алфавита и значения возможных внутренних состояний автомата — внутренний алфавит. Табличные данные являются командами, которые воспринимает машина Тьюринга. Решение задач происходит таким образом: буква, считываемая головкой в ячейке, над которой она в данный момент находится, и внутреннее состояние головки автомата обусловливают, какую из команд необходимо выполнять. Конкретно такая команда находится на пересечении символов внешнего алфавита и внутреннего, находящихся в таблице.

Составляющие для вычислений

Чтобы построить машину Тьюринга для решения одной определенной задачи, необходимо определить для нее следующие параметры.

Внешний алфавит. Это некоторое конечное множество символов, обозначающихся знаком А, составляющие элементы которого именуются буквами. Один из них — а0 — должен быть пустым. Для примера, алфавит устройства Тьюринга, работающего с двоичными числами, выглядит так: A = <0, 1, а0>.

Непрерывная цепочка букв-символов, записываемая на ленту, именуется словом.

Автоматом называется устройство, которое работает без вмешательства людей. В машине Тьюринга он имеет для решения задач несколько различных состояний и при определенно возникающих условиях перемещается из одного положения в другое. Совокупность таких состояний каретки есть внутренний алфавит. Он имеет буквенное обозначение вида Q=. Одно из таких положений — q1 — должно являться начальным, то есть тем, что запускает программу. Еще одним необходимым элементом является состояние q0, которое является конечным, то есть тем, что завершает программу и переводит устройство в позицию остановки.

Таблица переходов. Эта составляющая представляет собой алгоритм поведения каретки устройства в зависимости от того, каковы в данный момент состояние автомата и значение считываемого символа.

Алгоритм для автомата

Кареткой устройства Тьюринга во время работы управляет программа, которая во время каждого шага выполняет последовательность следующих действий:

Запись символа внешнего алфавита в позицию, в том числе и пустого, осуществляя замену находившегося в ней, в том числе и пустого, элемента.
Перемещение на один шаг-ячейку влево или же вправо.
Изменение своего внутреннего состояния.

Таким образом, при написании программ для каждой пары символов либо положений необходимо точно описать три параметра: a_i – элемент из выбранного алфавита A, направление сдвига каретки («←” влево, «→” вправо, «точка” — отсутствие перемещения) и q_k — новое состояние устройства. К примеру, команда 1 «←” q₂ имеет значение «заместить символ на 1, сдвинуть головку каретки влево на один шаг-ячейку и сделать переход в состояние q₂”.

Машина Тьюринга: примеры

Пример 1. Дана задача построить алгоритм, прибавляющий единицу к последней цифре заданного числа, расположенного на ленте. Входные данные – слово – цифры целого десятичного числа, записанные в последовательные ячейки на ленту. В первоначальный момент устройство располагается напротив самого правого символа – цифры числа.

Решение. В случае если последняя цифра равняется 9, то ее нужно заменить на 0 и затем прибавить единицу к предшествующему символу. Программа в этом случае для данного устройства Тьюринга может быть написана так:

a₀	0	1	2	3	.	7	8	9
q₁	1 H q₀	1 H q₀	2 H q₀	3 H q₀	4 H q₀	.	8 H q₀	9 H q₀	0 λ q₁

Здесь q₁ — состояние изменения цифры, q₀ — остановка. Если в q₁ автомат фиксирует элемент из ряда 0..8, то он замещает ее на один из 1..9 соответственно и затем переключается в состояние q₀, то есть устройство останавливается. В случае если же каретка фиксирует число 9, то замещает ее на 0, затем перемещается влево, останавливаясь в состоянии q₁. Такое движение продолжается до того момента, пока устройство не зафиксирует цифру, меньшую 9. Если все символы оказались равными 9, они замещаются нулями, на месте старшего элемента запишется 0, каретка переместится влево и запишет 1 в пустую клетку. Следующим шагом будет переход в состояние q₀ – остановка.

Пример 2. Дан ряд из символов, обозначающих открывающие и закрывающие скобки. Требуется построить устройство Тьюринга, которое выполняло бы удаление пары взаимных скобок, то есть элементов, расположенных подряд – “( )”. Например, исходные данные: “) ( ( ) ( ( )”, ответ должен быть таким: “) . . . ( (”. Решение: механизм, находясь в q₁, анализирует крайний слева элемент в строке.

a₀	(	)
q₁	a₀ H q₀	( П q₂	) П q₁
q₂	a₀ H q₀	( П q₂	) λ q₃
q₃	a₀ H q₀	a₀ П q₃	a₀ П q1

Состояние q₁: если встречен символ “(”, то совершить сдвиг вправо и переход в положение q₂; если определен “a₀”, то остановка.

Состояние q₂: проводится анализ скобки “(” на наличие парности, в случае совпадения должно получиться “)”. Если элемент парный, то сделать возврат каретки влево и перейти в q₃.

Состояние q₃: осуществить удаление сначала символа “(”, а затем “)” и перейти в q₁.

Элементарная Машина Тьюринга

Введение

Машина Тьюринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.

В состав машины Тьюринга входит бесконечная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.

Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.

Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.[1]

Описание формальной модели алгоритма на основе рекурсивных функций

Определение понятия примитивно рекурсивной функции является индуктивным. Оно состоит из указания класса базовых примитивно рекурсивных функций и двух операторов (подстановки и примитивной рекурсии), позволяющих строить новые примитивно рекурсивные функции на основе уже имеющихся.

К базовым примитивно рекурсивным фунциям относят:

— выбор аргумента [2].

Задание: доказать примитивную рекурсивность функции «ближайшее к n простое число».

Протестируем приведённую выше схему вычисления ближайшего к простого числа на конкретных примерах.

В качестве параметра возьмём простое число 5.

Рисунок 1.1 — Тест алгоритма на числе 5

В качестве параметра возьмём 15:

Рисунок 1.2 — Тест алгоритма на числе 15

Аналитическая модель Машины Тьюринга

Элементарная Машина Тьюринга

Задание: реализовать Машину Тьюринга для вычисления функции получения остатка от деления двух чисел в унарном коде с сохранением данных. Описать полученную машину тремя способами: правилами переходов, таблицей состояний и графом состояний.

Во входных данных находятся делимое и делитель в унарном коде, разделённые символом «*». В выходных данных к входным должна добавиться конструкция «= », где — результат вычислений в унарном коде.

Пример входных данных: 11111111*111

Пример выходных данных: 11111111*111=11

Ниже приведено описание элементарной машины Тьюринга тремя способами: списком правил переходов, таблицей состояний и графом:

> Рисунок 2.1 — Правила переходов для Машины Тьюринга

2.1.6 Описание Машины Тьюринга таблицей состояний

Таблица 2.1 — Таблица состояний Машины Тьюринга