Loading AI tools
З Вікіпедії, вільної енциклопедії
Теза Черча — твердження, згідно з яким, клас алгоритмічно-обчислюваних функцій збігається з класом частково-рекурсивних функцій, функцій обчислюваних за Тюрінгом та інших формальних уточнень інтуїтивного поняття алгоритм. З неї випливає, що якщо функція належить до класу певної формалізації алгоритмічно-обчислюваної функції, то вона є алгоритмічно-обчислювана. Теза не доводиться. А еквівалентність класів формалізмів підлягає доведенню, що і було зроблено. Названа на честь американського математика Алонзо Черча.
Також виділяють тезу Черча-Тюрінга.
Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її. |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.