Алгоритмы, потенциальная осуществимость, вычислимость
По мнению Д.Кнута, интеллектуальное ядро информатики составляют алгоритмы, а вопрос о том, что алгоритмизируемо, он называет одним из самых волнующих вопросов современности. Понятие алгоритма было известно человечеству давно, однако активные исследования в этой области начали осуществляться с двадцатых годов XX века.
Понятие алгоритма тесно связано с идеализацией (абстракцией) потенциальной осуществимости.
Пример — число
Число большое, но его можно считать конструктивно. Его конструктивность в потенциальной осуществимости процесса его записи — если бы у нас было время и много бумаги, мы могли бы завершить запись этого числа. Для завершения этого процесса, нужно выполнить принципиально конечное число актов поведения. Эти акты поведения могут относиться как к материальным об'ектам, так и к ментальным сущностям. Во избежание всяческих недоразумений, эти действия должны носить элементарный характер. Различный набор элементарных действий определяет различные подходы к уточнению идей вычислимости
1. Рекурсивный подход Чёрча
Основания заложены К.Гёделем. Большое значение в формировании подхода сыграли труды А. Чёрча, Ст. Клини.
Исходные об'екты — натуральные числа. Над ними определяют простейшие функции, именуемые рекурсивными. Примитивно-рекурсивные функции составляют основу математической деятельности (пример — операция взятия числа, следующего за данным).
На основе примитивно-рекурсивных функций строятся более сложные функции.
В некоторых схемах приходится привлекать условный оператор, что вносит некоторого рода неопределенность, которая не принимается в классической теории функций. Однако, такая неопределенность кажется вполне естественной, если смотреть на математику как на творческий процесс, как на процесс создания новых знаковых моделей.
Главное, что все действия являются надежными, т.е. понятными, элементарными и обозримыми.
2. Подход Тьюринга
Он исходил из посылки, что механические операции являются наиболее простыми и надежными. А. Тьюринг предложил принципиально осуществимую конструкцию, которая получила название машины Тьюринга.
Основное свойство машины в том, что она имеет конечное число внутренних состояний. Кроме того, она реагирует на знаки из некоторого набора — внешнего алфавита. Эти знаки нанесены на ленте, которая по предположению является потенциально бесконечной в обе стороны (потому машину и называют абстрактной).
В лице Тьюринга математика вернулась к своему первоисточнику — к механическим материальным процессам. (с) Белков и Тростников
Доказано, что машина Тьюринга в состоянии делать все, что могут делать с числами рекурсивные функции.
3. Подход А.А.Маркова
К каким элементарным и математически точно определенным операциям можно было бы свести все процедуры, широко применяемые в математике и других науках? Искомое точное определение алгоритмов должно соответствовать содержательно-интуитивному пониманию алгоритмов в математике.
В работах Маркова получила развитие идея, что все математические алгоритмы сводятся к повторению одной элементарной операции, выполняемой в строгом соответствии с начертанным на бумаге предписанием, которое после очень простого об'яснения на естественном языке или после демонстрации нескольких примеров, становится ясным каждому человеку, и всеми людьми понимается одинаково.
Алгоритмы по Маркову — это вертикальный список команд (формул подстановки).
Сравнение подходов
- аппарат рекурсивных функций ближе всего к классической математике, т.к. оперирует только числами
- машины Тьюринга стоят дальше от тех понятий, которые, по традиционному мнению, должны интересовать математика. Но сама идея механистичности имеет давнюю традицию.
- алгоритмы Маркова, на первый взгляд представляющие собой "игру в слова", позволяют дать представление о том, что такое алгоритм вообще, и тем самым расширить круг рассматриваемых математиками и информатиками структур и процессов.
Возникает серьезный вопрос — насколько полно рекурсивные функции, машины Тьюринга, алгоритмы Маркова представляют идею вычислимости? Все ли функции могут быть сведены к представленным простейшим операциям? На этот вопрос отвечают тезис Чёрча-Тьюринга (в самой общей форме он гласит, что любая интуитивно вычислимая функция является частично вычислимой, или, что тоже самое, может быть вычислена некоторой машиной Тьюринга) и принцип нормализации Маркова (принцип нормализации эквивалентен тезису Чёрча).
Эти утверждения в принципе недоказуемы, т.к. в них устанавливается тождество между понятиями интуитивными и понятиями строго определенными.
