Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій, Детальна інформація

клас РФ спiвпадає з класом тотальних АОФ, заданих на множинi натуральних чисел.

Значення тези Чорча (скорочено ТЧ) полягає в наступному.

1) Прийняття тези Чорча перетворює iнтуїтивнi поняття алгоритму, обчислюваностi, розв’язностi в об’єкти математичного вивчення.

2) Використання тези Чорча як своєрiдної аксiоми дозволяє в багатьох випадках замiнити формальнi завдання алгоритмiв на неформальнi їх описи. Це дає iстотне спрощення доведень, звiльняючи його вiд зайвих деталей. Проте доведення на основi тези Чорча має бути ретельно аргументованим! При виникненнi сумнiвiв треба вміти провести чисто формальне доведення.

теж є ЧРФ. Для цього розглянемо процес глобального обчислення всіх значень функції f. Такий процес розіб'ємо на етапи. На кожному етапі починаємо обчислення для наступного значення аргументу. На етапі 0 робимо 1-й крок обчислення f(0). На етапі 1 робимо 1-й крок обчислення f(1) та 2-й крок обчислення f(0) і т.д. На етапі п робимо 1-й крок обчислення f(п), 2-й крок обчислення f(п-1), … , (п+1)-й крок обчислення f(0). Якщо на якомусь етапі обчислення певного f(т) завершується, порівнюємо f(т) та х. При умові f(т)=х процес глобальних обчислень завершується, адже тоді х(Ef , тому результатом нашої роботи буде число 1. При умові f(т)(х продовжуємо процес глобальних обчислень. Таким чином, описано алгоритм для обчислення функції h(x), звідки за тезою Чорча функція h(x) є ЧРФ.