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

·>Что значит "реализовывал"? Алгоритм либо работает, либо нет — т.е. выдаёт ровно те же ответы что и f при всех значениях x, либо нет.

Алгоритм реализует функцию f(x) = 42, эквивалентную приведённой тобой, но не являющуюся ею.

·>, где isFermaTheoremCorrect(x) — возвращает false если найдены a,b,c,n < x удовлетворяющие теореме Ферма
·>- тоже реализует ровно ту же функцию, но доказать это несколько сложнее.

Если isFermaTheoremCorrect частично рекурсивна -- это не "несколько сложнее", а невозможно доказать в принципе.

·>Если я правильно понял твою запись, то хотя бы с помощью алгебры:

И где эта алгебра в приведённом алгоритме?

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

Под корректной работой алгоритма подразумевается, что:

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

Так -- достаточно формально? И, повторю свой вопрос, какая посылка изначально привела к тем вопросам, которые ты задал?