Существует ли такой алгорим?

Question

[vzhilin]

Существует ли алгоритм, который делает что-то тривиальное, например складывает натуральные числа, но для которого невозможно формально доказать, что он действительно складывает натуральные числа?

Comments

[ambisinister One]

vzhilin, Вот алгоритм тривиального калькулятора, которому
ни формально, ни неформально невозможно доказать, что он складывает натуральные числа)))

[ambisinister One]

Александр, У калькулятора, наверное, чувства юмора больше,
чем у Вас. Или оно само по себе работает...
=)

[ambisinister One]

Александр, akzeptiert )

Answer 1

[Wataru]

Я так понял задача в том, а есть ли алгоритм, который для двух входных чисел всегда выводит их сумму, но невозможно доказать, а выводит ли он ее или что-то другое.

Есть такой алгоритм. В общем случае он выглядит так:

Read(a);
Read(b);
DoSomething(a, b);
Write(a+b);

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

Поэтому 100% существует такой DoSomething, про который формально доказать что он не виснет нельзя. Иначе бы проблема остановки решалась.

Comments

[Mercury13]

Хотел отметить решением, но это неверно. Могут существовать частичные решения, которые скажут «да» на наш алгоритм и «ХЗ» на остальные. И если это решение гарантированно и доказанно работает для определённого класса алгоритмов — ну чем не доказательство?

Тут, блин, сложнее — теория рекурсивно перечислимых множеств.
Ну или как-то доказать, что алгоритмов, выдающих a+b, больше, чем подобных частичных решений.

[Wataru]

Mercury13, ну так точно так же могут быть частичные решения для задачи останова. Это неконструктивное доказательство. Я не знаю, что за dosomething() в искомом алгоритме. Но я знаю, что оно существует. Потому что иначе бы задача останова решалась.

[Wataru]

Mercury13, можно усложнить. пусть dosomething берет и выполняет a-ый в лексикографическом порядке алгоритм, передав ему b. Множество алгоритмов же счетное?

Вот тут уже точно любой метод проверки этого кода становится эквивалентен решению задачи останова.

[Mercury13]

Wataru, Вот теперь похоже на правду.

Answer 2

[Griboks]

Если существует алгоритм, то всегда можно формально представить его в виде функции f: A→B, которая переводит множество входных данных в множество выходных. В компьютере эти множества конечны из-за ограниченности памяти. Поэтому всегда можно выполнить полный перебор, т.е. определить функцию f.

С другой стороны, тут может быть интересен вопрос сложности алгоритма. На этом как раз базируются разнообразные хеши и шифры.

Также, возможно, вас интересует неалгоритмическая задача.

Answer 3

[Николай Савельев]

Это про NP
https://en.wikipedia.org/wiki/P_versus_NP_problem