Затем студентка отсортировала матрицу по строкам. Если какой-то фрагмент оказывается повторяющимся, то в отсортированной матрице две соседние строки должны оказаться идентичными.
| T | . | . | . | C | C |
| G | G | A | |||
| T | G | G | A | C | C |
| . | . | . |
Проверка этого условия оказывается тривиальной задачей. Причина, по которой APL- программа оказалась быстрее, не имела ничего общего со скоростью работы APL по сравнению с Fortran. Главным было то, что программа на Fortran использовала алгоритм со сложностью O(M ґN 2), в то время как алгоритм сортировки APL-программы требовал примерно O(M ґN log N) операций.
Ключевой момент этой истории не в том, что APL является лучшим языком программирования, чем Fortran, но в том, что APL-программист естественным образом пришел к более удачному решению. В частности, из-за того, что на языке APL очень неудобно организовывать циклы, а сортировка является тривиальной операцией— ей соответствует встроенный оператор языка. Таким образом, раз уж сортировку можно столь легко использовать, хороший APL-программист всегда старается найти для нее новое применение. В этом смысле язык программирования, на котором записывается решение задачи, напрямую влияет на ход мыслей программиста, заставляя его рассматривать задачу под определенным углом.
1.2.3. Принцип Чёрча и гипотеза Ворфа
Легко поверить в утверждение, что язык, на котором высказывается идея, направляет мышление. Однако есть более сильное утверждение, известное среди лингвистов как гипотеза Сапира–Ворфа. Она идет еще дальше, хотя и является спорной[Pullum 1991].
Гипотеза Сапира–Ворфа утверждает, что индивидуум, использующий некоторый язык, в состоянии вообразить или придумать нечто, не могущее быть переведенным или даже понятым индивидуумами из другой языковой среды. Такое происходит, если в языке
второго индивидуума нет эквивалентных слов и отсутствуют концепции или категории для идей, вовлеченных в рассматриваемую мысль. Интересно сравнить данную идею с прямо противоположной концепцией в информатике— а именно принципом Чёрча.
В 30-хгодах у математиков пробудился большой интерес к различным формализмам, которые могут быть использованы при вычислениях. Эти идеи получили развитие в40– 50-хгодах, когда они привлекли внимание молодого сообщества специалистов по информатике. Примерами таких систем являются модели, предложенные Чёрчем
[Church 1936], Постом [Post 1936],Марковым [Markov 1951],Тьюрингом [Turing 1936],
Клини [Kleene 1936] и другими. В одно время приводилось множество аргументов, доказывающих, что каждая из этих систем может быть использована для моделирования остальных. Часто такие доводы были двухсторонними, показывая, что обе модели эквивалентны с некой общей точки зрения. Все это привело логику Алонзо Чёрча к гипотезе, которая теперь связана с его именем.
Принцип Чёрча: Любое вычисление, для которого существует эффективная процедура, может быть реализовано на машине Тьюринга.
По самой своей природе это утверждение недоказуемо, поскольку мы не имеем строгого определения термина «эффективная процедура». Тем не менее до сих пор не было найдено контр примера, и убедительность очевидности, по-видимому, благоприятствует принятию этого утверждения1 .