Машина Тьюринга имеет:
- Конечное число состояний , из которых одно принимает , а одно отклоняет . По-видимому, для выполнения задачи требуется пять состояний (четыре неотклоняемых (одно из которых должно быть принято) и одно отклоняющее). Состояния обычно рисуются в виде кружков с меткой (названием штата) внутри каждого. Одним из состояний является начальное состояние ; это отмечено стрелкой, указывающей на это.
- Конечный входной алфавит . {0, 1} или {a, b} являются типичными вариантами выбора.
- Конечный ленточный алфавит , который включает специальный пустой символ , все символы из входного алфавита и, возможно, большее количество символов (но это не обязательно).
- A функция перехода , которая назначает состояние, символ ленты и направление для каждой комбинации состояния и символа ленты. Направление может быть L (слева) или R (справа). Переход рисуется как стрелка из одного состояния в другое (или, возможно, круговая стрелка из состояния обратно в себя), и стрелка помечена двумя символами ленты и либо L, либо R. Очевидно, вам нужно шесть таких стрелок.
Машина также имеет бесконечную ленту , которая разделена на ячейки. В каждой ячейке может быть символ из ленты алфавита. Символы, которые изначально находятся на ленте, называются input to the machine. Машина имеет считывающую головку , которая всегда расположена над одной из ячеек. Допустим, у вас есть стрелка перехода из состояния A в состояние B с символами a, b и R на нем. Это означает: «Если аппарат находится в состоянии A, а символ под головкой ленты - a, то мы должны заменить этот символ на b, перейти в состояние B и переместить считывающую головку на одну ячейку вправо».