Машина Тьюринга Имеется некоторое конечное множество символов S0,S1,..,Sn,

алфавитом машины. В каждой ячейке может быть записан только один

из символов - букв алфавита машины.

Машина обладает некоторым конечным множеством внутренних состояний {q0,q1,...,qm}. В каждый данный момент времени машина находится только в одном из этих состояний. Считаем, что внутренним состоянием q0 обладает каждая машина и q0 называется начальным состоянием.

данный момент времени машина находится только в одном из этих

состояний. Считаем, что внутренним состоянием q0 обладает каждая машина и q0 называется начальным состоянием.

(т.е. стоит на квадрате), содержащий символ Si, и машина находится

во внутреннем состоянии qj, то действие машины определено, и она совершает одно из следующих четырех действий:

1) головка стирает символ Si и записывает на том же квадрате символ Sk;
2) головка перемещается в соседний слева квадрат;
3) головка перемещается в соседний справа квадрат;
4) машина останавливается.

готова к действию в следующий момент времени t+1.

Первые три

из возможных актов действия машины могут быть описаны соответственно следующими упорядоченными четверками символов, которые в дальнейшем будем называть командами:

1) qj Si Sk qr;
2) qj Si L qr;
3) qj Si R qr.

Любая машина имеет конечное (непустое) множество команд.

читающая головка обозревает какой-то символ Sk, а
среди команд машины

нет команды, начинающейся с qjSk.

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

непустое конечное множество упорядоченных четверок символов (команд), удовлетворяющих условиям:

а)

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

Множество всех символов типа Sm, входящих в команды машины, называется алфавитом заданной машины, а входящие в эти команды символы qi называются внутренними состояниями заданной машины Т.

преобразования слова Р машиной Т обязательно указывается положение слова на

ленте относительно читающей головки. Если это не сделано, то предполагается, что читающая головка находится на первой (самой левой) букве слова Р.

1. Пусть задана машина Т командами:
q01Rq1
q1S01q0,
а на ленте записано слово Р=1,

машина Т, начав работу с первой буквы слова Р, приписывает к нему справа
по одной букве 1 на каждом шаге, никогда при этом не останавливаясь.
Следовательно, эта машина неприменима к слову Р.

где ни одно из Si(1≤i≤k) не совпадает с символом 1,

двигается по ленте вправо, пока не встретит вхождение (если такое вообще имеется) символа 1, после чего останавливается.

любому слову Р алфавита {a,b} справа букву а и останавливается.

связать некоторый алгоритм AT,A в алфавите А машины Т. Возьмем

произвольное слово Р алфавита А и запишем его слева направо в квадратах чистой ленты, причем так, чтобы первая (самая левая) буква Р находилась под читающей головкой. Приведем машину Т во внутреннее состояние q0. Машина начинает работать. Если она когда-нибудь остановится, то появившееся в результате на ленте слово алфавита А является значением алгоритма AT,A. Такой алгоритм AT,A называется алгоритмом Тьюринга.

частично вычисляет частичную арифметическую функцию
f(x1,x2,...,xn), если для любых натуральных

k1,k2,...,kn и
некоторых r и m имеем:

тогда и только тогда, когда определена хотя бы одна из
частей этого равенства. Это означает, что применение
алгоритма Тьюринга AT,A к слову

даст слово, означающее с точностью до слов и r0Sm0S
значение функции
f(k1,k2,...,kn)
(SΟ - интерпретируется как изображение пустого квадрата ленты).

натуральных
k1,k2,...,kn и некоторых r и m имеем:
Это означает,

что применение алгоритма Тьюринга AT,A
к слову

даст слово, означающее с

точностью до слов

значение функции f(k1,k2,...,kn), иначе существует машина
Тьюринга, вычисляющая эту функцию для любых значений
её аргументов.

функция вычислима по Тьюрингу.
Для этого построим машину Тьюринга:
эта

машина переводит слово

а последнее слово означает число m+n, следовательно,
эта машина Тьюринга вычисляет функцию х+у.
Итак, функция х+у вычислима по Тьюрингу.

- машина Тьюринга с алфавитом А.
Тогда существует нормальный алгоритм

B над А, вполне
эквивалентный относительно А алгоритму Тьюринга AT,A..

Следствие. Всякая частично вычислимая (вычислимая)
по Тьюрингу функция является частично вычислимой
(вычислимой) по Маркову функцией.

целью дать строгое (с некоторых позиций) определение
алгоритма были введены

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

ему нормальный алгоритм С над А, т.е.
∀P в А:

В(Р) ≈ С(Р).
Иначе эта гипотеза формулируется так.
Всякий алгоритм может быть задан посредством некоторой машины Тьюринга и реализован в этой машине.
Эту гипотезу называют основной гипотезой, или основным тезисом теории алгоритмов, или принципом нормализации, или тезисом Черча.