Аппаратные и программные

3.2.4 Полнота по Тьюрингу 
В теории вычислимости
2
исполнитель (множество вычисляющих 
элементов) называется тьюринг-полным, если на нём можно реализовать 
любую вычислимую функцию. Другими словами, для каждой вычислимой 
функции существует вычисляющий её элемент (например, машина Тьюринга) 
или программа для исполнителя, а все функции, вычисляемые множеством 
вычислителей, являются вычислимыми функциями (возможно, при некотором 
кодировании входных и выходных данных). Название пошло от Алана 
Тьюринга, который придумал абстрактный вычислитель - машину Тьюринга и 
дал определение множества функций, вычислимых посредством машин 
Тьюринга. Большинство широко используемых языков программирования - 
тьюринг-полные. Это касается как императивных языков, таких как Паскаль, 
так и функциональных (Haskell) и языков логического программирования 
(Prolog). Полными по Тьюрингу являются также грамматики общего вида. 
Примерами неполных по Тьюрингу формализмов являются конечные автоматы, 
примитивно рекурсивные функции, контекстно-свободные и регулярные 
грамматики. 
3.2.5 Модель вычислений
Модель вычислений, вычислительная модель (model of computation, MOC) 
– набор законов взаимодействия элементов вычислительной системы.
Модель вычислений – набор правил организации вычислительного 
процесса, в рамках которых возможен его формальный анализ.
Модель вычислений – набор формальных правил, в рамках которых 
организована взаимосвязь и поведение множества составляющих атомарных 
частей модели некоторой вычислительной системы.
2
Теория вычислимости – это раздел современной математики и теории вычислений, возникший в 
результате изучения понятий вычислимости и невычислимости. Изначально теория была посвящена 
вычислимым и невычислимым функциям и сравнению различных моделей вычислений. Сейчас поле 
исследования теории вычислимости расширилось - появляются новые определения понятия вычислимости и 
идёт слияние с математической логикой, где вместо вычислимости и невычислимости идёт речь о доказуемости 
и недоказуемости (выводимости и невыводимости) утверждений в рамках каких-либо теорий. 

---

138 
Модель вычислений – строго определенная парадигма (набор правил), 
описывающая протекание вычислительного процесса, способы обмена 
данными, взаимодействия между отдельными функциональными элементами.
Модель вычислений – недвусмысленный формализм для представления 
спецификаций проекта и проектных решений.
Модель вычислений – математическая модель, демонстрирующая 
пользователю вычислительные возможности вычислителя и правила их 
использования. 
Теория вычислимости и теория сложности вычислений трактует модель 
вычисления не только как определение множества допустимых операций, 
использованных для вычисления, но также и относительных издержек их 
применения. Охарактеризовать необходимые вычислительные ресурсы время 
выполнения, объём памяти, а также ограничения алгоритмов или компьютера 
можно только в том случае, если выбрана определённая модель вычислений. В 
модельно-ориентированной инженерии модель вычислений и её выбор дают 
ответ на вопрос, как ведёт себя система в целом, если известно поведение её 
отдельных частей. При асимптотической оценке сложности вычислений модель 
вычислений определяется через допустимые примитивные операции, для 
каждой из которых известна её цена. 
Известен целый ряд моделей вычислений, зависящих от набора 
применяемых операций и их вычислительной сложности. Они распадаются на 
следующие большие категории: абстрактные машины (абстрактные 
вычислители), используемые для доказательства вычислимости и получения 
верхней границы вычислительной сложности алгоритма и модели принятия 
решений, используемые для получения нижней границы сложности 
вычислений для алгоритмических задач. 
Примеры языков принадлежащих различным моделям вычислений: 
• Си, Pascal, Ada – императивная модель или модель Фон-Неймана; 
• VHDL, Verilog – модель дискретных событий; 
• Prolog, Рефал – сентенциональная модель; 
• XML – иерархическая модель данных; 
• SQL – реляционная модель; 
• Lisp – функциональная модель [40].