Проблема вычислимости. 
Философия науки

Обсудив понятие информации, следует перейти к следующему вопросу. А именно, говоря простым языком, что, собственно, можно с этой информацией делать. С точки зрения «информатики», оперирование информацией — это и есть выполнение программы. А «программирование» — это написание правил, следуя которым можно преобразовать информацию к требуемому виду.

С технической точки зрения, программирование есть планирование поведения некой автономной системы^[1]. На инженерном уровне такой автономной системой может быть компьютер. Традиционно принято, что компьютер (реальный вычислитель) есть реализация Машины Тьюринга, а само вычисление есть процесс обработки данных в идеальном случае.

Проблему разрешимости, в се предельном варианте, исследовал А. Тьюринг (Entscheidungsproblem). Эта проблема формулировалась как проблема о существовании универсальной механической процедуры, позволившей бы решить все математические задачи^[2]. В своей статье «On computable numbers, with an application to the entscheidungsproblem», вышедшей в ноябре 1936 г., он описал модель «машины», не затрагивая каких-либо практических аспектов реализации. Универсальность этой процедуры понималась как «возможность промоделировать поведение любой другой машины такого же типа». Предполагалось, что в разрешимой теории на каждую проблему, которая только может быть сформулирована в ее словаре, имеется ответ, причем ответ этот можно получить чисто механическим образом, следуя некоторым фиксированным предписаниям^[3].

За время развития компьютерных технологий было построено множество реальных вычислительных машин и алгоритмов, решающих многие важные задачи. Это обстоятельство заставляет серьезнее отнестись к известной философской проблеме о соотношении теоретического уровня научных исследований и практического применения полученных результатов. Для компьютерных наук в этом смысле интересно сопоставление понятий алгоритма, которые дают А. Тьюринг и Д. Кнут.

По А. Тьюрингу, для любого алгоритма существует машина Тьюринга, которая может его исполнить. То есть машина Тьюринга (или ее эквивалент) определяет понятие алгоритмической (выполнимой = рекурсивной = = механической) процедуры [13, с. 357].

Д. Кнут, будучи сам разработчиком нескольких языков программирования, определяет алгоритм посредством перечисления его свойств, а не теоретически. Последнее, среди прочих, указанное Д. Кнутом свойство, — эффективность алгоритма. «Алгоритм обычно считается эффективным, если все его операторы достаточно просты для того, чтобы их можно было точно выполнить в течение конечного промежутка времени с помощью карандаша и бумаги» [11, с. 24]. Такое определение, с одной стороны, накладывает ряд ограничений, с другой стороны, гарантирует возможность его реализации, поскольку позволяет оформить тот или иной процесс в виде задачи.

Это противопоставление обозначает два разных рода деятельности, переплетающихся в компьютерных науках, а именно, математику и инженерию. В различных областях компьютерной науки эти роды деятельности представлены по-разному. Можно сказать, что их пропорция образует целый спектр от теории алгоритмов (с преобладанием дискретной математики в ней) до системного программирования (с преобладанием инженерной составляющей построения сложных систем), между которыми находятся «смешанные» области, такие как криптография или теория компиляторов.

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

• [1] Из чего, кстати, проистекает любопытный терминологический курьез: математическая дисциплина " mathematical programming" - на русский традиционно переводится как «математическое программирование», хотя на самом деле является, конечно, «планированием» и не предполагает написания каких-либо программ.
• [2] В рамках математической логики она известна как «проблема алгоритмической разрешимости», которая была поставлена Давидом Гильбертом (доклад на Международном математическом конгрессе 1928 г. в Болонье). Эта проблема состояла в отыскании универсальной алгоритмической процедуры для решения математических задач, а точнее, в поиске ответа на вопрос о принципиальной возможности такой процедуры.
• [3] Эту проблему можно выразить следующим вопросом. Верно ли, что обладая очень хорошо формализованной системой, можно придумать алгоритм, который преобразует имеющиеся данные любым желаемым способом?