45. Различные аспекты понятия алгоритм. Фундаментальный аспект

Принимаемая человеком информация или информация, связанная с построенной моделью так или иначе обрабатывается и возможно запоминается. Обработка информации может происходить осознанно или на уровне подсознания. Но в любом случае эта обработка производится по каким-то правилам, над информацией выполняется некоторая последовательность действий. В результате получается, вообще говоря, некоторая новая информация, которая представлена в форме опять же сообщения. Эти правила обработки, эту последовательность действий принято называть алгоритмом.

Фундаментальный аспект понятия алгоритм.

Некоторые этапы построения математики:

1. Дедуктивный (аксиоматический) подход Пифагора (580-500 г.г. до н.э.).

2. Арифметический подход, середина XIX века. Нуль, отрицательные числа и дроби, можно представлять парами натуральных чисел: 0->{1,1}; -5->{1,6}; 2/3->{2,3}, и т.д.

3. Подход теории множеств, конец XIX - начало XX века.

4. Конструктивное направление теории множеств. Следует использовать только такие математические объекты, для которых существует или для которых можно разработать алгоритм их построения.

46. Логические теории алгоритмов. Тезис Черча.

Примеры выявленных неразрешимых проблем, то есть задач, для которых не существует способа их решения.

Задача о квадратуре круга: требуется найти метод (алгоритм) построения с помощью циркуля и линейки квадрата равновеликого данному кругу.

Задача о трисекции угла: требуется найти способ деления с помощью циркуля и линейки произвольного угла на три равные части.

Необходимо своевременное выявление неразрешимых проблем, с тем чтобы не затрачивать бесполезно время и усилия. То есть, необходимо доказывать отсутствие алгоритма решения той или иной задачи.

Эти задачи решаются с помощью строгих и точных методов классических теорий алгоритмов: теории рекурсивных функций, теории машины Поста, теории машины Тьюринга, теории нормальных алгоритмов Маркова. Классические теории алгоритмов иногда объединяют под общим названием логической теории алгоритмов.

Любой объект может быть представлен, закодирован цепочкой символов в некотором алфавите. Следовательно, можно считать, что алгоритм - это правило преобразования кодов в некотором алфавите. Любой код в любом алфавите может быть представлен двоичным кодом, который в свою очередь может трактоваться как целое неотрицательное число. Следовательно, любому алгоритму может быть поставлена в соответствие функция, отображающая множество целых неотрицательных чисел в себя.

Тезис Черча

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

Таким образом проблема существования или не существания алгоритма сводится к решению вопроса о существовании или не существовании соответствующей рекурсивной функции.

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