Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Реализация алгоритма в машине Тьюринга.
|
|
На ряде примеров покажем, как строятся тьюринго-вы машины, реализующие некоторые простые арифметические алгоритмы.
Пример 1. Реализация в машине Тьюринга алгоритма перехода от n к n+1 в десятичной системе счисления.
Пусть дана десятичная запись натурального числа п и требуется указать десятичную запись числа n+1, т.е. вычислить функцию f(n) = п + 1.
Ясно, что здесь внешний алфавит машины должен содержать все цифры О, 1, 2, 3, 4, 5, 6, 7, 8, 9 исимвол пустой клетки aQ. Число п будем записывать в десятичной системе на ленте, причем цифры будут помещаться по одной в каждой клетке подряд без пропусков.
Чтобы решить поставленную задачу, машина должна в первом такте работы стереть последнюю цифру числа л, заменить ее цифрой на единицу большей и перейти в стоп-состояние, если последняя цифра была меньше цифры 9.
Бели же последняя цифра числа n была 9, то машина должна, стерев цифру 9, записать в освободившуюся клетку цифру 0 и произвести сдвиг влево к соседнему более высокому разряду, оставаясь в том же начальном состоянии. Здесь во втором такте работы машина должна прибавить единицу к цифре более высокого разряда.
Очевидно, что в случае сдвига влево, управлявшая головка машины может выйти на пустую клетку в случае, когда цифры более высокого разряда нет. При этом машина вписывает в пустую клетку цифру 1.
Из сказанного следует, что при реализации алгоритма вычисления функции f(n) = n + 1 машина может пребывать лишь в двух состояниях ql и q 0.
Таким образом, машина Тьюринга, реализующая алгоритм перехода от n кn+1 в десятичной системе счисления будет иметь вид:
| a 0 | |||||||||||
| q 1 | 1 q 0 | 1 q 0 | 2 q 0 | 3 q 0 | 4 q 0 | 5 q 0 | 6 q 0 | 7 q 0 | 8 q 0 | 9 q 0 | 0 q 1 |
Рис.3
На рис. 4 и 5 выписаны соответствующие конфигурации для n = 183 и n = 399:
| a 0 399 a 0 q 1 | |
| a 0 183 a 0 q 0 | a 0 390 a 0 q 1 |
| a 0 184 a 0 q 1 | a 0 300 a 0 q 1 |
| a 0 400 a 0 q 0 |
Рис.4 Рис.5
Пример 2. Алгоритм сложения натуральных чисел» Пусть на ленту подается два числа, заданных наборами палочек; например, 2 и 3. Нужно сложить эти числа.
Будем обозначать символ сложения звездочкой. Таким образом, на ленте машины будет записано слово
а0 ||*
А0 (1) Требуется предложить функциональную схему, которая, будучи примененной, к слову (1), давала бы в результате сумму чисел 2 и 3, то есть слово а0
А0 (2) Опишем процесс работы машины для решения задачи. Пусть в начальный момент обозревается самая левая палочка. Ее нужно сдвинуть вправо, минуя все палочки и звездочку до тех пор, пока не будет достигнута первая пустая клетка. В эту пустую клетку вписывается первая палочка. Затем нужно вернуться за второй палочкой и ее перенести вправо так же, как это делалось с первой палочкой. После этой процедуры нужно вернуться к звездочке, стереть ее и остановиться. Изобразим все такты работы машины в виде соответствующих конфигураций: 1. a0 ||*
|
|