Презентация_Машины_Поста_и_Тьюринга

1.

Машины Поста и Тьюринга

2.

Что такое вычислительные
модели
• Понятие абстрактной вычислительной
машины
• Зачем нужны формальные модели
алгоритмов
• Машины Поста и Тьюринга — классика
вычислимости

3.

Почему важно изучать
• Связь с алгоритмами
• Основа теории вычислимости
• Фундамент для языка программирования

4.

История Машины Поста
• Автор: Эмиль Пост
• 1920–1940 годы
• Цель — формализация вычислений

5.

Устройство Машины Поста
• Лента — цепочка символов
• Алфавит: 0, 1 или пусто
• Команды: вставка, удаление, переход

6.

Принцип работы
• Чтение символа
• Выполнение команды
• Дискретное пошаговое выполнение

7.

Значение Машины Поста
• Формализация вычислимости
• Эквивалентность Тьюрингу
• Простота структуры

8.

Задача 1: Удвоение строки
• Исходная: 111 → 111111
• Поиск конца строки
• Добавление символов

9.

Задача 2: Удаление каждого
второго символа
• Исходная: 101010 → 111
• Пометка позиций
• Удаление через один

10.

Задача 3: Проверка на единицы
• Исходная: 111101
• Поиск нуля
• Вывод истины/лжи

11.

История Машины Тьюринга
• Автор: Алан Тьюринг
• 1936 год
• Исследование алгоритмичности

12.

Устройство Машины Тьюринга
• Бесконечная лента
• Головка: чтение, запись, движение
• Таблица переходов

13.

Принцип работы
• Чтение символа
• Запись символа
• Движение головки
• Переход между состояниями

14.

Значение Машины Тьюринга
• Универсальность
• Эквивалентность современным
компьютерам
• Идея универсальной машины

15.

Задача 1: Инкремент
• 111 → 1111
• Переход вправо
• Запись нового символа

16.

Задача 2: Проверка палиндрома
• 10101
• Сравнение левого и правого символов
• Использование маркеров

17.

Задача 3: Сложение в унарном
коде
• 1110111 → 111111
• Удаление разделителя
• Объединение строк

18.

Сравнение моделей
• Обе эквивалентны по мощности
• Разные представления программы
• Машина Тьюринга — более привычная
модель

19.

Современное значение
• Основа теории алгоритмов
• Пределы вычислимости
• Применение в анализе сложности

20.

Заключение
• Машины Поста и Тьюринга — фундамент
информатики
• Служат моделью любого вычисления
• Ключ к пониманию алгоритмов

21.

Вопросы