Машины Тьюринга. Алгоритмы и структуры данных

1.

Алгоритмы и структуры
данных
2022-2023 учебный год
Нестеров Роман Александрович, PhD & Бессмертный Александр Игоревич
Департамент программной инженерии

2.

План
1. Повторить построение конечного автомата для заданного
регулярного автомата.
2. Несколько слов о машине Тьюринга.
3. Какую задачу решает заданная машина Тьюринга?
4. Построение машины Тьюринга по описанию задачи/языка.
5. Пределы вычислимости/разрешимости.
6. Иерархия сложности алгоритмов по времени и по памяти.

3.

Регулярные выражения и
автоматы

4.

Упражнение
По заданному регулярному выражению построить конечный
автомат, распознающий этот регулярный язык в алфавите {a, b}.
•(a + ab)*

5.

О машине Тьюринга

6.

Автоматы и машины Тьюринга
• Конечные автоматы не имеют оперативной памяти для
промежуточного хранения
• Автоматы с магазинной памятью моделируют работу
вычислительных устройств со стековой памятью
• Машины Тьюринга (1936)
• Оперируют с неограниченной слева и справа лентой, с которой
можно писать и на которую можно записывать символы
• «Контролируется» конечным автоматов
• Моделируют работу любого компьютера – Тезис Черча-Тьюринга
• НЕ может решить все возможные вычислительные задачи

7.

Машина Тьюринга
• Входной алфавит Σ.
• Алфавит ленты Γ = Σ ∪