Доказательство конечности алгоритма

[Чудо-в-перьях]

Какие методы являются предпочтительными для доказательства конечности алгоритма? (спорю с оппонентом:))

[Dandan]

ну один из методов - составляете натуральнозначную функцию от текущего состояния и показываете, что она уменьшается с каждым шагом. Но так не всё можно доказать. Например, теорему Гудстейна так не докажешь, но можно для её доказательства построить функцию во вполне упорядоченное множество с порядковым числом $\epsilon_0$, уменьшающуюся на состояниях.

[Чудо-в-перьях]

Спасибо!!... Попробую;)