Поиски алгоритмов решения

Поиски алгоритмов решения все более сложных задач сделали актуальными исследования в области предельных ограничений самих процессов алгоритмизации. Если не существует алгоритма выполнения задания, то это задание не может быть выполнено машиной. Говорят, что задача, решение которой может быть описано с помощью алгоритма, является алгоритмической. Из этого определения следует, что машины способны выполнять только алгоритмические задания.

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

Стремление исследовать свойственные алгоритмическим методам ограничения, вытекающие из сделанного Геделем открытия, привело математиков к разработке понятия абстрактных машин, предназначенных для выполнения алгоритмов, и изучению теоретических возможностей этих гипотетических машин. (Это было еще до того, как технология позволила создать действующие машины для проведения подобных исследований.) В настоящее время результаты подобных исследований алгоритмов и машин представляют теоретические основы компьютерных наук. Некоторые темы из этой области мы рассмотрим в главе 11.