2. Внутренний алфавит машины, состоящий из символов q0, q1, q2, …, qm, п, л, н. Символы q0, q1, q2, …, qm выражают конечное число состояний машины. Для любой машины число состояний фиксировано. Два состояния имеют особое назначение: q1 – начальное состояние машины, q0 – заключительное состояние (стоп-состояние). Символы п, л, н – это символы сдвига (вправо, влево, на месте).
3. Бесконечная в обе стороны лента (внешняя память машины). Она разбита на клет-ки. В каждую клетку может быть записана только одна буква. Пустую клетку бу-дем обозначать символом а0.
4. Управляющая головка. Она передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, т.е. воспринимать символ или печатать символ. В од-ном такте работы машины управляющая головка может сдвигаться только на одну клетку (вправо, влево) или оставаться на месте.
Каждое сведение, хранящееся на ленте, изображается конечным набором символов (букв) внешнего алфавита, отличного от а0. К началу работы машины на ленту подаётся начальное сведение (начальная информация). В этом случае управляющая головка, как правило, находится у крайнего левого знака с указанием начального состояния q1 (началь-ная конфигурация).
А0 а1 а2 а3 … … … аn а0 А0
q0
Работа машины складывается из тактов, по ходу которых происходит преобразова-ние начальной информации в промежуточные информации.
В качестве начальной информации на ленту можно подать любую конечную систе-му знаков внешнего алфавита (любое слово в этом алфавите), расставленную произволь-ным образом по ячейкам. Но в зависимости от того, какая была подана начальная инфор-мация, возможны два случая:
1. После конечного числа тактов машина останавливается (переходит в стоп-состояние q0), и при этом на ленте оказывается изображённой информация В. В та-ком случае говорят, что машина применима к начальной информации А и перера-батывает её в результирующую информацию В.
2. Машина никогда не останавливается (не переходит в стоп-состояние). В таком слу-чае говорят, что машина не применима к начальной информации А.
В каждом такте работы машины она действует по функциональной схеме, которая имеет вид:
aiqj av
