Элементы теоретического программирования Машина Тьюринга – математическое понятие алгоритма

Сентябрь 1, 2022

Главная
Информатика
Элементы теоретического программирования Машина Тьюринга – математическое понятие алгоритма

Содержание

2. Машина Тьюринга – математическое понятие алгоритма Каждой паре вида (si, qi), где si∈А и qi∈Q\{q0}, соответствует
3. Машина Тьюринга – математическое понятие алгоритма Множество всех пар вида (si, qi), где si∈A и qi∈Q\{q0},
4. Машина Тьюринга – математическое понятие алгоритма Таким образом, программа машины Тьюринга представляет собой функцию с областью
5. Машина Тьюринга – математическое понятие алгоритма Машиной Тьюринга (МТ) называется система вида (A, s0, Q, q1,
6. Машина Тьюринга – математическое понятие алгоритма Машина Тьюринга перерабатывает слова в алфавите машины согласно программе этой
7. Машина Тьюринга – математическое понятие алгоритма Какую бы МТ, имеющую алфавит A={s0, s1, ..., sk}, состояния
8. Машина Тьюринга – математическое понятие алгоритма Другими словами, с математической точки зрения МТ — это алгоритм
9. Машина Тьюринга – математическое понятие алгоритма Массовость алгоритма. Множество исходных данных для алгоритма — множество всевозможных
10. Машина Тьюринга – математическое понятие алгоритма Результативность алгоритма. Алгоритм по любому исходному данному позволяет в конечное
11. Машина Тьюринга – математическое понятие алгоритма Конструктивность объектов. Исходные объекты, промежуточные и окончательные результаты для МТ
12. Машина Тьюринга – математическое понятие алгоритма Детерминированность (определенность) алгоритма. Программа τ составлена таким образом, что ее
13. Машина Тьюринга – математическое понятие алгоритма Детерминированность (определенность) алгоритма. Свойство детерминированности означает также, что применение программы
14. Машина Тьюринга – математическое понятие алгоритма Конечность предписания, задающего алгоритм. Программа τ представляет собой конечное предписание,
15. Машина Тьюринга – математическое понятие алгоритма Нельзя ли задавать посредством МТ и другие известные нам алгоритмы,
16. Машина Тьюринга – математическое понятие алгоритма Тезис Тьюринга: Всякий алгоритм может быть задан посредством МТ
17. Машина Тьюринга – математическое понятие алгоритма В тезисе Тьюринга речь идет, с одной стороны, о понятии
18. Классы задач не имеющих разрешающего алгоритма Существует ли алгоритм, позволяющий по произвольному уравнению с целыми коэффициентами
19. Классы задач не имеющих разрешающего алгоритма Существует ли алгоритм, позволяющий по любому ассоциативному исчислению выяснить, разрешима
20. Машина Тьюринга ~ Нормальный алгоритм Маркова Класс алгоритмов в форме машин Тьюринга и класс нормальных алгоритмов
21. Машина Тьюринга ~ Нормальный алгоритм Маркова Иными словами, для каждого алгоритма из класса машин Тьюринга существует
23. Скачать презентацию

Слайд 2

Машина Тьюринга – математическое понятие алгоритма
Каждой паре вида (si, qi), где

si∈А и qi∈Q\{q0}, соответствует тройка (sj, t, qj), где sj∈A, t∈T и qj∈Q (q0 не участвует в парах (si, qi), так как паре (si, q0) уже ничего не соответствует, машина останавливается в заключительном состоянии q0).

Слайд 3

Машина Тьюринга – математическое понятие алгоритма
Множество всех пар вида (si, qi),

где si∈A и qi∈Q\{q0}, называется произведением множеств А и Q\{q0) и обозначается А×Q\{q0). Аналогично, множество всех троек вида (sj, t, qj), где sj∈A, t∈T и qj∈Q, называется произведением множеств А, Т и Q и обозначается А×Т×Q

Слайд 4

Машина Тьюринга – математическое понятие алгоритма
Таким образом, программа машины Тьюринга представляет

собой функцию с областью определения А×Q\{q0}, принимающую значения из множества А×Т×Q, или отображение первого множества во второе: А×Q\{q0}→A×T×Q

Слайд 5

Машина Тьюринга – математическое понятие алгоритма
Машиной Тьюринга (МТ) называется система вида

(A, s0, Q, q1, q0, T, τ), где А − конечное множество − алфавит МТ, s0∈A и называется пустой буквой алфавита, Q − конечное множество, элементы которого называются состояниями МТ (Q − множество состояний МТ), q1∈Q, q1 − начальное состояние МТ, q0∈Q, q0 − пассивное или заключительное состояние МТ, Т={Л, Н, П} − множество сдвигов МТ, τ :А×Q\{q0}→A×T×Q, τ − программа МТ.

Слайд 6

Машина Тьюринга – математическое понятие алгоритма
Машина Тьюринга перерабатывает слова в алфавите

машины согласно программе этой машины.

Слайд 7

Машина Тьюринга – математическое понятие алгоритма
Какую бы МТ, имеющую алфавит A={s0, s1,

..., sk}, состояния q0, q1, ..., qp и программу τ, мы ни взяли, можем считать, что имеется алгоритм, исходными объектами, промежуточными и окончательными результатами которого являются слова в алфавите А. Предписанием, задающим этот алгоритм, является программа τ.

Слайд 8

Машина Тьюринга – математическое понятие алгоритма
Другими словами, с математической точки зрения

МТ — это алгоритм для переработки слов в алфавите этой машины (ради удобства отождествляем МТ с ее программой).

Слайд 9

Машина Тьюринга – математическое понятие алгоритма
Массовость алгоритма. Множество исходных данных для алгоритма

— множество всевозможных слов в алфавите А машины. Это множество бесконечно, его элементы записываются на ленте машины.

Слайд 10

Машина Тьюринга – математическое понятие алгоритма
Результативность алгоритма. Алгоритм по любому исходному

данному позволяет в конечное число шагов получить результат. Программа МТ применяется единообразно ко всевозможным исходным данным и не меняется в процессе работы машины над исходным словом. Программа описывает переход от одного состояния к другому. Некоторое состояние опознается как заключительное. Появившееся при этом на ленте слово в алфавите А является результатом переработки слова, записанного на ленте в начальном состоянии машины.

Слайд 11

Машина Тьюринга – математическое понятие алгоритма
Конструктивность объектов. Исходные объекты, промежуточные и

окончательные результаты для МТ — слова в алфавите А машины. Такие объекты являются конструктивными.

Слайд 12

Машина Тьюринга – математическое понятие алгоритма
Детерминированность (определенность) алгоритма. Программа τ составлена

таким образом, что ее исполнение однозначно осуществимо. Действительно, программа τ — это совокупность команд вида siqj→smTqp, причем любые две различные команды не содержат одинаковых левых частей. При этом условии система команд не может требовать двух или более различных действий в одно и то же время.

Слайд 13

Машина Тьюринга – математическое понятие алгоритма
Детерминированность (определенность) алгоритма. Свойство детерминированности означает

также, что применение программы τ к одному и тому же слову в алфавите А приводит к одному и тому же результату с одной и той же последовательностью состояний ленты.

Слайд 14

Машина Тьюринга – математическое понятие алгоритма
Конечность предписания, задающего алгоритм. Программа τ

представляет собой конечное предписание, причем процесс вычислений протекает только согласно программе и исходным данным, ничего более не используется.

Слайд 15

Машина Тьюринга – математическое понятие алгоритма
Нельзя ли задавать посредством МТ и

другие известные нам алгоритмы, задаваемые обычно с помощью предписаний. Другими словами, насколько «богат» класс МТ? Быть может он включает все алгоритмы?

Слайд 16

Машина Тьюринга – математическое понятие алгоритма
Тезис Тьюринга: Всякий алгоритм может быть задан

посредством МТ

Слайд 17

Машина Тьюринга – математическое понятие алгоритма
В тезисе Тьюринга речь идет, с

одной стороны, о понятии алгоритма, которое не является точным математическим понятием; с другой стороны, о точном математическом понятии — МТ. Значение этого тезиса и заключается в том, что он уточняет понятие алгоритма через математическое понятие — машину Тьюринга

Слайд 18

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

уравнению с целыми коэффициентами выяснить, имеет оно целочисленное решение или нет?

Слайд 19

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

ассоциативному исчислению выяснить, разрешима в нем проблема эквивалентности слов или нет?

Слайд 20

Машина Тьюринга ~ Нормальный алгоритм Маркова
Класс алгоритмов в форме машин Тьюринга

и класс нормальных алгоритмов совпадают, эти алгоритмы равносильны.

Слайд 21

Машина Тьюринга ~ Нормальный алгоритм Маркова
Иными словами, для каждого алгоритма из

класса машин Тьюринга существует равносильный ему алгоритм в классе нормальных алгоритмов, и наоборот.

Элементы теоретического программирования Машина Тьюринга – математическое понятие алгоритма

Содержание

Машина Тьюринга – математическое понятие алгоритмаКаждой паре вида (si, qi), где

Машина Тьюринга – математическое понятие алгоритмаМножество всех пар вида (si, qi),

Машина Тьюринга – математическое понятие алгоритмаТаким образом, программа машины Тьюринга представляет

Машина Тьюринга – математическое понятие алгоритмаМашиной Тьюринга (МТ) называется система вида

Машина Тьюринга – математическое понятие алгоритмаМашина Тьюринга перерабатывает слова в алфавите

Машина Тьюринга – математическое понятие алгоритмаКакую бы МТ, имеющую алфавит A={s0, s1,

Машина Тьюринга – математическое понятие алгоритмаДругими словами, с математической точки зрения

Машина Тьюринга – математическое понятие алгоритмаМассовость алгоритма. Множество исходных данных для алгоритма

Машина Тьюринга – математическое понятие алгоритмаРезультативность алгоритма. Алгоритм по любому исходному

Машина Тьюринга – математическое понятие алгоритмаКонструктивность объектов. Исходные объекты, промежуточные и

Машина Тьюринга – математическое понятие алгоритмаДетерминированность (определенность) алгоритма. Программа τ составлена

Машина Тьюринга – математическое понятие алгоритмаДетерминированность (определенность) алгоритма. Свойство детерминированности означает

Машина Тьюринга – математическое понятие алгоритмаКонечность предписания, задающего алгоритм. Программа τ

Машина Тьюринга – математическое понятие алгоритмаНельзя ли задавать посредством МТ и

Машина Тьюринга – математическое понятие алгоритмаТезис Тьюринга: Всякий алгоритм может быть задан

Машина Тьюринга – математическое понятие алгоритмаВ тезисе Тьюринга речь идет, с

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

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

Машина Тьюринга ~ Нормальный алгоритм МарковаКласс алгоритмов в форме машин Тьюринга

Машина Тьюринга ~ Нормальный алгоритм МарковаИными словами, для каждого алгоритма из

Похожие презентации