3. Машина Тьюринга.

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

Основные положения машины Тьюринга

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

• после конечного числа тактов машина останавливается (имея информацию ), подавая сигнал об остановке. В этом случае МТ применима к информации  и перерабатывает ее в информацию ;

• остановка никогда не наступает. В этом случае МТ не применима к начальной информации .

2. В каждый момент обозревается лишь одна ячейка ленты (памяти). Переход может осуществляться лишь к соседней ячейке (R – вправо, L – влево, N – нет перехода (остаться)). Переход к произвольной ячейке производится путем последовательного перебора всех ячеек, разделяющих текущую и необходимую ячейки. На каждом отдельном такте команда предписывает только замену единственного знака s_i, хранящегося в обозреваемой ячейке, каким-либо другим знаком s_j.

3. Логический блок МТ имеет конечное число состояний {q_i} i=1…m. Знаки R, L, N, q₁,…,q_m – внутренний алфавит машины. Переработанный знак s_j и операция перехода P(t+1) являются функцией s_i и q_k :

s_i(t+1)=f(s_i (t), q_k).

P(t+1)= (s_i(t), q_k)

Программа для МТ определяется тройкой {s_i,P,q}_t+1.

Символ (si)	Состояние
	q1	q2	q3	q4
0	0Rq2	0Nq4	1Nq4	0Nq4
1	1Rq3	1Nq4	0Nq4	1Nq4

Перед началом работы машина Тьюринга находится в состоянии q1 считывания первого операнда.

Данная МТ применима к исходной информации. Останов – состояние q4. Значение s_i в ячейке y не меняется (сохраняется результат).

Если программа для МТ будет определена таблицей переходов

Символ (si)	Состояние
	q1	q2	q3	q4
0	0Rq2	0Nq4	1Nq4	1Nq4
1	1Rq3	1Nq4	0Nq4	0Nq4

то данная МТ будет не применима к исходной информации. В состоянии q4 значение s_i в ячейке y постоянно меняется на противоположное.