Формализация понятия алгоритма. Машина Тьюринга
Теория для подготовки к ЕГЭ по информатике. Раздел 3.1: Формализация алгоритмов и машина Тьюринга как универсальная модель вычислений.
Понятие алгоритма и его свойства
Алгоритм — это точная конечная система правил, определяющая последовательность действий над некоторыми объектами для решения задачи.
Основные свойства алгоритмов:
- Дискретность — алгоритм состоит из отдельных шагов
- Определённость — каждое действие точно определено
- Понятность — алгоритм состоит только из известных исполнителю команд
- Результативность — алгоритм должен приводить к результату за конечное число шагов
- Массовость — алгоритм применим к целому классу задач
Примеры алгоритмов:
- Рецепт приготовления блюда
- Инструкция по сборке мебели
- Математический алгоритм (например, алгоритм Евклида)
- Компьютерная программа
Формализация понятия алгоритма
В 1930-х годах математики начали формализацию понятия алгоритма, что привело к созданию нескольких эквивалентных моделей вычислений.
Основные формальные модели алгоритмов:
- Машина Тьюринга (Алан Тьюринг, 1936)
- Рекурсивные функции (Курт Гёдель, 1934)
- Лямбда-исчисление (Алонзо Чёрч, 1936)
- Нормальные алгоритмы Маркова (Андрей Марков, 1951)
Тезис Чёрча-Тьюринга:
Любая функция, которая может быть вычислена алгоритмически, может быть вычислена с помощью машины Тьюринга.
Это означает, что все формальные модели алгоритмов эквивалентны по своей вычислительной мощности.
Важно: Не существует алгоритмического процесса, который мог бы определить, остановится ли произвольная машина Тьюринга на произвольных входных данных (проблема остановки).
Машина Тьюринга: основные понятия
Машина Тьюринга — это абстрактная вычислительная машина, предложенная Аланом Тьюрингом в 1936 году.
Компоненты машины Тьюринга:
- Бесконечная лента, разделённая на ячейки
- Головка чтения/записи, которая может перемещаться вдоль ленты
- Управляющее устройство, которое находится в одном из состояний
- Таблица правил (программа), определяющая поведение машины
Принцип работы машины Тьюринга
На каждом шаге машина Тьюринга выполняет следующие действия:
- Считывает символ из текущей ячейки ленты
- В зависимости от текущего состояния и считанного символа:
- Записывает новый символ в текущую ячейку
- Перемещает головку влево или вправо
- Переходит в новое состояние
- Останавливается, если достигнуто конечное состояние
Формальное определение машины Тьюринга:
Машина Тьюринга — это семёрка (Q, Γ, Σ, δ, q₀, B, F), где:
- Q — конечное множество состояний
- Γ — конечный алфавит символов ленты
- Σ ⊆ Γ — входной алфавит
- δ: Q × Γ → Q × Γ × {L, R} — функция переходов
- q₀ ∈ Q — начальное состояние
- B ∈ Γ — пустой символ
- F ⊆ Q — множество конечных состояний
Пример машины Тьюринга
Рассмотрим простую машину Тьюринга, которая инвертирует биты (0 заменяет на 1, а 1 на 0).
Компоненты машины:
- Q = {q₀, q_f}
- Γ = {0, 1, B}
- Σ = {0, 1}
- q₀ — начальное состояние
- B — пустой символ
- F = {q_f} — конечное состояние
Таблица правил (функция переходов δ):
| Состояние | Символ | Новое состояние | Новый символ | Движение |
|---|---|---|---|---|
| q₀ | 0 | q₀ | 1 | R |
| q₀ | 1 | q₀ | 0 | R |
| q₀ | B | q_f | B | — |
Работа машины на входе «101»:
Шаг 1: Состояние q₀, читаем ‘1’ → пишем ‘0’, двигаемся вправо, остаемся в q₀
Шаг 2: Состояние q₀, читаем ‘0’ → пишем ‘1’, двигаемся вправо, остаемся в q₀
Шаг 3: Состояние q₀, читаем ‘1’ → пишем ‘0’, двигаемся вправо, остаемся в q₀
Шаг 4: Состояние q₀, читаем ‘B’ → переходим в состояние q_f, останавливаемся
Результат: «010» (инверсия исходной строки «101»)
Универсальная машина Тьюринга
Универсальная машина Тьюринга — это машина, которая может имитировать любую другую машину Тьюринга.
Принцип работы универсальной машины Тьюринга:
- На вход подаётся описание машины Тьюринга M и входные данные w
- Универсальная машина имитирует работу машины M на данных w
- Результат работы совпадает с результатом работы M(w)
Значение универсальной машины Тьюринга:
- Доказывает возможность создания программируемых вычислительных устройств
- Является теоретической основой для современных компьютеров
- Показывает, что одна машина может выполнять любые вычисления
- Предвосхитила концепцию хранимых программ в компьютерах
Важно: Универсальная машина Тьюринга демонстрирует, что все современные компьютеры являются реализацией этой абстрактной модели, способной выполнять любые алгоритмы.