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