Вычислимость функції
При відповідному кодуванні натуральних чисел у вигляді послідовностей символів функція на натуральних чисел називається обчислюваною за версією Тюрінга, якщо абстрактна машина знаходила потрібний алгоритм і виводила цю функцію на стрічці. Подібне пристрій, якого не існувало в 1930-х, в майбутньому стали вважати комп’ютером. Абстрактна машина Тьюринга і теза Черча стали провісниками ери розвитку обчислювальних пристроїв. Було доведено, що формально визначені обома вченими класи функцій співпадають. Тому в результаті обидва твердження об’єднали в одну. Обчислювальні функції і теза Черча також надали сильний вплив на концепцію обчислюваності. А також стали важливою підмогою для математичної логіки і теорії доказів.
Обґрунтування та проблеми методу
Існують суперечливі точки зору на тезу. Численні докази були зібрані для «робочої гіпотези», запропонованої Черчем і Тюринг в 1936 році. Але всі відомі методи або операції для виявлення нових ефективно обчислюваних функцій заданих були пов’язані з методами побудови машин, яких тоді не існувало. Для того щоб довести теза Черча-Тюрінга, виходять з того факту, що кожна реалістична модель обчислень еквівалентна.
Із-за різноманітності різних аналізів, як правило, це вважається особливо переконливим доказом. Всі спроби більш точно визначити інтуїтивне поняття ефективно обчислюваної функції виявилися еквівалентними. Кожен запропонований аналіз довів, що він виділяє один і той же клас функцій, а саме ті, які вычислимы машинами Тюрінга. Але деякі обчислювальні моделі виявилися більш ефективні з точки зору часових витрат і використання пам’яті для різних завдань. Пізніше зазначалося, що основні поняття рекурсивних функцій і теза Черча є, швидше, гіпотетичними.
