5.1 Машина Тьюринга

Определение. Многоленточной машиной Тьбринга (МТ) называется свертка: Q, T, I, q₀, q_end. В этом наборе:

Q –множество состояний;

T – множество символов на лентах (алфавит);

I – множество входных символов, I⊆T (входной алфавит);

δ – функция перевода.

δ(q,a₁,a₂,…,a_k) =(q’,(a₁’,m₁),( a₂’,m₂),…,( a_k’,m_k))

a₁,a₂,…,a_k - обозреваемые символы на лентах

a₁’,a₂’,…,a_k’ – новые символы которые записывают вместо a₁,a₂,…,a_k

m₁,m₂,…,m_k – команды перехода к соседней клетке, т. е. либо L (сдвиг в лево ) , либо R (сдвиг вправо), либо S (остановка на месте).

Все символы на лентах – буквы некоторого заранее зафиксированного алфавита

b – специальный выделенный пустой символ (служит для разделения слов)

q₀ – начальное состояние

q_end – конечное состояние машины, попав в которое она останавливается.

С помощью МТ можно реализовать любые програмы написаные на языке высокого уровня.

Входное слово w допускается машиной Тьюринга (ТМ) М, если машина Тьюринга, начав работу из состояния q₀ имея слово w ? записанное на нашей ленте, рано или поздно закончит работу, т.е . попадет в состояние q_end. При этом обычно в ячейках ленты записывается в закодированном виде ответ (см. пример выше).

Определение. Мгновенное описание МТ М – полная информация о МТ в некоторый момент времени t, оно состоит из :

1. текущего состояния q₁ ;

2. содержимого всех лент;

3. номеров обозреваемых ячеек.

Зная мгновенное описание С_t, т.е. всю информацию, мы можем смоделировать по функции переходов δ последующие мгновенное описание С_t+1 и т. д.

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

Тезис Черча. Все что можно числить с помощью некоторого алгоритма (понятие алгоритма не формализируется) может быть описано на языке МТ.