Вычислимые функции и их алгоритмы

Материал из synset
Версия от 16:25, 29 августа 2010; WikiSysop (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Формальные доказательства << Оглавление >> Немного программирования

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

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

Logic1.png

Таким образом есть программа (строка "") и вычислитель (маркер), который на данном шаге выполнения алгоритма указывает на один символ — инструкцию для компьютера (на рисунке выше это треугольник, стоящий на инструкции "").

Программы записываются на некотором формальном языке программирования. Это может быть язык машины Тьюринга, ассемблер для процессоров с бесконечной разрядностью, или С++, в котором нет ограничения на размер целочисленных переменных. Формальный язык определяется при помощи синтаксических правил. Это означает, что всегда можно отличить "бессмысленную" последовательности символов от тех, по которым может перемещаться вычислитель. Ситуация полностью аналогична, например, арифметике, где правильно построенная формула "" отличима от неправильной: "".

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

Кроме программы и вычислителя существует память, в которую могут помещаться натуральные числа, вычисляющиеся по мере выполнения алгоритма. Память можно считать некоторым бесконечным упорядоченным множеством . Величины называются "ячейками памяти". Перед началом работы алгоритма, все , для определённости, равны нулю. В момент "запуска" алгоритма на выполнение, в первые элементы памяти помещаются значения входных аргументов функции . Порядок перемещения вычислителя по тексту программы зависит как от символов программы, так и от значений чисел в памяти (начальных или "промежуточных").

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

Logic2.png

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

Функция — это "ящик" с несколькими входами , и одним выходом :

Logic3.png

Фразы "один вход" или "один выход" не являются принципиальными. Понятно, что упорядоченных целых чисел всегда можно представить как одно, и наоборот. Для этого достаточно взять первых простых чисел и вычислить . Обратная операция разложения на простые множители одного числа позволяет восстановить значения всех . Тем не менее, будем считать, что может быть несколько входов, но выход всегда один.

Компьютер может вычислять некоторые "очевидно вычислимые" функции, например, складывать два числа: . Они берутся из памяти, а индекс обозначает номер числа в упорядоченной последовательности . Результат тоже помещается в память, с указанием номера ячейки. Для этого в языке есть операция присвоения: (1-я и 2-я ячейки складываются и отправляются в 3-ю):

(в ячейке будет 10). Точка с запятой — это разделительный символ (отделяющий инструкции). Пробелы компьютером пропускаются. В качестве номера ячейки может выступать явно заданное натуральное число: или число из другой ячейки: .

Кроме этого, можно выяснить равны ли между собой два числа:

Символы обозначают некоторые куски программы (строки). Если число равно , то вычислитель переходит к выполнению строки , после чего выполняет строку . Если же условие в круглых скобках не выполняется, то пропускается и сразу начинает выполняться строка . Выполнить кусок программы означает, что вычислитель должен дойти до конца строки, которая её описывает. Фигурные скобки ограничивают блок . Для упрощения разрешим также символ меньше: , т.е. если то , иначе .

Компьютер может перескочить в любую точку программы. Для этого вводится понятие метка к которой нужно перепрыгнуть. Так, следующий алгоритм:

требует от компьютера выполнить , затем проигнорировать "#1;", выполнить , а встретив "goto(1);", найти в тексте программы "#1;" и начать работать сразу после неё (выполнять ). Предполагается, что метка "#1;" с данным номером в программе есть и только одна. Различных меток "#1;" "#2;",... может быть сколь угодно много.

Последняя, необходимая для описания алгоритмов команда

приводит к остановке работы компьютера с сообщением, что в ячейке находится результат вычисления (т.е. возвращается значение функции). Даже если вычислитель дошёл до конца программы , и остановился, но там нет инструкции return, — то алгоритм не закончен!

Приведенный выше язык составления программ алгоритмов будем называть BASE. Он и объекты достаточны для описания любого алгоритма. Точнее, наоборот:

всё, что выражается в терминах приведенных выше символов, по определению является алгоритмом.

Для дальнейшего анализа удобно ввести понятие совокупности функций, хотя их всегда можно имитировать в рамках только BASE.

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

Указание аргументов функции в скобках необходимо только для того, чтобы единообразным образом можно было использовать их и в текстах описания алгоритма функции. Другими словами, мы предполагаем, что значение вычислений некоторой функции (число) может быть использовано в алгоритме любой функции, также как и ячейка памяти (см. выше описание ). Всё это уже расширение языка (т.н. BASE с функциями).

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

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


Формальные доказательства << Оглавление >> Немного программирования

Истинность и доказуемость - о конструктивной математике, Канторе и Гёделе