Здравствуйте, kochetkov.vladimir, Вы писали:

KV>·>Что значит "реализовывал"? Алгоритм либо работает, либо нет — т.е. выдаёт ровно те же ответы что и f при всех значениях x, либо нет.
KV>Алгоритм реализует функцию f(x) = 42, эквивалентную приведённой тобой, но не являющуюся ею.
А какая разница между "являться" и "быть эквивалентным"? Учти, даже то, что f(x) = 42 эквивалентна f(x) = 42 + x — x требует хоть и тривиального, но доказательства.

KV>·>, где isFermaTheoremCorrect(x) — возвращает false если найдены a,b,c,n < x удовлетворяющие теореме Ферма
KV>·>- тоже реализует ровно ту же функцию, но доказать это несколько сложнее.
KV>Если isFermaTheoremCorrect частично рекурсивна -- это не "несколько сложнее", а невозможно доказать в принципе.
Доказать возможно (и теорема Ферма была доказана!), но если ты намекаешь на Проблему Останова и Ко., то это о другом — написать алгоритм, который будет доказывать _любой_ алгоритм — невозможно. При этом заметь, что написать алгоритм, который в частности доказывает конкретно Теорему Ферма — возможно!

KV>·>Если я правильно понял твою запись, то хотя бы с помощью алгебры:
KV>И где эта алгебра в приведённом алгоритме?
Алгебры в алгоритме нет. Алгебра используется для построения доказательства функции.

KV>·>Я просто пытаюсь свести твои рассуждения к формальным понятиям из теории алгоритмов. А ты оперируешь какими-то терминами без каких-то точных значений, и из них получаешь странные выводы.
KV>Под корректной работой алгоритма подразумевается, что:
KV>а) алгоритм останавливается на всех элементах принадлежащих области определения реализуемой им функции (и только на них);
KV>б) любой полученный алгоритмом результат соответствует отображению, которое определяет реализуемая им функция.
KV>Так -- достаточно формально? И, повторю свой вопрос, какая посылка изначально привела к тем вопросам, которые ты задал?
Ок. Верно. Давай рассмотрим алгоритм "print 42". Он по обоим твоим пунктам удовлетворяет для функции f(x) = 42 + x — x. Так? Значит он корректно работает. Так?