Устройство машины Тьюринга

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

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

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

Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.

[Править]Описание машины Тьюринга

Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: q_ia_j→q_i1a_j1d_k (если головка находится в состоянии q_i, а в обозреваемой ячейке записана буква a_j, то головка переходит в состояние q_i1, в ячейку вместо a_j записывается a_j1, головка делает движение d_k, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации <q_i, a_j> имеется ровно одно правило (для недетерминированной машины Тьюринга может быть большее количество правил). Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

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

28.АЛГОРИТМА СЛОЖНОСТЬ

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

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

Общей особенностью этих двух конкретных типов сигнализирующих является наличие эффективной процедуры, позволяющей для любого алгоритма (т. е., в частности, для машины Тьюринга, или, точнее, для ее программы), всякого исходного данного хи натурального числа tустановить, верно ли, что процесс применения к хзаканчивается со сложностью t. Это обстоятельство положено в основу аксиоматич. построения теории сложности вычислений (см. [1]). Эффективная процедура г наз. мерой вычислений, если она: 1) всегда заканчивается результатом 0 или 1 применительно к тройкам вида (алгоритм, исходное данное, натуральное число), 2) обладает тем свойством, что для любого алгоритма и исходного данного хравенство верно не более чем при одном натуральном t, причем такое tсуществует тогда и только тогда, когда процесс применения a к хзаканчивается. Вводится сигнализирующая функция по мере r для ': тогда и только тогда, когда 

Таким образом, последнее равенство объявляется эквивалентом высказывания "сложность вычисления на хравна t(по мере r)".

Фиксируя ту или иную меру вычислений, можно ставить задачи о сложности вычисления конкретных функций f, напр, об отыскании алгоритма , вычисляющего f "лучше других алгоритмов". Однако, как показывает теорема ускорения (см. ниже), подобная постановка не всегда правомерна, и речь может идти скорее об описании скорости роста тех сигнализирующих , для к-рых вычисляет f [напр., об отыскании верхней и нижней границ сложности вычисления f - двух функций таких, что существует вычисление функции f, для к-рого , и для всякого алгоритма , вычисляющего f, функция в каком-то смысле мажорирует g].

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

Укажем нек-рые фундаментальные результаты, не зависящие от выбора меры сложности (в том числе и от выбора конкретного уточнения понятия алгоритма) - лишь бы существовала, напр., эффективная возможность взаимного моделирования алгоритмов рассматриваемого типа и обыкновенных машин Тьюринга. (Для простоты можно представить себе дело так, что речь идет о времени вычисления на машинах Тьюринга натураль-нозначных функций натурального аргумента.) Пусть Ти hсуть вычислимые натуральнозначные функции (см. Вычислимая функция).на объектах применения алгоритмов, f - функция, определенная на тех же объектах и принимающая лишь два значения (например, 0 и 1).

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

неверно лишь в ограниченном числе случаев.

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

в случае это приводит к 

для почти всех .