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

Функционирование машины Тьюринга:

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

Машина Тьюринга работает с тремя алфавитами:

1. входной алфавит А ={ а₀ … а_n }, с помощью которого записывается входная, промежуточная, выходная информация. а₀ – пустой символ (незначащий ноль, Ù, В, #), а₁ – 1 или |

2. внутренний алфавит, или алфавит состояний Q ={ q₀ … q_m }, q₀ - заключительное состояние q₁ – начальное состояние q₀…q_n – рабочее состояние

3. алфавит сдвига {Л, В, Н} или {-1, +1, 0} (влево, вправо, на месте)

Машина Тьюринга состоит из следующих частей:

1) лента, потенциально бесконечная в обе стороны. Потенциальная бесконечность означает, что в каждый момент времени на ленте записано конечное слово, но в случае необходимости слева и справа от слова можно достроить необходимое количество ячеек. Лента разделена на ячейки, в каждой из которых записан только один символ входного алфавита. В пустых ячейках записан пустой символ. Если в ячейке информацию необходимо стереть, то достаточно записать в неё пустой символ.

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

3) головка (считывающее и записывающее устройство) в каждый момент времени выполняет следующие действия

· считывает символ, записанный в ячейке

· заменяет его на другой символ алфавита А или оставляет прежним

· сдвигается по ленте вправо, влево на одну ячейку или остается на месте

Правило работы машины Тьюринга:

Машина Тьюринга, находясь в состоянии q_i и считывая символ a_j, записывает в данную ячейку символ а_k, переходит в состояние q_e, осуществляет сдвиг. При этом говорят, что машина выполнила одну команду: a_jq_i ® a_kq_eS SÎ {Л, П, Н}

Совокупность команд называется программой МТ.

a_jq_i – исходные символы команд должны быть различны. Если это условие выполняется, машина называется детерминированной, в противном случае – недетерминированной. Машина работает в дискретные моменты времени.

Таким образом, полное описание машины Тьюринга в каждый момент времени, по которому можно определить её дальнейшее поведение, содержит инфу о:

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

Композицией машин Т₁ ° Т₂ называется машина Т (A, Q, П), где А = А₁ È A₂; Q =(Q₁ È Q₂)\{ q₁₀ } (q₁₀ – заключительное состояние Т₁). Машина Т работает по следующему правилу: U – некоторое слово, Т (U)= Т₁ ° Т₂ (U)= Т₂ (Т₁ (U))

Теорема. Композиция машин Т₁ ° Т₂ существует.

Q₁ ={ q₁₀, q₁, …, q_n }

Q₂ ={ q₂₀, q`<sub>1 ,</sub> …, q`_n }, тогда для построения Q удалим состояние q₁₀, переобозначив его в q _n+1, которое совпадает с начальным состоянием второй машины, а все остальные состояния - в q` _i= q_{n+ 1}.

Вычислимые по Тьюрингу функции:

Функция f(x₁…x_n) называется вычислимой по Тьюрингу, если существует машина Тьюринга, вычисляющая значение этой функции, когда заданы значения аргументов. Функция f(x₁…x_n) задана на множестве натуральных чисел, но теория алгоритмов рассматривает расширенное множество натуральных чисел NÈ {0}.

Аргументы функции f(x₁…x_n) на ленте представляются в виде следующего слова:

Каждому аргументу соответствует столько палочек, каково значение этого аргумента. Если функция f определена на данном наборе значений переменной x₁…x_n, то в результате работы машины Тьюринга на ленте должно остаться такое количество палочек, записанных подряд, которое равно значению функции на данном наборе. Если функция f не определена на данном наборе, то машина Тьюринга должна работать бесконечно.

Начальная конфигурация – считывание крайней левой палочки.