1 Создание математического формализма вычислимости было связано с необходимостью определить понятие алгоритма. Пока исследования в этой области шли успешно, каждая новая формализованная последовательность вычислений получала имя «алгоритм» просто по определению. Когда же математики столкнулись с задачами, для которых пришлось доказывать отсутствие алгоритма, потребовалось формальное определение. В настоящий момент принято считать, что алгоритмом является последовательность действий, которая может быть сведена к программе, выполняемой с помощью машины Тьюринга. Или, в эквивалентной форме: последовательность действий, которая может быть сведена к программе для машины Поста, или конечного автомата Маркова, или же к последовательности рекурсивных функций Клини и Чёрча, является алгоритмом. Доказано, что все эти формальные системы вычислимости являются эквивалентными. Тем самым принцип Чёрча является аксиомой, не требующей доказательства, которая формализует понятие алгоритма( «эффективной процедуры») и в силу статуса аксиомы опровергающего контр примера иметь не может. — Примеч. перев.
Признание принципа Чёрча имеет важное и глубокое следствие для языков программирования. Машины Тьюринга являются изумительно простыми механизмами. От языка программирования требуется немного, чтобы смоделировать такое устройство. В1960-хгодах, к примеру, было показано, что машина Тьюринга может быть смоделирована на любом языке программирования, в котором содержатся условные операторы и операторы цикла[Bohm 1966]. Этот не совсем правильно понимаемый результат был одним из основных доводов в защиту утверждения о том, что знаменитый оператор goto является ненужным.
Если мы признаем принцип Чёрча, то любой язык, на котором можно смоделировать машину Тьюринга, является достаточно мощным, чтобы осуществить любой реализуемый алгоритм. Для решения проблемы надо построить машину Тьюринга, которая выдаст желаемый результат, — согласно принципу Чёрча такая машина должна существовать для каждого алгоритма. Затем остается только смоделировать машину Тьюринга на вашем любимом языке программирования. Тем самым споры об относительной «мощности» языков программирования— если под мощностью мы понимаем «способность решать задачи», — оказываются бессмысленными. Позднее Алан Перлис ввел удачный термин для подобных аргументов, назвав их «тьюринговская пропасть», поскольку из них так сложно выбраться, в то время как сами они столь фундаментально бесполезны.
Заметим, что принцип Чёрча является в определенном смысле точной противоположностью гипотезы Сапира–Ворфа. Принцип Чёрча утверждает, что по своей сути все языки программирования идентичны. Любая идея, которая выражается на одном языке, может(согласно теории) быть реализована на другом. Гипотеза же Сапира–Ворфа,как вы помните, утверждает, что существуют идеи, не согласующиеся с этим принципом.
Многие лингвисты отвергают гипотезу Сапира–Ворфаи вместо этого принимают «тьюринговский эквивалент» для естественных языков: любая идея в принципе может быть выражена на любом языке. Например, несмотря на то что язык людей, живущих в жарком климате, не содержит готовых понятий для типов снежного покрова, в принципе южане тоже могут стать специалистами в области гляциологии. Аналогично объектно- ориентированная техника не снабжает(в теории) вас новой вычислительной мощностью, которая позволила бы решить проблемы, недоступные для других средств. Но объектно- ориентированный подход делает задачу проще и приводит ее к более естественной форме. Это позволяет обращаться с проблемой таким образом, который благоприятствует управлению большими программными системами.
Итак, как для компьютерных, так и для естественных языков справедливо: язык направляет мысли, но не предписывает их.
1.3. Новая парадигма
Объектно-ориентированное программирование часто называют новой парадигмой программирования. Другие парадигмы программирования: директивное(языки типа Pascal или C), логическое(языки типа Prolog) и функциональное(языки типа Lisp, FP или Haskell) программирование.
Интересно исследовать слово «парадигма». Следующий фрагмент взят из толкового словаря American Heritage Dictionary of the English Language:
par-a-digm(сущ.) 1. Список всех вариантов окончаний слова, рассматриваемый как иллюстративный пример того, к какому спряжению или склонению оно относится. 2.
Любой пример или модель (от латинскогоparadigma и греческогоparadeigma — модель, отparadeiknunai — сравнивать, выставлять).
На первый взгляд, склонение и спряжение слов(например, латинских) имеет мало общего с компьютерными языками. Чтобы понять связь, мы должны заметить, что слово «парадигма» пришло в программирование из оказавшей большое влияние книги «Структура научных революций», написанной историком науки Томасом Куном