Рис.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.