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

{| width="100%"  
 | width="40%"|[[Формальные доказательства]] << 
 ! width="20%"|[[Истинность и доказуемость|Оглавление]] 
 | width="40%" align="right"| >> [[Немного программирования]]
|}
----
''Вычислимой'' называется функция <math>\textstyle f(x_1,...,x_n)</math> от одного или нескольких натуральных аргументов, натуральные значения которой получаются в результате выполнения некоторого ''алгоритма''. Определить термин "алгоритм" без синонимичных ссылок на себя же самого сложно. Фразы типа "дискретные, однозначные последовательные действия..." не являются полностью удовлетворительными. Поэтому считается, что "алгоритм", как и "множество" &mdash; это понятие первичное. Для определённости будем считать, что алгоритм это математическая модель уже ''существующего'' физического устройства &mdash; цифрового ''компьютера''. У него идеализируется память, которая может быть сколь угодно большой. Естественно, исключаются и форс-мажорные ситуации - перегрев, блондинки, чашки с кофе и т.п. Поэтому вычислимой будет функция, для которой можно составить ''программу'', т.е. дать ''конечное'' определение, позволяющее вычислить функцию при помощи этого идеального устройства.

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

<center>
[[File:logic1.png]]
</center>

Таким образом есть программа (строка "<math>\textstyle acbaac</math>") и вычислитель (маркер), который на данном шаге выполнения алгоритма указывает на один символ &mdash; инструкцию для компьютера (на рисунке выше это треугольник, стоящий на инструкции "<math>\textstyle c</math>").

Программы записываются на некотором формальном ''языке'' программирования. Это может быть язык машины Тьюринга, ассемблер для процессоров с бесконечной разрядностью, или С++, в котором нет ограничения на размер целочисленных переменных. Формальный язык определяется при помощи ''синтаксических правил''. Это означает, что всегда можно отличить "бессмысленную" последовательности символов от тех, по которым может перемещаться вычислитель. Ситуация полностью аналогична, например, арифметике, где правильно построенная формула "<math>\textstyle (2<1)</math>" отличима от неправильной: "<math>\textstyle 2)(1<</math>".

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

Кроме программы и вычислителя существует ''память'', в которую могут помещаться натуральные числа, вычисляющиеся по мере выполнения алгоритма. Память можно считать некоторым бесконечным упорядоченным множеством <math>\textstyle \mathcal M:\{m_0, m_1, m_2,...\}</math>. Величины <math>\textstyle m_i</math> называются "''ячейками памяти''". Перед началом работы алгоритма, все <math>\textstyle m_i</math>, для определённости, равны нулю. В момент "запуска" алгоритма на выполнение, в первые <math>\textstyle n</math> элементы памяти <math>\textstyle {\mathcal M}</math> помещаются значения <math>\textstyle n</math> входных аргументов функции <math>\textstyle f(x_1,...,x_n)</math>. Порядок перемещения вычислителя по тексту программы зависит как от символов программы, так и от значений чисел в памяти (начальных или "промежуточных").

Таким образом, компьютер состоит из ''конечной'' программы <math>\textstyle \mathcal P</math>, вычислителя <math>\textstyle \mathcal C</math>, указывающего на выполняемую инструкцию, и ''неограниченной'' памяти <math>\textstyle \mathcal M</math>, в которую могут помещаться и считываться натуральные числа. Ниже приведен пример трёх последовательных шагов некоторого алгоритма, вычисляющего функцию одной переменной <math>\textstyle f(x)</math> при <math>\textstyle x=5</math>:

<center>
[[File:logic2.png]]
</center>

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

Функция &mdash; это "ящик" с несколькими входами <math>\textstyle x</math>, и одним выходом <math>\textstyle y</math>:

<center>
[[File:logic3.png]]
</center>

Фразы "один вход" или "один выход" не являются принципиальными. Понятно, что <math>\textstyle n</math> упорядоченных целых чисел <math>\textstyle (x_1,x_2,...,x_n)</math> всегда можно представить как одно, и наоборот. Для этого достаточно взять <math>\textstyle n</math> первых ''простых чисел'' <math>\textstyle p_i</math> и вычислить <math>\textstyle x=2^{x_1}\cdot 3^{x_2}\cdot 5^{x_3}\cdot 7^{x_4}\cdot 11^{x_5}\cdot ...\cdot p_n^{x_n}</math>. Обратная операция разложения на простые множители одного числа <math>\textstyle x</math> позволяет восстановить значения всех <math>\textstyle x_i</math>. Тем не менее, будем считать, что может быть несколько входов, но выход всегда один.

<math>\textstyle \bullet</math> Компьютер может вычислять некоторые "очевидно вычислимые" функции, например, складывать два числа: <math>\textstyle m_1+m_2</math>. Они берутся из памяти, а индекс обозначает номер числа в упорядоченной последовательности <math>\textstyle {\mathcal M}</math>. Результат тоже помещается в память, с указанием номера ячейки. Для этого в языке есть операция присвоения: <math>\textstyle m_3\leftarrow m_1+m_2;</math> (1-я и 2-я ячейки складываются и отправляются в 3-ю):

