. Словом в данном алфавите называется каждое слово, все буквы которого принадлежат этому алфавиту. Если алфавит состоит из букв А, В, С, то слова А, ВАА, СА, ВВ, ССАВВ будут словами в этом алфавите. Длиной слова называется число входящих в него символов. Так длинами написанных выше слов являются числа 1, 3, 2, 2, 5. Два слова называются графически равными если они имеют одинаковые длины и на соответствующих местах в них находятся равные буквы. Операции применяемые к словам, есть инструкции. Мы говорим, что инструкция примененная к слову 1 переводит слово 1 в слово 2. Слово 1 и слово 2 – слова в одном алфавите.
На сегодняшний момент соответствием соответствий является соответствие: «рабочая лента машины Тюринга-Поста»:
| рабочая лента машины Тюринга-Поста |
|---|
| ячейка1 | содержимое ячейки (символ1) |
| ячейка2 | содержимое ячейки (символ2) |
| ячейка3 | содержимое ячейки (символ3) |
| ячейка4 | содержимое ячейки (символ1) |
| ячейка5 | содержимое ячейки (символ3) |
| ячейка6 | содержимое ячейки (символ2) |
и т. д.
Рабочая лента бесконечна. О символы, которые могут записываться как содержание ячейки говорят, что они заданы на определенном алфавите.
Машина Тюринга-Поста– механическое устройство состоящее из следующих основных частей.
1) В машине имеется потенциально неограниченная память, разбитая на отдельные линейно-упорядоченные ячейки. В каждой ячейке может быть записан символ из некоторого конечного алфавита, или она может быть пустой. Считают, что в ячейке записан особый символ, называемый пустым. В каждый момент времени память, обычно называемая рабочей лентой машины, состоит из конечного числа ячеек, однако при необходимости к ней могут быть пристроены слева или справа новые ячейки с записанных в них пустым символом. Рабочая лента и информация, записанная в ней, представляются конечной цепочкой символов над словарем рабочей ленты.
2) Помимо рабочей ленты в машине Тюринга имеется еще и другое запоминающее устройство. Это регистр состояний – особая память, рассчитанная на хранение одного символа. Символ, который запоминается в регистре, выбирается из конечного множества, определяющего множество состояний машины.
3) В каждый момент времени машина Тюринга анализирует не всю информацию, хранящуюся на рабочей ленте, а содержимое лишь одной ячейки этой ленты. Для определения этой ячейки служит управляющая головка, которая всегда указывает на некоторую ячейку рабочей ленты.
Выполняя заданный алгоритм, машина Тюринга последовательно производит ряд элементарных действий, причем каждое такое действие выполняется за один рабочий такт машины. Элементарные действия можно разбить на следующие три группы:
