Проблема вычислимости
Обсудив понятие информации, следует перейти к следующему вопросу. А именно, говоря простым языком, что, собственно, можно с этой информацией делать. С точки зрения "информатики", оперирование информацией – это и есть выполнение программы. А "программирование" – это написание правил, следуя которым можно преобразовать информацию к требуемому виду.
С технической точки зрения, программирование есть планирование поведения некой автономной системы[1]. На инженерном уровне такой автономной системой может быть компьютер. Традиционно принято, что компьютер (реальный вычислитель) есть реализация Машины Тьюринга, а само вычисление есть процесс обработки данных в идеальном случае.
Проблему разрешимости, в се предельном варианте, исследовал А. Тьюринг (Entscheidungsproblem). Эта проблема формулировалась как проблема о существовании универсальной механической процедуры, позволившей бы решить все математические задачи[2]. В своей статье "On computable numbers, with an application to the entscheidungsproblem", вышедшей в ноябре 1936 г., он описал модель "машины", не затрагивая каких-либо практических аспектов реализации. Универсальность этой процедуры понималась как "возможность промоделировать поведение любой другой машины такого же типа". Предполагалось, что в разрешимой теории на каждую проблему, которая только может быть сформулирована в ее словаре, имеется ответ, причем ответ этот можно получить чисто механическим образом, следуя некоторым фиксированным предписаниям[3].
За время развития компьютерных технологий было построено множество реальных вычислительных машин и алгоритмов, решающих многие важные задачи. Это обстоятельство заставляет серьезнее отнестись к известной философской проблеме о соотношении теоретического уровня научных исследований и практического применения полученных результатов. Для компьютерных наук в этом смысле интересно сопоставление понятий алгоритма, которые дают А. Тьюринг и Д. Кнут.
По А. Тьюрингу, для любого алгоритма существует машина Тьюринга, которая может его исполнить. То есть машина Тьюринга (или ее эквивалент) определяет понятие алгоритмической (выполнимой = рекурсивной = = механической) процедуры [13, с. 357].
Д. Кнут, будучи сам разработчиком нескольких языков программирования, определяет алгоритм посредством перечисления его свойств, а не теоретически. Последнее, среди прочих, указанное Д. Кнутом свойство, – эффективность алгоритма. "Алгоритм обычно считается эффективным, если все его операторы достаточно просты для того, чтобы их можно было точно выполнить в течение конечного промежутка времени с помощью карандаша и бумаги" [11, с. 24]. Такое определение, с одной стороны, накладывает ряд ограничений, с другой стороны, гарантирует возможность его реализации, поскольку позволяет оформить тот или иной процесс в виде задачи.
Это противопоставление обозначает два разных рода деятельности, переплетающихся в компьютерных науках, а именно, математику и инженерию. В различных областях компьютерной науки эти роды деятельности представлены по-разному. Можно сказать, что их пропорция образует целый спектр от теории алгоритмов (с преобладанием дискретной математики в ней) до системного программирования (с преобладанием инженерной составляющей построения сложных систем), между которыми находятся "смешанные" области, такие как криптография или теория компиляторов.
Более детальное рассмотрение вопроса соотношения математики и инженерии потребовало бы детального рассмотрения каждой области. Четкое различие между теорией, ее применением и инженерной деятельностью, характерное для физических наук, хоть и прослеживается в некоторых направлениях компьютерной науки, не столь естественно для нее.