09.08 Формальное определение алгоритма: машина Тьюринга

Алгоритм

полнота, выполнимость, однозначность, конечность.

Программа

формальная конечная запись алгоритма для формализованного исполнителя

Требует также формализации данных (⇒ моделирования aka «договоримся, что числа вот в этих ячейках памяти — это количество ящиков).

Чем отличается программа от промпта?

Алгоритмически полный формализм:: дисциплина записи любых программ, включает в себя:

• Синтаксис (правила записи)
• Семантику (правила интерпретации формальным исполнителем)

ИРЛ начинается самое интересное — прагматика (когда исполнять надо на конкретной ЭВМ). В Си мы довольно часто будем встречаться именно с прагматикой.

Вот здесь побольше про синтаксис, семантику и прагматику.

Ниоткуда взявшиеся, но пока что никем не опровергнутые свойства алгоритмической полноты:

• Соответствие операциональному определению

• Дисциплина аллегирования _/\_/\_ данных (как полагается на них ссылаться). Например, в функциональном программировании нет метафоры «переменная как контейнер, куда кто угодно может положить данные», а есть «переменная — это имя», как в математике.

• Действия, обусловленные свойствами данных. Например, условные операторы.

Может ли кто привести пример ЯП, в котором нет операторов цикла? А что там вместо них? ассемблер с переходами назад и лисп с рекурсией

Машина Тьюринга

Повторение: как устроен исполнитель МТ

• лента с ячейками
• считывающе-записывающее устройство («головка»)
• переход по ленте

Повторение: как устроена программа для МТ

• Понятие «состояния» q

• «Конфигурация» ::= Обозреваемый символ S + состояние q

• «Такт» ::= Запись символа S₁, перемещение по ленте L, N, R, переход в новое состояние q₁

  • символ и состояние могут совпадать с текущей конфигурацией

Представление данных: понятия «символ», «алфавит» и «слово»; пустой символ

• Договорённость о словах на ленте — нет дыр, положение головки

Программа

• как отображение {Sᵢ, qₘ} → {Sₖ, R|N|L, qₙ}

• как таблица

Практикум

Эмулятор TODO: втянуть на uneex

• См. текст по ссылке

Особенности эмулятора:

• Состояния нумеруются с 0

• Вместо понятия «такт останова» (в лекциях: такт [S, N, q] для конфигурации [S, q]) вводится понятие «конечное состояние» (№ «!»)

• Умолчания для полей такта
• Значащие пробелы и пустые строки

• в том числе отсутствие перевода строки в конце последней строки! (не является ошибкой, хотя ругается)

Сюда кидать решения

• Разбор и проход вручную примеров 1, 2 по ссылке (нажать (загрузить в эмулятор), пройти пошагово)

  • Принципы работы в эмуляторе — редактирование, копипаста, пошаговое/полное выполнение, сброс

• Модификация задачи 2 — вычитание 1 вместо умножения

• Это не алгоритм, если допустимо слово «0»

• Разбор и проход вручную примера 3 по ссылке

  • Примитив «добежать до символа» (q₀ — до "∧")

  • Примитив «маркер» (дополнительный символ в алфавите, "#")

• №3: Дан алфавит A = {*, a, b, c}, P = *Q , где *∉Q. Получить Q*.

  • TODO: переделать формулировку под произвольное количество звёздочек слева: P = ***...***Q -> Q***...***

• №7: В алфавите {1, 2} оставить на ленте 2, если непустое слово чётной длины, иначе — 1

TODO Задача посложнее на конец семинара в режиме «кто успеет» из https://cmcmsu.info/1course/mt.markov.tasks.htm (а надо ли?)

Д/З

1. A = {a, b, c}. Удвоить каждую букву P.
2. A = {a, b, c}. Заменить последнее вхождение буквы a в P на bb. Если a∉P, то оставить P без изменений.

3. A = {a, b, c, |}. Приписать к концу P столько палочек, сколько раз буква b входит в P. Пример: abcbb → abcbb|||.