Операции объединения и пересечения регулярных языков

где — конечное множество состояний; — конечный входной алфавит; — символ, называемый маркером начала ленты; — символ, называемый пустым (или пробелом); — символы, называемые символами направления движения головки; — начальное состояние; — заключительное состояние; — функция переходов, являющаяся отображением вида причем значение , коль скоро оно определено, есть конечное (возможно, и пустое) множество упорядоченных троек из соответствующего декартова произведения.

Функция переходов может быть записана в виде системы команд. Каждая команда есть слово вида

где .

Слово (до стрелки) называется левой частью команды, а слово (после стрелки) — правой частью команды.

Неформально работу машины Тьюринга можно представить следующим образом. Машина имеет устройство управления, которое может находиться в одном из состояний множества , полубесконечную ленту, разделенную на ячейки, в каждой из которой может быть записан символ из алфавита , причем крайняя левая ячейка хранит символ , и головку чтения-записи, которая в каждый момент дискретного времени обозревает какую-то одну ячейку ленты. Символ (пробел) не следует путать с пустой цепочкой — это специальный символ, означающий пустую, т.е. не хранящую символов алфавита , ячейку ленты. Команда, записанная выше, разрешает машине Тьюринга, устройство управления которой находится в состоянии , а головка обозревает ячейку, хранящую символ , перевести устройство управления в состояние , записав в обозреваемую ячейку символ (который может и совпадать с ), и оставить головку на прежнем месте, если , сдвинуть ее на одну ячейку влево, если , или на одну ячейку вправо, если .

Будем говорить, что машина Тьюринга применима к слову , если из конфигурации выводится конфигурация для некоторого .

Слово будем называть в этом случае результатом применения машины Тьюринга к слову и обозначать его . Факт применимости машины к слову будем обозначать ; если же не применима к , то будем записывать .

Множество всех слов , таких, что , называется областью применимости машины Тьюринга .

Словарная функция в алфавите называется вычислимой по Тьюрингу, если существует такая машина Тьюринга с входным алфавитом , содержащим , что

Тезис Черча-Тьюринга - для любой интуитивно вычислимой функции существует вычисляющая её значения машина Тьюринга.

28. Конфигурации и вычисления машин Тьюринга. Универсальная вычислимая функция. Теорема Клини о нормальной форме.

Конфигурация машины Тьюринга есть кортеж

Из конфигурации непосредственно выводится конфигурация , если .

Из конфигурации непосредственно выводится конфигурация , если .

Из конфигурации непосредственно выводится конфигурация , если .

Выводом на множестве конфигураций машины Тьюринга называется произвольная последовательность конфигураций , такая, что ( если существует).

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

Конфигурация есть тройка (состояние, часть цепочки на ленте до головки, часть цепочки на ленте, первый символ которой обозревается головкой). При этом, по соглашению, любая цепочка из множества (для фиксированного ) отождествляется с цепочкой , т.е. можно отбрасывать любое число пробелов в конце слова.