Проект Машина Поста преза

1.

Групповой проект на тему
Машина Поста
«Умственный компьютер», который выполняет команды по строгим правилам. Несмотря на свою
простоту, она может решать любые задачи, которые решают современные компьютеры, если только для
них существует алгоритм
• Демьяненко Данил
• Строев Павел
• Герасименко Игорь
Энгельке Сергей
Пахомова Олеся
Николаюк Никита

2.

Эмиль Пост (1897–1954)
Математик и логик
Исследование
Родился в Польше, работал в
Вычислимые функции и логика
США
вычислений
Влияние
Основа для языков программирования и процессоров

3.

Три компонента машины
Лента
Бесконечная, разделённая на ячейки с метками (1) или пусто (0)
Считывающая головка
Указатель, движется влево или вправо на одну клетку
Программа
Список команд, выполняемых по очереди

4.

Шесть основных команд
1
2
3
4
5
6
Поставить метку (1)
Записать единицу в пустую ячейку
Стереть метку (0)
Если в ячейке есть единица, стереть её
Сместиться вправо (→)
Перейти на соседнюю ячейку справа
Сместиться влево (←)
Перейти на соседнюю ячейку слева
Проверить состояние ячейки
Если в текущей ячейке есть метка, перейти к одной команде; если нет — к другой.
Остановиться
Завершить выполнение программы.

5.

Пример 1
Задача: Увеличить число на 1 (111 → 1111)
1
2
3
Найти конец
Добавить метку
Результат
Двигаться вправо до пустой ячейки
Поставить единицу в пустую ячейку
Число увеличено на 1

6.

Пример 2
Задача: Сложить 3 + 2 (1110 + 11 → 11111)
1
2
3
4
Найти разделитель
Переместить метки
Удалить разделитель
Получить сумму
Результат: 11111 (5)
Пустую ячейку между
Стирать справа, добавлять
Стереть пустую ячейку
числами
слева
между группами

7.

Значение для информатики
Теория алгоритмов
Доказала, что любая вычислимая
задача — это простой алгоритм
Архитектура
компьютеров
Основа для создания первых
вычислительных машин
Программирование
Принцип «если-то-иначе» и языки программирования

8.

Машина Поста
сегодня
Образование
Применение
Обучение информатике
Демонстрация сложности
Логика и алгоритмы
Разложение на простые шаги
Основы программирования
Понимание вычислений

9.

От простых шагов к
сложным вычислениям
Машина Поста— это один из первых шагов человечества к
созданию компьютеров.
Эмиль Пост показал, что вычисления — это не
обязательно сложные формулы и машины, а просто
последовательность элементарных действий, выполняемых
по правилам