Программы как математические объекты

Фундаментальный подход в компьютерных науках предполагает понимание программ как математических объектов, о которых можно рассуждать с математической строгостью. Математически программа больше, чем ее представление на языке программирования, например таком как CFPascal. Аналогичная ситуация с числами. Число тринадцать – математический объект, который имеет свойство быть тринадцатью вне зависимости от того, как это число будет представлено в письменной или устной форме: словом «двенадцать», набором цифр «12», или в римском варианте «XII» или «дюжина». Все эти представления являются строками символов. Разница между числом и его устным или письменным обозначением в том, что число имеет определенные математические свойства, не зависимые от того, как мы называем или обозначаем это число. Двенадцать – это на два больше, чем десять, четное, кратное трем, четырем, шести и т.д.

Выделение концепции натуральных чисел в виде набора аксиом было большим достижением в математике, сделанным итальянским математиком Джузеппе Пеано, который жил на рубеже XIX и XX веков.

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

1) 0 есть натуральное число;

2) следующее за натуральным числом есть натуральное число;

3) 0 не следует ни за каким натуральным числом;

4) если натуральное число а следует за натуральным числом b и за натуральным числом с, то b и с тождественны;

5) если какое-либо предложение доказано для 0 и если из допущения, что оно верно для натурального числа n, вытекает, что оно верно для следующего за п натурального числа, то это предложение верно для всех натуральных чисел.

Последняя аксиома - аксиома полной индукции - даёт возможность доказывать общие свойства натуральных чисел.

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

1 для s(0)

2 для s(1) = s(s(0))

…

10 для s(9) = s(s(8)) = …

…

100 для s(99) = s(s(98)) = …

Математические свойства чисел 0, 1, 2, …, 10, …, 100,… зависят только от 0 и s, а не от представления их с помощью цифр. Например, 10 > 8, потому что существует выражение

10 = s(s(8)), 5 = 3 + 2, потому что 5 = s(s(3)) (s использовано дважды). Нужно заметить, что представления чисел ни разу не использованы в работе Пеано, за исключением символа 0, который достаточно условно взят как символ начала последовательности.

Большинство людей имеют дело с обычными представлениями чисел, например при сложении, делении и т.д. Понимание чисел как математических объектов, например, через аксиомы Пеано, обычно является областью деятельности тех, кто изучает математику в соответствующих вузах. Но операции, которые мы выполняем над числами, используя их некоторые представления, основаны именно на свойствах чисел. Например, при нахождении квадратного корня из 100 мы используем свойства десятичного представления числа и легко получаем 10, та же самая процедура будет сложнее, если мы будем пользоваться римским представлением чисел, но даст тот же результат, потому что вычисление квадратного корня базируется на свойстве числа, а не на его представлении.

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

Свойство программ, которое не зависит от их представления, синтаксиса – управление поведением компьютером. Программа, которая сортирует строку, конечно имеет представление, выраженное в соответствии с синтаксическими правилами, но суть того, что она делает – сортировка. Может существовать множество программ на CF Pascal, которые сортируют строку, подобно тому как число 12 может быть получено из 11+1, 10+2, 7+5 и т.д. Аналогичные программ могут быть написаны на других языках программирования, таких как BASIC или С. Каждый язык программирования – всего лишь средство выражения способа решения задачи аналогично тому, как арабские или римские цифры представляют натуральные числа. Функциональное поведение программы независимо от ее представления на том или ином языке программирования и конкретной формы для выбранного языка.

Таким образом, понимание программ как математических объектов – это понимание функционального поведения программ по управлению компьютером.