Математическая логика и теория алгоритмов

происходит от имени узбекского математика Аль-Хорезми*, который в IX веке систематизировал правила арифметических операций. Рассмотрим правила сложения целых чисел в десятичной системе счисления. Этот алгоритм перерабатывает выражение, записанное с использованием цифр 0,1,...,9, Результатом является выражение, записанное с помощью цифр 0,1,,..,9. Таким образом, имеем процедуру преобразования некоторых символьных входов (цифр, означающих слагаемые) в определенные символьные выходы (цифры, означающие сумму). Аналогичная ситуация имеет место и для остальных арифметических операций. В общем случае понятно, что алгоритм есть преобразование каких-то входов, записанных с помощью некоторых символов, в выходы, записанные тоже с по­ мощью символов. Грубо говоря, алгоритм - это детерминированная процедура, которую можно применять к любому элементу некоторого класса символьных входов и которая для каждого такого входа дает через конечное число действий (шагов) соответствующий символьный выход. Существенными чертами неформального понятия алгоритма оказываются следующие: 1 - алгоритм задается как набор инструкций конечных размеров, т. е. его можно описать конечным набором слов и специальных символов; 2 - имеется вычислитель, например человек, который умеет обращаться с инструкциями и производить вычисления; 3 - алгоритм имеет некоторое число входных данных; 4 - имеется возможность для выделения, запоминания и повто­ рения шагов вычисления; 5 - для каждого данного входа вычисление (преобразование входа) производится по данным инструкциям; 6 - с помощью алгоритма получается одно или несколько выходных данных. Легко заметить аналогию с цифровыми вычислительными машинами. * Полное имя Аль-Хорезми следующее: Лль-Хорезми Аб у Абдалла Мухаммед бен Муса аль-Маджуси, 218