Примеры на составление программ для МТ

Для сокращения формулировки задач введем следующие два соглашения:

• 
  буквой Р будем обозначать входное слово;
  
• 
  буквой А будем обозначать алфавит входного слова, т.е. набор тех симво­лов, из которых и только которых может состоять Р (отметим, однако, что в промежуточных и выходном словах могут появляться и другие символы).
  

1. Перегнать автомат под последнюю цифру числа.

2. Если это цифра от 0 до 8, то заменить ее цифрой на 1 больше и остановиться, например:

3. Если же это цифра 9, тогда заменить ее на 0 и сдвинуть автомат к предыдущей цифре, после чего таким же способом увеличить на 1 эту предпоследнюю цифру, например:

4. Особый случай: в Р только девятки (например, 99). Тогда автомат будет сдвигаться влево, заменяя девятки на нули, и в конце концов окажется под пустой клеткой. В эту пустую клетку надо записать 1 и остановиться (ответом будет 100):

В виде программы для МТ эти действия описываются следующим образом:

q₁ — это состояние, в котором автомат «бежит» под последнюю цифру числа. Для этого он все время движется вправо, не меняя видимые цифры и оставаясь в том же состоянии. Но здесь есть одна особенность: когда автомат находится под последней цифрой, то он еще не знает об этом (ведь он не видит, что записано в соседних клетках) и определит это лишь тогда, когда попадет на пустую клетку. Поэтому, дойдя до первой пустой клетки, автомат возвращается назад под послед­нюю цифру и переходит в состояние q₂ (вправо двигаться уже не надо).

q₂ — это состояние, в котором автомат прибавляет 1 к той цифре, которую видит в данный момент. Сначала это последняя цифра числа; если она - в диапазоне от 0 до 8, то автомат заменяет ее цифрой, которая на 1 больше, и останавливается. Но если это цифра 9, то автомат заменяет ее на 0 и сдвигается влево, оставаясь в состоянии q₂. Тем самым, он будет теперь прибавлять 1 к предыдущей цифре. Если и эта цифра равна 9, то автомат заменяет ее на 0 и сдвигается влево, оставаясь по-прежнему в состоянии q₂, т.к. должен выполнить то же самое действие - увеличить на 1 видимую цифру. Если же автомат сдвинулся влево, а в видимой клетке нет цифры (а есть «пусто»), то он записывает сюда 1 и останавливается.

Отметим, что для пустого входного слова наша задача не определена, поэтому на этом слове МТ может вести себя как угодно. В нашей программе, например, при пустом входном слове МТ останавливается и выдает ответ 1.

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

Именно так мы и будем в дальнейшем записывать программы.