Общее понятие программы

Понятие программы обычно определяется в контексте некоторого языка программирования. Представление об общем понятии программы, абстрагированное от конкретного языка программирования, для специалиста в области информатики суммируется из его опыта работы с разными языками программирования. В литературе хорошо представлены различные аспекты языков программирования: типы данных, модульность, объектная ориентированность, параллелизм и др. (см., например, [13]). Однако сумма разных аспектов не дает четкой интегрированной концепции общего понятия программы. Этот пробел обнаруживается в учебных курсах по основам программирования и в энциклопедиях. Возможно, лучшим кратким определением в энциклопедиях является следующее: «программа есть описание алгоритма решения задачи, заданное на языке программирования» [1].

Понятия алгоритма и программы не тождественны. Понятие алгоритма известно давно и считается хорошо изученным. В математике существуют следующие формализации понятия алгоритма: машина Тьюринга [10], частично рекурсивные функции, нормальный алгорифм Маркова [2] и каноническая система Поста [3]. Понятие программы появилось вместе с первыми компьютерами в 1940-х [1].

Имеются два определяющих свойства программы: автоматическая вычислимость и существование спецификации.