Презентация на тему Элементы теоретического программирования

(si, qi), где si∈А и qi∈Q\{q0}, соответствует тройка (sj,

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

вида (si, qi), где si∈A и qi∈Q\{q0}, называется произведением

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

машины Тьюринга представляет собой функцию с областью определения А×Q\{q0},

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

называется система вида (A, s0, Q, q1, q0, T,

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

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

имеющую алфавит A={s0, s1, ..., sk}, состояния q0, q1, ...,

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

математической точки зрения МТ — это алгоритм для переработки

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

данных для алгоритма — множество всевозможных слов в алфавите

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

по любому исходному данному позволяет в конечное число шагов

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

объекты, промежуточные и окончательные результаты для МТ — слова

в алфавите А машины. Такие объекты являются конструктивными.

алгоритма. Программа τ составлена таким образом, что ее исполнение

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

алгоритма. Свойство детерминированности означает также, что применение программы τ

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

алгоритм. Программа τ представляет собой конечное предписание, причем процесс

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

посредством МТ и другие известные нам алгоритмы, задаваемые обычно

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

может быть задан посредством МТ

речь идет, с одной стороны, о понятии алгоритма, которое

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

позволяющий по произвольному уравнению с целыми коэффициентами выяснить, имеет

оно целочисленное решение или нет?

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

проблема эквивалентности слов или нет?

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

алгоритмы равносильны.

каждого алгоритма из класса машин Тьюринга существует равносильный ему

алгоритм в классе нормальных алгоритмов, и наоборот.