Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 13 стр.

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

      3.2. Неформальное определение машины Тьюринга
    Машина Тьюринга представляет собой автомат,
      имеющий бесконечную в обе стороны ленту, считывающую головку и управляющее
устройство. Управляющее устройство может находиться в одном из состояний, образующих
конечное множество Q = {q0, q1, ..., qn}. Множество Q называют внутренним алфавитом
машины Тьюринга.
    Принципиальное отличие машины Тьюринга от вычислительных машин состоит в том,
что ее запоминающее устройство представляет собой бесконечную ленту, из-за которой
невозможна ее физическая реализация. Лента разделена на ячейки, в каждой из которых
может быть записан один из символов конечного алфавита A = {a0, a1, . . . , am}, который
называют входным алфавитом машины Тьюринга. Во время функционирования машины
Тьюринга может быть заполнено конечное число ячеек. Считывающая головка в каждый
момент времени обозревает ячейку ленты, в зависимости от символа в этой ячейке и
состояния управляющего устройства записывает в ячейку новый символ или оставляет его
без изменения, сдвигается на ячейку влево или вправо или остается на месте. При этом
управляющее устройство переходит в новое состояние или остается в старом. Среди
состояний управляющего устройства выделены начальное состояние q0 и заключительное
состояние qz.
    Таким образом, за один такт работы машина Тьюринга может считать символ, записать
вместо него новый или оставить его без изменения и сдвинуть головку на одну ячейку влево
или вправо или оставить ее на месте.

      3.3. Формальное определение машины Тьюринга
    Алфавит A – это некоторое конечное множество символов.
    Цепочкой над алфавитом называется последовательность символов из этого алфавита.
Длина цепочки x представляет собой число символов в цепочке и обозначается | x |. Длина
пустой цепочки равна нулю.
    Конкатенацией цепочек X и Y называют цепочку, полученную приписыванием символов
цепочки Y справа к цепочке X.
    Машиной Тьюринга называется семерка вида
    T = (Q, A, δ, p0, pz, a0, a1), где
    Q – конечное множество состояний, в которых может находиться управляющее
устройство;
    A – входной алфавит;
    δ – функция переходов, δ = Q ⋅ A → Q ⋅ A ⋅ S, где