Машина Тьюринга как формальная модель алгоритма. Тезис Тьюринга

Сентябрь 2, 2022

Главная
Алгебра
Машина Тьюринга как формальная модель алгоритма. Тезис Тьюринга

Содержание

2. Неформальное и формальное определение МТ. Конфигурации. УУ Конечное множество состояний УУ: Q={q1,…, qn}. Алфавит: Σ= {a1,…,am}.
3. Примеры простейших машин Тьюринга Дана цепочка из символов 0 и 1. Все нули заменить на 2.
4. Переработка цепочек. Вычислимость по Тьюрингу. Если α1 q0 α2 =>β1 qz β2, то будем говорить, что
5. Вычислимость композиции Композиция g (x) = f2 (f1(x)) T1 и T2 - машины, вычисляющие f1 и
6. Вычислимость на полуленте и с восстановлением df Говорят, что Т вычисляет предикат P(α), если T(α) =
7. Вычислимость разветвления Теорема. Если функции g1(α), g2(α) и предикат Р(α) вычислимы по Тьюрингу, то разветвление g1(α)
9. Скачать презентацию

Слайд 2

Неформальное и формальное определение МТ. Конфигурации.
УУ
Конечное множество состояний УУ: Q={q1,…, qn}.

Алфавит: Σ= {a1,…,am}.
Формальное определение: МТ=(Q,Σ,δ,q0,qz,a0,ar)
Команда МТ: qi aj →q’i a’j S (S – направление сдвига :L – влево ,R - вправо, E-на месте)
Конфигурации: произвольная - α1 qi α2 , стандартная начальная q0α, стандартная заключительная qzα
Переходы: непосредственный K→K’.
Если для K1 и Kn существует последовательность конфигураций K1, K2, …, Kn, такая, что K1 → K2 → …→ Kn,
то обозначим переход K1 =>Kn.

Слайд 3

Примеры простейших машин Тьюринга
Дана цепочка из символов 0 и 1. Все

нули заменить на 2.

0 ->2 R

1->1 R

2 ->2 L
1 ->1 L

ε ->ε L

ε ->ε R

1 -> 1R

ε -> ε R

Машина, работающая бесконечно на цепочке из 1:

Слайд 4

Переработка цепочек. Вычислимость по Тьюрингу.
Если α1 q0 α2 =>β1 qz β2,

то будем говорить, что машина Т перерабатывает слово α1 α2 в слово β1β2, и обозначать это T(α1α2) = β1β2.
Унарный код:
x единиц 1…1 = 1x , ε=0.
q0 1х1 * 1х2 * … * 1 хn⇒ qz 1y , когда f ( x 1 , … , xn ) = y, и работает бесконечно, начиная со стандартной начальной конфигурации, если f(x1,…,x n ) не определена.
Примеры:функций, вычислимых по Тьюрингу: сложение чисел , копирование.

Слайд 5

Вычислимость композиции
Композиция g (x) = f2 (f1(x))
T1 и T2 - машины,

вычисляющие f1 и f2 :
Q1 = {q10,…,q1n } и Q2 = {q20,…,q2n }
Граф машины Т: q20 = q1z . Начальное состояние Т - q10, заключительное – q2z.
Пусть f2(f1(x)) определена. Тогда Т1(1x) = 1f1(x) и
q101x => q1z1f1 (x).
Машина Т:
вместо q1z1f 1(x) она перейдет в q201f 1(x).
Машина Т2: q201f1 (x) => q2z1f2 (f1(x)).
Машина Т: q101x => q201f1 (x) => q2z1f 2(f 1(x)) и, следовательно, Т(1x) = 1f2 (f1 (x)).

Слайд 6

Вычислимость на полуленте и с восстановлением
df Говорят, что Т вычисляет предикат

P(α), если T(α) = ω, где ω = Т, когда Р(α) истинно, и ω = F, когда P(α) ложно.
df Говорят, что машина Т вычисляет Р(α) с восстановлением, если Т(α) = ωα.
Доказательство теоремы о вычислимости с восстановлением:
q0α => qn1 α* α => α *qn2 α => α * qn3 ω => qn4 ωα.

Слайд 7

Вычислимость разветвления
Теорема. Если функции g1(α), g2(α) и предикат Р(α) вычислимы по

Тьюрингу, то разветвление g1(α) и g2(α) по Р(α) также вычислимо.
Доказательство. Пусть Т1 – машина с состояниями q10,q11,…,q1n и системой команд , вычисляющая g1, Т2 – машина с состояниями q20,q21,…, q2n и системой команд , вычисляющая g2; Тp вычисляет с восстановлением Р(α). Тогда машина Т, вычисляющая разветвление g1 и g2 по Р, - это композиция Тр и машины Т3, система команд которой имеет следующий вид: