Модель вычисления

Эта статья в значительной степени или полностью основана на одном источнике . Соответствующее обсуждение можно найти на странице обсуждения . Пожалуйста, помогите улучшить эту статью, добавив ссылки на дополнительные источники . Найти источники:  «Модель вычисления» – новости  · газеты  · книги  · ученый  · JSTOR ( февраль 2021 г. )

В информатике , а точнее в теории вычислимости и теории сложности вычислений , модель вычислений — это модель, описывающая, как вычисляется выход математической функции при заданном входе. Модель описывает, как организованы единицы вычислений, памяти и коммуникации. ^[1] Вычислительную сложность алгоритма можно измерить при заданной модели вычислений. Использование модели позволяет изучать производительность алгоритмов независимо от вариаций, характерных для конкретных реализаций и конкретной технологии.

Модели вычислений можно разделить на три категории: последовательные модели, функциональные модели и параллельные модели.

Последовательные модели включают в себя:

• Конечные автоматы
• Постмашины ( Постмашины Тьюринга и теговые машины ).
• Автоматы Pushdown
• Регистрировать машины
  • Машины с произвольным доступом
• Машины Тьюринга
• Модель дерева решений

Функциональные модели включают в себя:

• Системы переписывания абстрактных текстов
• Комбинаторная логика
• Общие рекурсивные функции
• Лямбда-исчисление

К параллельным моделям относятся:

• Модель актера
• Клеточный автомат
• Сети взаимодействия
• Сети процессов Кана
• Логические вентили и цифровые схемы
• Сети Петри
• Процесс исчисления
• Синхронный поток данных

Некоторые из этих моделей имеют как детерминированные , так и недетерминированные варианты. Недетерминированные модели соответствуют пределам определенных последовательностей конечных компьютеров, но не соответствуют ни одному подмножеству конечных компьютеров; ^{[ необходима цитата ]} они используются при изучении вычислительной сложности алгоритмов.

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

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

• Стековая машина (машина с 0 операндами)
• Накопительная машина (машина с одним операндом)
• Регистровая машина (машина операндов 2,3,...)
• Машина с произвольным доступом
• Абстрактная машина
• Модель «клеточный зонд»
• Модель запроса Робертсона-Уэбба
• Иерархия Хомского
• полнота по Тьюрингу

• Фернандес, Марибель (2009). Модели вычислений: введение в теорию вычислимости . Темы бакалавриата по информатике. Springer. ISBN 978-1-84882-433-1.
• Savage, John E. (1998). Модели вычислений: исследование мощности вычислений . Addison-Wesley. ISBN 978-0201895391.