Теза Черча-Тюрінга відноситься до поняття ефективного, систематичного або механічного методу в логіці, математиці та інформатиці. Він формулюється як опис інтуїтивного поняття обчислюваності і у відношенні до общерекурсивным функцій частіше називається тезою Черча. Він також відноситься до теорії вычислимых за допомогою комп’ютерів функцій. Теза з’явився в 1930-х роках, коли самих комп’ютерів ще не існувало. Пізніше він був названий на честь американського математика Алонзо Черча і його британського колеги Алана Тюрінга.
Ефективність методу досягнення результату
Першим пристроєм, що нагадував сучасний комп’ютер, була Bombie – машина, створена англійським математиком Аланом Тюрінгом. Вона використовувалася для розшифровки німецьких повідомлень під час Другої світової війни. Але для своєї тези і формалізації поняття алгоритму він використовував абстрактні машини, згодом названі машинами Тюрінга. Теза становить інтерес, як для математиків, так і для програмістів, так як ця ідея надихнула творців перших комп’ютерів.
В теорії обчислюваності теза Черча-Тюрінга також відомий як гіпотеза про природу вычислимых функцій. Він свідчить, що для будь-алгоритмічно обчислюваною функції на натуральних числах існує машина Тюрінга, здатна її обчислити. Або, іншими словами, є підходящий для неї алгоритм. Добре відомим прикладом ефективності цього методу є тест-таблиці істинності для перевірки тавтологичности.
Спосіб для досягнення якого-небудь бажаного результату називається «ефективною», «систематичним» або «механічним», якщо:
- Метод задається в термінах кінцевого числа точних команд, кожна інструкція виражається за допомогою кінцевого числа символів.
- Він буде виконуватися без помилок, призведе до бажаного результату через певне число кроків.
- Метод може виконуватися людиною без сторонньої допомоги будь-яким обладнанням, крім паперу й олівця
- Він не вимагає розуміння, інтуїції або винахідливості з боку людини, здійснює дії
Раніше в математиці використовувався неофіційний термін «ефективно вычислимый», щоб позначити функції, які можна обчислити за допомогою олівця і паперу. Але саме поняття алгоритмічної обчислюваності було швидше інтуїтивним, ніж чимось конкретним. Тепер же воно характеризувалося функцією з натуральним аргументом, для якої існує алгоритм обчислення. Одним з досягнень Алана Тюрінга було уявлення формально точного предиката, за допомогою якого можна було б замінити неформальний, якщо використовувати умова ефективності методу. Черч зробив те ж саме відкриття.
