Теза Черча — Тюрінга — Вікіпедія

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

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

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

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

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

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

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