При использовании данной презентации при объяснении новой темы появляется возможность применять методы личностно-ориентированного обучения: проблемный метод, метод эвристической беседы и элементы исследования. Постановка проблемы ставит учащихся в условия, которые побуждают его решать учебную проблему, проводить анализ материала и оперировать им. Такая деятельность позволяет учащимся получить новую информацию, освоит новые способы применения знаний
Для формального определения
алгоритма математиками
Тьюрингом (1936 г.) и независимо
от него Постом (1937 г.) были
предложены абстрактные
вычислительные
конструкции, которые позже
были названы «машинами».
Машина Тьюринга (МТ)
– абстрактная
бесконечная лента,
разделенная на ячейки,
содержащие символы
заданного алфавита, и
чтения/записи символов,
управляемая программой.
головка для
А={ао,а1,…аm} – алфавит
входных символов, где
ао пустая ячейка;
Q= {qо,q1,…qn} – алфавит
состояний, где
qо конечное состояние,
q1 начальное состояние.
Система команд МТ
Читать содержимое ячейки
Стирать и записывать
символы в ячейку
Перемещаться вправо(П),
влево(Л), стоять
неподвижно(Н)
Перейти в новое состояние
Программа МТ
– таблица, в которой в
каждой клетке записана
команда, указывающая
какой символ записать в
текущую ячейку, куда
передвинуть головку и в
какое состояние
перейдет машина.
а0
а1 … аi … аm
Если в текущей ячейке – аi, то
записать в неё аk,
переместиться (Л, П или Н),
затем перейти в новое
состояние qp
Л
аk П qp
Н
q0
q1
…
qj
…
qn
Пример
Построить МТ, которая прибавляет 1
к натуральному десятичному числу
на ленте. В начальный момент –
головка напротив младшего разряда
справа.
q1 – состояние изменения цифры
а0
1Нq0
q1
1
0
1Нq0 2Нq0 3Нq0
2 … 8
9
9Нq0 0Лq1
Тезис Тьюринга
– всякий алгоритм
может быть
реализован
соответствующей
машиной Тьюринга.
Алгоритм (по Тьюрингу)
– программа для машины
Тьюринга, приводящая к
решению поставленной
задачи.
Если для решения задачи можно
построить машину Тьюринга, то
она алгоритмически разрешима.
mashina_tjuringa.ppt