:<center><math>m_1\leftarrow 5;\;\;\;m_2\leftarrow m_1;\;\;\;m_3\leftarrow m_1+m_2;</math></center>

(в ячейке <math>\textstyle m_3</math> будет 10). Точка с запятой &mdash; это разделительный символ (отделяющий инструкции). Пробелы компьютером пропускаются. В качестве номера <math>\textstyle i</math> ячейки <math>\textstyle m_i</math> может выступать явно заданное натуральное число: <math>\textstyle m_{2}</math> или число из другой ячейки: <math>\textstyle m_{m_1}</math>.

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

:<center><math>\mathbf{if}(m_i=m_j)\;\{ \mathcal P_1 \}\;\;\;\mathcal P_2</math></center>

Символы <math>\textstyle \mathcal P_i</math> обозначают некоторые куски программы (строки). Если число <math>\textstyle m_i</math> равно <math>\textstyle m_j</math>, то вычислитель переходит к выполнению строки <math>\textstyle \mathcal P_1</math>, после чего выполняет строку <math>\textstyle \mathcal P_2</math>. Если же условие в круглых скобках не выполняется, то <math>\textstyle \mathcal P_1</math> ''пропускается'' и сразу начинает выполняться строка <math>\textstyle \mathcal P_2</math>. Выполнить кусок программы <math>\textstyle \mathcal P_1</math> означает, что вычислитель должен дойти до конца строки, которая её описывает. Фигурные скобки ограничивают блок <math>\textstyle \mathcal P_1</math>. Для упрощения разрешим также символ меньше: <math>\textstyle \mathbf{if}(m_i<m_j) \;\{\mathcal P_1\}\;\mathcal P_2</math>, т.е. если <math>\textstyle m_i<m_j</math> то <math>\textstyle \mathcal P_1\mathcal P_2</math>, иначе <math>\textstyle \mathcal P_2</math>.

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

:<center><math>\mathcal P_1\;\;\;\#1;\;\;\; \mathcal P_2\;\;\;\mathbf{goto}(1);\;\;\;\mathcal P_3</math></center>

требует от компьютера выполнить <math>\textstyle \mathcal P_1</math>, затем ''проигнорировать'' "#1;", выполнить <math>\textstyle \mathcal P_2</math>, а встретив "'''goto'''(1);", найти в тексте программы "#1;" и начать работать сразу после неё (выполнять <math>\textstyle \mathcal P_2</math>). Предполагается, что метка "#1;" с данным номером в программе ''есть'' и только ''одна''. Различных меток "#1;" "#2;",... может быть сколь угодно много.

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

:<center><math>\mathbf{return}\;m_i;</math></center>

приводит к остановке работы компьютера с сообщением, что в ячейке <math>\textstyle m_i</math> находится результат вычисления (т.е. возвращается значение функции). Даже если вычислитель <math>\textstyle \mathcal C</math> дошёл до конца программы <math>\textstyle \mathcal P</math>, и остановился, но там нет инструкции '''return''', &mdash; то алгоритм не закончен!

<math>\textstyle \bullet</math> Приведенный выше язык составления программ алгоритмов будем называть BASE. Он и объекты <math>\textstyle \left\langle \mathcal P,\mathcal C, \mathcal M\right\rangle </math> ''достаточны'' для описания ''любого'' алгоритма. Точнее, наоборот: <blockquote> всё, что выражается в терминах приведенных выше символов, по определению является ''алгоритмом''. </blockquote> Для дальнейшего анализа удобно ввести понятие совокупности функций, хотя их всегда можно имитировать в рамках только BASE.

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

:<center><math>\begin{array}{ll} f_1() &\{\;\;\mathbf{return}\;1;\;\;\}\\ f_2(m_0) &\{\;\;m_1\leftarrow m_0+25;\;\;\;\;\;\;\;\mathbf{return}\;m_1;\;\;\}\\ f_3(m_0,m_1)&\{\;\;m_2\leftarrow m_0+f_2(m_1);\;\mathbf{return}\;m_2;\;\;\}\\ \end{array}</math></center>

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

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

Приведенное описание синтаксиса программы и её интерпретации компьютером можно перевести на формальный язык. Начало будет выглядеть примерно так. "Пустая строка символов является программой. Если <math>\textstyle \mathcal P_1</math> и <math>\textstyle \mathcal P_2</math> программы, то их последовательное соединение <math>\textstyle \mathcal P_1 \mathcal P_2</math> это тоже программа. Если <math>\textstyle \mathcal P</math> программа, а <math>\textstyle i</math>, <math>\textstyle k</math> целые числа, то "<math>\textstyle \mathcal P\;m_i\leftarrow k;</math>" &mdash; программа", и т.д., и т.п. Естественно, подобные описания также являются алгоритмами. Однако мы считаем их на столько простыми и естественными, что будем рады ''свести к ним'' любые другие, сколь угодно сложные алгоритмы.

----
{| width="100%"  
 | width="40%"|[[Формальные доказательства]] << 
 ! width="20%"|[[Истинность и доказуемость|Оглавление]] 
 | width="40%" align="right"| >> [[Немного программирования]]
|}
----
[[Истинность и доказуемость]] - о конструктивной математике, Канторе и Гёделе