Многоленточные машины Тыоринга

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

У многоленточной МТ несколько лент, по каждой из которых движется своя головка. Программа такой машины описывает элементарные действия (движение головок, чтение/запись на ленты) в зависимости от состояния машины и содержимого ячеек, над которыми находятся головки.

Определения

Из сделанного выше описания ясно, какие изменения нужно сделать в формальных определениях.

Определение 4.39. к-ленточная Машина Тьюринга — это набор (Л, Q, Qf, 6, qo, Л), где Л, Q — конечные множества, Qf С Q, qo € Q, A € Л, S: Л* x Q —> A* x { — 1,0,1}* x Q (функция, которая называется таблицей переходов).

Как видим, изменения касаются только формата таблицы переходов. Можно, конечно, дать более общее определение, в котором для разных лент используются разные алфавиты, но такое обобщение не представляет интереса, так как не меняет сколь-нибудь существенным образом возможности вычислительной модели.

Определение 4.40. Назовём конфиггдшцией к-летпочной МТ (A, Q. Q f, S, qo, А) набор из к слов (мц,…, Wk) в алфавите ЛиQ, каждое из которых содержит ровно один символ из множества Q, причём этот символ одинаков для всех слов Wi, а первые и последние символы Wi не являются пустыми.

Начальная конфигурация к-ленточной МТ имеет вид (q₀u, q₀,…, q₀), и € (А {Л})*.

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

Аналогично 1-ленточному случаю даются определения расширенной конфигурации, отображений на расширенных конфигурациях и на конфигурациях. Например, для определения отображения на расширенных конфигурациях нужно повторить определение 4.8 для каждого слова Wi конфигурации (г*ц,…, Wk), используя вместо 5(а, q) тройку (iai, ri, q'), где a*, г* — i-e компоненты в первых двух компонентах S (a, q).

Результатом работы многоленточной МТ, которая остановилась в конфигурации (гец,…, гс/ь), является слово гец, из которого вычеркнут символ состояния машины, т. е. содержимое первой ленты в конце работы.

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