Ключевой момент этой истории не в том, что APL является лучшим языком
программирования, чем Fortran, но в том, что APL-программист естественным образом
пришел к более удачному решению. В частности, из-за того, что на языке APL очень
неудобно организовывать циклы, а сортировка является тривиальной операцией — ей
соответствует встроенный оператор языка. Таким образом, раз уж сортировку можно
столь легко использовать, хороший APL-программист всегда старается найти для нее
новое применение. В этом смысле язык программирования, на котором записывается
решение задачи, напрямую влияет на ход мыслей программиста, заставляя его
рассматривать задачу под определенным углом.
1.2.3. Принцип Чёрча и гипотеза Ворфа
Легко поверить в утверждение, что язык, на котором высказывается идея, направляет
мышление. Однако есть более сильное утверждение, известное среди лингвистов как
гипотеза Сапира–Ворфа. Она идет еще дальше, хотя и является спорной [Pullum 1991].
Гипотеза Сапира–Ворфа утверждает, что индивидуум, использующий некоторый язык, в
состоянии вообразить или придумать нечто, не могущее быть переведенным или даже
понятым индивидуумами из другой языковой среды. Такое происходит, если в языке
второго индивидуума нет эквивалентных слов и отсутствуют концепции или категории
для идей, вовлеченных в рассматриваемую мысль. Интересно сравнить данную идею с
прямо противоположной концепцией в информатике — а именно принципом Чёрча.
В 30-х годах у математиков пробудился большой интерес к различным формализмам,
которые могут быть использованы при вычислениях. Эти идеи получили развитие в 40–
50-х годах, когда они привлекли внимание молодого сообщества специалистов по
информатике. Примерами таких систем являются модели, предложенные Чёрчем
[Church 1936], Постом [Post 1936], Марковым [Markov 1951], Тьюрингом [Turing 1936],
Клини [Kleene 1936] и другими. В одно время приводилось множество аргументов,
доказывающих, что каждая из этих систем может быть использована для моделирования
остальных. Часто такие доводы были двухсторонними, показывая, что обе модели
эквивалентны с некой общей точки зрения. Все это привело логику Алонзо Чёрча к
гипотезе, которая теперь связана с его именем.
Принцип Чёрча: Любое вычисление, для которого существует эффективная процедура, может быть
реализовано на машине Тьюринга.
По самой своей природе это утверждение недоказуемо, поскольку мы не имеем строгого
определения термина «эффективная процедура». Тем не менее до сих пор не было
найдено контрпримера, и убедительность очевидности, по-видимому, благоприятствует
принятию этого утверждения
1
.
1
Создание математического формализма вычислимости было связано с необходимостью определить
понятие алгоритма. Пока исследования в этой области шли успешно, каждая новая формализованная
последовательность вычислений получала имя «алгоритм» просто по определению. Когда же математики
столкнулись с задачами, для которых пришлось доказывать отсутствие алгоритма, потребовалось
формальное определение. В настоящий момент принято считать, что алгоритмом является
последовательность действий, которая может быть сведена к программе, выполняемой с помощью машины
Тьюринга. Или, в эквивалентной форме: последовательность действий, которая может быть сведена к
программе для машины Поста, или конечного автомата Маркова, или же к последовательности рекурсивных
функций Клини и Чёрча, является алгоритмом. Доказано, что все эти формальные системы вычислимости
являются эквивалентными. Тем самым принцип Чёрча является аксиомой, не требующей доказательства,
которая формализует понятие алгоритма («эффективной процедуры») и в силу статуса аксиомы
опровергающего контрпримера иметь не может. — Примеч. перев.
PDF created with pdfFactory Pro trial version www.pdffactory.com