Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Реализация алгоритма в машине Тьюринга.
На ряде примеров покажем, как строятся тьюринго-вы машины, реализующие некоторые простые арифметические алгоритмы. Пример 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 в десятичной системе счисления будет иметь вид:
Рис.3 На рис. 4 и 5 выписаны соответствующие конфигурации для n = 183 и n = 399:
Рис.4 Рис.5
Пример 2. Алгоритм сложения натуральных чисел» Пусть на ленту подается два числа, заданных наборами палочек; например, 2 и 3. Нужно сложить эти числа. Будем обозначать символ сложения звездочкой. Таким образом, на ленте машины будет записано слово а0 ||* А0 (1) Требуется предложить функциональную схему, которая, будучи примененной, к слову (1), давала бы в результате сумму чисел 2 и 3, то есть слово а0 А0 (2) Опишем процесс работы машины для решения задачи. Пусть в начальный момент обозревается самая левая палочка. Ее нужно сдвинуть вправо, минуя все палочки и звездочку до тех пор, пока не будет достигнута первая пустая клетка. В эту пустую клетку вписывается первая палочка. Затем нужно вернуться за второй палочкой и ее перенести вправо так же, как это делалось с первой палочкой. После этой процедуры нужно вернуться к звездочке, стереть ее и остановиться. Изобразим все такты работы машины в виде соответствующих конфигураций: 1. a0 ||*
|