Что такое алгоритм, исполнитель и вычислительная модель?

Алгоритм задаёт конечное и однозначное управление исполнителем для целого класса входных данных. Исполнитель определяется набором команд, состоянием и правилами выполнения. Поэтому одна и та же инструкция может быть алгоритмом для машины с нужными операциями и бессмысленным текстом для исполнителя, который их не понимает.

Свойства описания

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

Абстрактная машина

Машина Тьюринга отделяет принцип вычисления от конкретного процессора: бесконечная лента хранит символы, головка читает и меняет ячейку, таблица переходов задаёт действие по состоянию. Модель крайне проста, но способна выражать любой обычный алгоритм при достаточных ресурсах.

Граница вычислимости

Тезис Чёрча — Тьюринга связывает интуитивно вычислимые процедуры с формальными универсальными моделями. При этом существуют задачи, для которых общий завершающийся алгоритм невозможен. Классический пример — проблема остановки: нельзя создать один анализатор, безошибочно решающий для любой программы и любого входа, завершится ли выполнение.

Сложность не равна вычислимости

Алгоритм может существовать, но требовать непрактичного числа операций или памяти. Сложность описывает рост ресурсов вместе с размером входа, а вычислимость отвечает на более фундаментальный вопрос существования процедуры. Быстрый частный эвристический метод также не доказывает решение общего случая.

Устное объяснение

Выберите бытовой процесс и формализуйте исполнителя, команды, вход и условие остановки. Затем назовите ситуацию, которую первоначальная инструкция не покрывает. Это упражнение показывает, что точность алгоритма рождается из модели допустимых состояний, а не из подробности естественного языка самой по себе.

Исполнитель задаёт смысл каждой команды

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

def run_counter(program: list[str], start: int, limit: int = 100) -> int:
    value = start
    for step, command in enumerate(program):
        if step >= limit:
            raise RuntimeError("step limit exceeded")
        if command == "inc":
            value += 1
        elif command == "double":
            value *= 2
        else:
            raise ValueError(f"unknown command: {command}")
    return value

print(run_counter(["inc", "double", "inc"], 3))  # 9

Свойства алгоритма разделяются. Конечность говорит о завершении на допустимом входе, определённость — об однозначности шага, результативность — о получении требуемого выхода. Оценка O(n) имеет смысл только после определения n и выбранной элементарной операции.

Практика: спецификация маленькой машины

Добавьте команды dec и jump-if-zero к исполнителю, задав счётчик команд и допустимые адреса. До написания кода опишите конфигурацию одним кортежем и переход для каждой команды. Создайте программу, которая уменьшает положительное число до нуля, и сформулируйте вариант цикла, доказывающий завершение. Затем намеренно соберите бесконечный переход и покажите, что лимит обнаруживает эксперимент, но не доказывает неостановимость произвольной программы.