09.08 Формальное определение алгоритма: машина Тьюринга
- Алгоритм
- полнота, выполнимость, однозначность, конечность.
- Программа
- формальная конечная запись алгоритма для формализованного исполнителя
Требует также формализации данных (⇒ моделирования aka «договоримся, что числа вот в этих ячейках памяти — это количество ящиков).
Чем отличается программа от промпта?
Алгоритмически полный формализм:: дисциплина записи любых программ, включает в себя:
- Синтаксис (правила записи)
- Семантику (правила интерпретации формальным исполнителем)
ИРЛ начинается самое иннереснное — прагматика (когда исполнять надо на конкретной ЭВМ). В Си мы довольно часто будем встречаться именно с прагматикой.
Вот здесь побольше про синтаксис, семантику и прагматику.
Ниоткуда взявшиеся, но пока что никем не опровергнутые свойства алгоритмической полноты:
- Соответствие операциональному определению
Дисциплина аллегирования данных (как полагается на них ссылаться). Например, в функциональном программировании нет метафоры «переменная как контейнер, куда кто угодно может положить данные», а есть «переменная — это имя», как в математике.
- Действия, обусловленные свойствами данных. Например, условные операторы.
Может ли кто привести пример ЯП, в котором нет операторов цикла? А что там вместо них?
Машина Тьюринга
Повторение: как устроен исполнитель МТ
- лента с ячейками
- считывающе-записывающее устройство («головка»)
- переход по ленте
Повторение: как устроена программа для МТ
Понятие «состояния» q
«Конфигурация» ::= Обозреваемый символ S + состояние q
«Такт» ::= Запись символа S₁, перемещение по ленте L, N, R, переход в новое состояние q₁
- символ и состояние могут совпадать с текущей конфигурацией
Представление данных: понятия «символ», «алфавит» и «слово»; пустой символ
- Договорённость о словах на ленте — нет дыр, положение головки
Программа
как отображение {Sᵢ, qₘ} → {Sₖ, R|N|L, qₙ}
- как таблица
- См. текст по ссылке
Особенности эмулятора:
- Состояния нумеруются с 0
Вместо понятия «такт останова» (в лекциях: такт [S, N, q] для конфигурации [S, q]) вводится понятие «конечное состояние» (№ «!»)
- Умолчания для полей такта
- Значащие пробелы и пустые строки
в том числе отсутствие перевода строки в конце последней строки! (не является ошибкой, хотя ругается)
Практиукм
TODO форма отчётности по работе в классе?
Разбор и проход вручную примеров 1, 2 по ссылке (нажать (загрузить в эмулятор), пройти пошагово) - Принципы работы в эмуляторе — редактирование, копипаста, пошаговое/полное выполнение, сброс
Модификация задачи 2 — вычитание 1 вместо умножения Это не алгоритм, если допустимо слово «0»
- Разбор и проход вручную примера 3 по ссылке
Примитив «добежать до символа» (q₀ — до "∧")
Примитив «маркер» (дополнительный символ в алфавите, "#")
- №3: Дан алфавит A = {*, a, b, c}, P = *Q , где *∉Q. Получить Q*.
TODO выбрать ещё простых задач из https://cmcmsu.info/1course/mt.markov.tasks.htm
Д/З
TODO !!!