Теза Черча

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Теза Черча — твердження, згідно з яким, клас алгоритмічно-обчислюваних функцій збігається з класом частково-рекурсивних функцій, функцій обчислюваних за Тюрінгом та інших формальних уточнень інтуїтивного поняття алгоритм. З неї випливає, що якщо функція належить до класу певної формалізації алгоритмічно-обчислюваної функції, то вона є алгоритмічно-обчислювана. Теза не доводиться. А еквівалентність класів формалізмів підлягає доведенню, що і було зроблено. Названа на честь американського математика Алонзо Черча.

Також виділяють тезу Черча-Тюрінга.

Джерела інформації[ред.ред. код]

Див. також[ред.ред. код]