Что такое доказательство существования алгоритма?

[gogoshik]

Прошу, плиз, доходчиво объяснить, что такое доказательство существования алгоритма. Допустим утверждается, что существует алгоритм чего-либо и нужно это доказать. Что я должен сделать?

[Xaositect]

Доказательств алгоритма не бывает, Вы что-то пропустили. Возможно, имеется в виду доказательство существования алгоритма, решающего заданную задачу, или доказательство корректности данного алгоритма для данной задачи.

[hazzo]

Либо предоставляете этот алгоритм с неопровержимым обоснованием, либо математически обоснуйте (доказываете) его существование в природе

[gogoshik]

Xaositect, пардон, исправил. Ну, в принципе о существовании я написал во втором предложении. Вопрос должен был быть понятен.

[thething]

Теоремы существования бывают двух типов: те, которые доказываются конструктивно (например, теорема Банаха о неподвижной точке содержит в своём доказательстве алгоритм поиска неподвижной точки) и те, которые доказываются неконструктивно (например, теорема о вложенных отрезках, которая просто говорит, что общая точка есть, но как её найти -- отдельный вопрос. Но найти-то -- можно). Вот также, видимо, и с существованием алгоритмов. По крайней мере до тех пор, пока Вы не поставите свой вопрос более конкретно.

[Евгений Машеров]

The proof of pudding is eating.
Доказательством существования алгоритма, решающего данную задачу, является сам алгоритм. Вот несуществование алгоритмов, решающих некую задачу, приходится доказывать. Например, показав, что предположение о существовании такого алгоритма приводит к противоречию. Или что задача вообще не имеет решений.

[mihaild]

Евгений Машеров в сообщении #1345399 писал(а):

Доказательством существования алгоритма, решающего данную задачу, является сам алгоритм

Не обязательно. Например, легко доказать, что существует алгоритм, отвечающий, доказуема ли гипотеза Римана в ZF. Предъявить такой алгоритм существенно сложнее.

[gogoshik]

Поправьте меня, если не прав.

Пусть у нас есть задача. Тогда с алгоритмической точки зрения вопрос сводится к следующим задачам:
1. Доказать или опровергнуть сущестование алгоритма решения данной задачи.
2. Если алгоритм существует, то построить или предъявить алгоритм (что не всегда возможно).
3. Если алгоритм построен, то проверить реализуем ли он практически или нет. То есть по алгоритму составить программный код, который сможет решить задачу за приемлемое время и с приемлемыми ресурсами. Как понимаю, из построения алгоритма не всегда следует его программное решение.

[Someone]

gogoshik в сообщении #1345619 писал(а):

1. Доказать или опровергнуть сущестование алгоритма решения данной задачи.
2. Если алгоритм существует, то построить или предъявить алгоритм (что не всегда возможно).

Не совсем так. Доказать существование алгоритма можно разными способами. Например:
1) выписать явно его код (что представляет собой этот код, зависит от конкретной версии определения алгоритма);
2) предположить, что алгоритм не существует, и показать, что это приводит к противоречию;
3) сконструировать алгоритм, используя алгоритмы, для которых существование уже доказано.
Я не претендую на полноту списка.

Во втором случае мы получаем "чистую" теорему существования, и неизвестно, удастся ли нам этот алгоритм сконструировать.
Если в третьем пункте используются только алгоритмы, коды которых явно выписаны, то мы потенциально сможем выписать и код сконструированного нами алгоритма.

Существует некоторое количество различных определений алгоритма (частично рекурсивная функция, машина Тьюринга, машина Поста, нормальный алгорифм Маркова; на полноту списка не претендую). Известно, что все они эквивалентны.

gogoshik в сообщении #1345619 писал(а):

3. Если алгоритм построен, то проверить реализуем ли он практически или нет. То есть по алгоритму составить программный код, который сможет решить задачу за приемлемое время и с приемлемыми ресурсами. Как понимаю, из построения алгоритма не всегда следует его программное решение.

Такого требования вообще нет. В определении алгоритма неявно предполагается, что он располагает неограниченными ресурсами. Его код должен быть конечным, но может быть сколь угодно длинным. В процессе работы он может требовать сколь угодно много ресурсов (пространства и времени). Если он в конце-концов остановится, мы получим какой-то результат. Но он может и не остановиться.

Если же речь идёт о реализации алгоритма в виде компьютерной программы, то ресурсы будут ограничены, и в таком случае не всякий алгоритм можно реализовать на практике.