Теза Черча

Матеріал з Вікіпедії — вільної енциклопедії.

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

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

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

• Енциклопедія кібернетики, т. 2, с. 530.

[ред.] Дивіться також

• Теорія алгоритмів

Це незавершена стаття з математики. Ви можете допомогти проекту, виправивши або дописавши її.