Рис.3 Обратите внимание, что если по ошибке в вход этой машине будет подано “пустое” слово, то она “зациклится”, т.е. будет бесконечно долго писать | . Действительно, единственно некоректной конфигурацией в начале работы будет сочетание qoL. По условию n>0. Поэтому в этом “неправильном” случае машина будет зацикливаться. Нетрудно подсчитать, что сложность этого алгоритма равна n+1. Пример 3. Построить Машину Тьюринга U((n)1)=(n)10 , где n>0 и (n)10 - запись числа n в десятичной системе. Другими словами эта Машина Тьюринга приводит запись числа n из унарной формы в десятичную. Работу этой машины организуем следующим образом. Изначально на ленте находится слово из одних | символов и каретка находится над крайне правым | символом. Сотрем один символ |, а перед словом из символов | поставим цифру 1. Затем опять сотрем крайне правый символ | , а затем увеличим цифровую запись слева от слова из | на 1 и т.д. Обратим внимание, что стирать палочки мы умеем, это делает Машина U2((n)1)=(n-1)1 и увеличивать десятичную запись числа на 1 тоже умеем, это делает машина U1((n)10)=(n+1)10. Программа для этой машины показана на рисунке 4.
|
Главная