Математическая логика и теория алгоритмов. Стенюшкина В.А. - 62 стр.

(Иногда считают указатель неподвижным, а ленту движущийся.) Говорят так-
же, что машина в данный такт «обозревает» соответствующую ячейку.
      4) Устройство управления – воображаемый механизм, который в зависи-
мости от состояния воспринимаемой ячейки и состояния внутренней памяти
может изменить состояние воспринимаемой ячейки и положение указателя,
сдвинув его на соседнюю ячейку влево или вправо. При этом, если необходимо,
пристраиваются новые ячейки. Если в некотором такте времени внутренняя па-
мять машины приходит в заключительное состояние q0, то дальнейших измене-
ний в машине не происходит, и машина называется остановившейся.
      Состоянием машины Тьюринга, или конфигурацией, называется слово aj1
aj2 … qi ajk …ajr, образованное вставкой символа внутреннего состояния перед
символом обозреваемой ячейки в слове состояния ленты. Это слово конфигура-
ции называется машинным словом.
      Работа машины состоит в том, что из данного состояния по истечении та-
кта времени она переходит в следующее состояние и так далее. При этом, если
машина, имея внутреннее состояние qi и воспринимая ячейку в состоянии aj,
переводит внутреннюю память в состояние qs, изменяет aj на аt и передвигает
указатель, то говорят, что машина выполняет команду qiaj→ qsаt D, где D – один
из символов: L – сдвиг влево, R – сдвиг вправо, Е – нет сдвига. Совокупность
всех команд, которые может выполнять машина, называется ее программой.
Предполагается, что для каждой пары qi aj имеется не более одной команды.
      Таким образом, машина Тьюринга считается заданной, если заданы ее
внешний, внутренний алфавиты и программа.
      Пример - Пусть А = 0,1, Q = q0, q1, q2, программа Р =  q10 → q20 R,
q20→ q01Е, q11→ q11 R, q21→ q21R, начальное слово µ0 = q111. Тогда, приме-
няя символ перехода состояний =, имеем: q11= 1 q11= 11 q10= 110 q20= 110
q01. Обозначая заключительное слово через µ и символ перехода с произволь-
ным числом тактов − , можно записать: µ0 −P µ. Если за конечное число ша-
гов внутреннее состояние переходит в q0, то говорят, что машина Тьюринга
применима к данному слову. В противном случае машина Тьюринга называется
«работающей вечно», или неприменимой к данному слову. В частности, возмо-
жно зацикливание или отсутствие подходящей команды. Существует много
модификаций машин Тьюринга, в том числе, многоленточные МТ, имеющие по
одному или несколько указателей на каждой из лент. Есть основания считать,
что уточнение общего представления об алгоритме в алфавите, произведенное с
помощью МТ, является адекватным. В теории алгоритмов известно следующее
соглашение.
      ТЕЗИС ТЬЮРИНГА Для всякого алгоритма А в каком- либо алфавите
может построен тьюринговый алгоритм, дающий при одинаковых исходных
данных те же результаты, что и алгоритм А.
      Согласно этому тезису, всякая вычислимая в интуитивном смысле функ-
ция вычислима с помощью некоторой МТ. Принятие тезиса Тьюринга равноси-
льно принятию тезиса Черча для частично рекурсивных функций.
      2.3 Нормальные алгоритмы