Теория алгоритмов Машина Тьюринга

Август 21, 2022

Главная
Математика
Теория алгоритмов Машина Тьюринга

Содержание

2. ПРИМЕР (КОПИРОВАНИЕ, ТКОП) Можно осуществить как переработку слова α в слово α * α; где α
3. ДИАГРАММА ПЕРЕХОДОВ
4. НЕКОТОРЫЕ ОПЕРАЦИИ НАД МАШИНАМИ ТЬЮРИНГА Теорема Если f1(x) и f2(x) вычислимы по Тьюрингу, то f2(f1(x)) также
5. ПРИМЕР (УМНОЖЕНИЕ): Рассмотрим машину, вычисляющую f(x) = 2x(x≠0). Ее можно представить как композицию Т+ (Ткоп). Ткоп
6. ДИАГРАММА ПЕРЕХОДОВ
7. ПРИМЕР (ПРЕДИКАТ) Записать на ленте И, если а – четное, иначе Л. P(a): a – четное
8. ПРИМЕР (ПРЕДИКАТ)
9. ПРИМЕР (РАЗВЕТВЛЕНИЕ) Т++ - для сложения n чисел ( n=1,2,…) Цикл из состояний q1, q2 ,
10. ЗАКЛЮЧЕНИЕ 1. Для вычислений на машине Тьюринга достаточно, чтобы лента была бесконечна в одну сторону, например,
12. Скачать презентацию

Слайд 2

ПРИМЕР (КОПИРОВАНИЕ, ТКОП)
Можно осуществить как переработку слова α в слово

α * α; где α = 1α
Ткоп при каждом проходе исходного числа 1α заменяет левую единицу 0 и пишет единицу справа от 1α в ближайшую пустую клетку.
Копирование проходит за α проходов,
до тех пор, пока когда при очередном проходе обнаруживается на ленте не 1, а *.
Тогда идем влево, заменяя по дороге все 0 на 1.

Слайд 3

ДИАГРАММА ПЕРЕХОДОВ

Слайд 4

НЕКОТОРЫЕ ОПЕРАЦИИ НАД МАШИНАМИ ТЬЮРИНГА
Теорема
Если f1(x) и f2(x) вычислимы по Тьюрингу,

то f2(f1(x)) также вычислима по Тьюрингу.

Слайд 5

ПРИМЕР (УМНОЖЕНИЕ):
Рассмотрим машину, вычисляющую f(x) = 2x(x≠0). Ее можно представить как

композицию Т+ (Ткоп).
Ткоп строит двухкомпонентный вектор, Т+ складывает компоненты этого вектора

Слайд 6

ДИАГРАММА ПЕРЕХОДОВ

Слайд 7

ПРИМЕР (ПРЕДИКАТ)
Записать на ленте И, если а – четное, иначе Л.
P(a):

a – четное число
ИДЕЯ:
Идем по числу вправо,
если число единиц четно, заканчиваем в состоянии q2,
если число единиц нечетно - в состоянии q3.
После чего идем влево, заменяя 1 пустыми символами и печатаем И или Л.

Слайд 8

ПРИМЕР (ПРЕДИКАТ)

Слайд 9

ПРИМЕР (РАЗВЕТВЛЕНИЕ)
Т++ - для сложения n чисел ( n=1,2,…)
Цикл из

состояний q1, q2 , q3 – «зацикленная» Т+
q4 – разветвление, в нем проверяется условие, есть ли 2-е слагаемое, если да (* присутствует), то переход к новому циклу, если нет (λ после единиц), то машина выходит из цикла

Слайд 10