Теза Черча-Тюрінга відноситься до поняття ефективного, систематичного або механічного методу в логіці, математиці та інформатиці. Він формулюється як опис інтуїтивного поняття обчислюваності і у відношенні до общерекурсивным функцій частіше називається тезою Черча. Він також відноситься до теорії вычислимых за допомогою комп’ютерів функцій. Теза з’явився в 1930-х роках, коли самих комп’ютерів ще не існувало. Пізніше він був названий на честь американського математика Алонзо Черча і його британського колеги Алана Тюрінга.
Ефективність методу досягнення результату
Першим пристроєм, що нагадував сучасний комп’ютер, була Bombie – машина, створена англійським математиком Аланом Тюрінгом. Вона використовувалася для розшифровки німецьких повідомлень під час Другої світової війни. Але для своєї тези і формалізації поняття алгоритму він використовував абстрактні машини, згодом названі машинами Тюрінга. Теза становить інтерес, як для математиків, так і для програмістів, так як ця ідея надихнула творців перших комп’ютерів.
В теорії обчислюваності теза Черча-Тюрінга також відомий як гіпотеза про природу вычислимых функцій. Він свідчить, що для будь-алгоритмічно обчислюваною функції на натуральних числах існує машина Тюрінга, здатна її обчислити. Або, іншими словами, є підходящий для неї алгоритм. Добре відомим прикладом ефективності цього методу є тест-таблиці істинності для перевірки тавтологичности.
Спосіб для досягнення якого-небудь бажаного результату називається «ефективною», «систематичним» або «механічним», якщо:
- Метод задається в термінах кінцевого числа точних команд, кожна інструкція виражається за допомогою кінцевого числа символів.
- Він буде виконуватися без помилок, призведе до бажаного результату через певне число кроків.
- Метод може виконуватися людиною без сторонньої допомоги будь-яким обладнанням, крім паперу й олівця
- Він не вимагає розуміння, інтуїції або винахідливості з боку людини, здійснює дії
Раніше в математиці використовувався неофіційний термін «ефективно вычислимый», щоб позначити функції, які можна обчислити за допомогою олівця і паперу. Але саме поняття алгоритмічної обчислюваності було швидше інтуїтивним, ніж чимось конкретним. Тепер же воно характеризувалося функцією з натуральним аргументом, для якої існує алгоритм обчислення. Одним з досягнень Алана Тюрінга було уявлення формально точного предиката, за допомогою якого можна було б замінити неформальний, якщо використовувати умова ефективності методу. Черч зробив те ж саме відкриття.
Основні поняття рекурсивних функцій
Заміна предикатів, запропонована Тюринг, на перший погляд виглядала відмінною від тієї, що запропонував його колега. Але в результаті вони виявилися еквівалентними, в тому сенсі, що кожен з них вибирає один і той же набір математичних функцій. Теза Черча-Тюрінга є твердженням, що це безліч містить кожну функцію, значення якої можуть бути отримані методом, що задовольняє умовам ефективності. Було ще одна відмінність цих двох відкриттів. Воно полягало в тому, що Черч розглядав тільки приклади додатних цілих чисел, тоді як Тьюринг описував свою роботу охоплює вычислимые функції з інтегральної або реальної змінної.
Загальні рекурсивні функції
У первісній формулюванні Черча говориться, що розрахунок може бути виконаний з використанням λ-числення. Це еквівалентно використанню загальних рекурсивних функцій. Теза Черча-Тюрінга охоплює більше видів обчислень, ніж ті, які спочатку передбачалися. Наприклад, пов’язані з клітинними автоматами, комбинаторами, реєстраційними машинами і системами заміщення. У 1933 році математики Курт Гедель і Жаком Хербранд створили формальне визначення класу, званого загальними рекурсивними функціями. Воно використовує функції, в яких можливий більш ніж один аргумент.
Створення методу λ-числення
У 1936 році Алонсо Черч створив метод визначення, званих λ-обчисленням. Він був пов’язаний з натуральними числами. Всередині λ-числення вчений визначив їх кодування. В результаті вони отримали назву чисел Черча. Функція на основі натуральних чисел називалася λ-обчислюваною. Було і інше визначення. Функція з тези Черча називається λ-обчислюваною за двох умов. Перше звучало так: якщо вона була розрахована на елементах Черча, а другою умовою була можливість подання членом λ-числення.
Також в 1936 році, перш ніж вивчати роботу свого колеги, Тюрінг створив теоретичну модель для абстрактних машин, тепер званих його ім’ям. Вони могли б виконувати обчислення шляхом маніпулювання символами на стрічці. Це також відноситься до іншим математичним діям, знайденим в теоретичної інформатики, таких як квантові імовірнісні обчислення. Функція з тези Черча тільки згодом була обґрунтована з застосуванням машини Тюрінга. Спочатку вони спиралися на λ-числення.
Вычислимость функції
При відповідному кодуванні натуральних чисел у вигляді послідовностей символів функція на натуральних чисел називається обчислюваною за версією Тюрінга, якщо абстрактна машина знаходила потрібний алгоритм і виводила цю функцію на стрічці. Подібне пристрій, якого не існувало в 1930-х, в майбутньому стали вважати комп’ютером. Абстрактна машина Тьюринга і теза Черча стали провісниками ери розвитку обчислювальних пристроїв. Було доведено, що формально визначені обома вченими класи функцій співпадають. Тому в результаті обидва твердження об’єднали в одну. Обчислювальні функції і теза Черча також надали сильний вплив на концепцію обчислюваності. А також стали важливою підмогою для математичної логіки і теорії доказів.
Обґрунтування та проблеми методу
Існують суперечливі точки зору на тезу. Численні докази були зібрані для «робочої гіпотези», запропонованої Черчем і Тюринг в 1936 році. Але всі відомі методи або операції для виявлення нових ефективно обчислюваних функцій заданих були пов’язані з методами побудови машин, яких тоді не існувало. Для того щоб довести теза Черча-Тюрінга, виходять з того факту, що кожна реалістична модель обчислень еквівалентна.
Із-за різноманітності різних аналізів, як правило, це вважається особливо переконливим доказом. Всі спроби більш точно визначити інтуїтивне поняття ефективно обчислюваної функції виявилися еквівалентними. Кожен запропонований аналіз довів, що він виділяє один і той же клас функцій, а саме ті, які вычислимы машинами Тюрінга. Але деякі обчислювальні моделі виявилися більш ефективні з точки зору часових витрат і використання пам’яті для різних завдань. Пізніше зазначалося, що основні поняття рекурсивних функцій і теза Черча є, швидше, гіпотетичними.
«Теза М»
Важливо розрізняти теза Тюрінга і твердження про те, що все, що може бути розраховано обчислювальним пристроєм, може бути розраховано його машиною. У другого варіанта є своє власне визначення. Ганді називає друге речення «Тезою М». Він звучить так: «Незалежно від того, що може бути обчислено пристроєм, можна обчислити машиною Тьюрінга». У вузькому розумінні тези, він є емпіричним пропозицією, истинностное значення якого невідоме. Теза Тюрінга і “Теза М” іноді плутають. Версія другого в широкому сенсі невірна. Були описані різні умовні машини, які можуть обчислювати функції, які не є вычислимыми по Тьюрингу. Важливо звернути увагу, що перша теза не тягне за собою другий, але узгоджується з його ложностью.
Зворотне имплицирование тези
В теорії обчислюваності теза Черча використовується як опис поняття обчислюваності класом общерекурсивных функцій. Американський Стівен Кліні дав більш загальне формулювання. Він назвав частково рекурсивними всі часткові функції, вычислимые за допомогою алгоритмів.
Зворотне имплицирование зазвичай називається зворотним тезою Черча. Він полягає в тому, що кожна рекурсивна функція позитивних цілих чисел ефективно обчислюється. У вузькому сенсі теза просто позначає таку можливість. А в широкому – абстрагується від питання про те, чи може існувати в ньому ця умовна машина.
Квантові комп’ютери
Поняття вычислимых функцій і теза Черча стали важливим відкриттям для математики, теорії машин та багатьох інших наук. Але техніка сильно змінилася і продовжує удосконалюватися. Передбачається, що квантові комп’ютери можуть виконувати безліч спільних завдань з меншими тимчасовими витратами в порівнянні з сучасними. Але залишаються такі питання, як проблема із зупинкою. На неї квантовий комп’ютер не може відповісти. І, відповідно тези Черча-Тюрінга, ніяке інше обчислювальне пристрій теж.
