Тезата на Чърч-Тюринг се отнася до концепцията за ефективен, систематичен или механичен метод в логиката, математиката и компютърните науки. Тя е формулирана като описание на интуитивната концепция за изчислимост и по отношение на общите рекурсивни функции по-често се нарича теза на Чърч. Също така се отнася до теорията на компютърно изчислимите функции. Тезата се появява през 30-те години на миналия век, когато самите компютри все още не са съществували. По-късно е кръстен на американския математик Алонсо Чърч и неговия британски колега Алън Тюринг.
Ефективност на метода за постигане на резултата
Първото устройство, което приличаше на модерен компютър, беше Bombie, машина, създадена от английския математик Алън Тюринг. Използван е за дешифриране на немски съобщения по време на Втората световна война. Но за своята теза и формализиране на концепцията за алгоритъм той използва абстрактни машини, наречени по-късно машини на Тюринг. Теза представяинтерес както за математиците, така и за програмистите, тъй като тази идея вдъхнови създателите на първите компютри.
В теорията на изчислимостта тезата на Чърч-Тюринг е известна още като предположението за природата на изчислимите функции. В него се посочва, че за всяка алгоритмично изчислима функция върху естествени числа има машина на Тюринг, способна да я изчисли. Или, с други думи, има алгоритъм, подходящ за това. Добре известен пример за ефективността на този метод е тестът с таблица на истинността за тестване на тавтология.
Начин за постигане на всеки желан резултат се нарича "ефективен", "систематичен" или "механичен", ако:
- Методът е определен по отношение на краен брой точни инструкции, всяка инструкция се изразява с краен брой знаци.
- Ще работи без грешки, ще доведе до желания резултат в определен брой стъпки.
- Методът може да се извърши от човек без чужда помощ с каквото и да е оборудване, различно от хартия и молив
- Не изисква разбиране, интуиция или изобретателност от страна на лицето, извършващо действието
По-рано в математиката неформалният термин "ефективно изчислим" беше използван за обозначаване на функции, които могат да бъдат изчислени с молив и хартия. Но самото понятие за алгоритмична изчислимост беше по-интуитивно от всичко конкретно. Сега се характеризираше с функция с естествен аргумент, за която има алгоритъм за изчисление. Едно от постиженията на Алън Тюринг бешепредставяне на формално точен предикат, с помощта на който би било възможно да се замени неформалният, ако се използва условието за ефективност на метода. Чърч направи същото откритие.
Основни понятия за рекурсивни функции
Промяната на предикатите на Тюринг на пръв поглед изглеждаше различно от тази, предложена от неговия колега. Но в резултат на това те се оказаха еквивалентни, в смисъл, че всеки от тях избира един и същ набор от математически функции. Тезата на Чърч-Тюринг е твърдението, че този набор съдържа всяка функция, чиито стойности могат да бъдат получени чрез метод, който удовлетворява условията за ефективност. Имаше още една разлика между двете открития. Чърч разглежда само примери за положителни числа, докато Тюринг описва работата си като покриване на изчислими функции с интегрална или реална променлива.
Общи рекурсивни функции
Оригиналната формулировка на Чърч гласи, че изчислението може да се извърши с помощта на λ-изчислението. Това е еквивалентно на използването на общи рекурсивни функции. Тезата на Чърч-Тюринг обхваща повече видове изчисления, отколкото се смяташе първоначално. Например свързани с клетъчни автомати, комбинатори, регистрационни машини и заместващи системи. През 1933 г. математиците Курт Гьодел и Жак Хербранд създават формална дефиниция на клас, наречен общи рекурсивни функции. Той използва функции, при които е възможен повече от един аргумент.
Създаване на методλ-изчисление
През 1936 г. Алонсо Чърч създава метод за определяне, наречен λ-изчисление. Той беше свързан с естествени числа. В рамките на λ-изчислението ученият определи тяхното кодиране. В резултат на това те се наричат църковни номера. Функция, базирана на естествени числа, се нарича λ-изчислима. Имаше и друго определение. Функцията от тезата на Чърч се нарича λ-изчислима при две условия. Първото звучеше така: ако беше изчислено върху църковни елементи, а второто условие беше възможността да бъде представен от член на λ-изчислението.
Също така през 1936 г., преди да изучава работата на своя колега, Тюринг създава теоретичен модел за абстрактните машини, които сега са кръстени на него. Те биха могли да извършват изчисления, като манипулират знаците на лентата. Това важи и за други математически дейности, открити в теоретичната компютърна наука, като квантово вероятностно изчисление. Функцията от тезата на Чърч едва по-късно беше обоснована с помощта на машина на Тюринг. Първоначално те разчитаха на λ-изчисление.
Изчислимост на функцията
Когато естествените числа са кодирани по подходящ начин като поредици от знаци, функция върху естествени числа се казва, че е изчислима по Тюринг, ако абстрактната машина намери необходимия алгоритъм и отпечата тази функция на лента. Такова устройство, което не е съществувало през 30-те години на миналия век, в бъдеще ще се счита за компютър. Абстрактната машина на Тюринг и тезата на Чърч предвещават ера на развитиеизчислителни устройства. Доказано е, че формално определените от двамата учени класове функции съвпадат. Следователно в резултат и двете твърдения бяха комбинирани в едно. Изчислителните функции и тезата на Чърч също оказаха силно влияние върху концепцията за изчислимостта. Те също така се превърнаха във важен инструмент за математическа логика и теория на доказателствата.
Обосновка и проблеми на метода
Има противоречиви възгледи относно тезата. Събрани са множество доказателства за "работната хипотеза", предложена от Чърч и Тюринг през 1936 г. Но всички известни методи или операции за откриване на нови ефективно изчислими функции от дадени бяха свързани с методи за изграждане на машини, които тогава не съществуваха. За да се докаже тезата на Чърч-Тюринг, се изхожда от факта, че всеки реалистичен модел на изчисление е еквивалентен.
Поради разнообразието от различни анализи, това обикновено се счита за особено силно доказателство. Всички опити за по-точно дефиниране на интуитивното понятие за ефективно изчислима функция се оказаха еквивалентни. Всеки предложен анализ е доказал, че отделя един и същ клас функции, а именно тези, които са изчислими от машини на Тюринг. Но някои изчислителни модели се оказаха по-ефективни по отношение на използването на време и памет за различни задачи. По-късно беше отбелязано, че основните концепции за рекурсивните функции и тезата на Чърч са по-скоро хипотетични.
Теза М
Важно е да се прави разлика между тезата на Тюринг и твърдението, че всичко, което може да бъде изчислено от изчислително устройство, може да бъде изчислено от неговата машина. Вторият вариант има свое собствено определение. Ганди нарича второто изречение "Теза М". Това гласи така: „Всичко, което може да бъде изчислено от устройство, може да бъде изчислено от машина на Тюринг.“В тесния смисъл на тезата това е емпирично твърдение, чиято истинност е неизвестна. Тезата на Тюринг и "Теза М" понякога се бъркат. Втората версия като цяло е неправилна. Описани са различни условни машини, които могат да изчисляват функции, които не са изчислими по Тюринг. Важно е да се отбележи, че първата теза не включва втората, но е в съответствие с нейната невярност.
Обратна импликация на тезата
В теорията на изчислимостта тезата на Чърч се използва като описание на понятието изчислимост от клас от общи рекурсивни функции. Американецът Стивън Клийн даде по-обща формулировка. Той нарече частично рекурсивни всички частични функции, изчислими чрез алгоритми.
Обратната импликация обикновено се нарича обратна теза на Чърч. Той се крие във факта, че всяка рекурсивна функция на положителни цели числа се оценява ефективно. В тесен смисъл тезата просто означава такава възможност. И в по-широк смисъл, той се абстрахира от въпроса дали тази условна машина може да съществува в нея.
Квантови компютри
Концепциите за изчислими функции и тезата на Чърч станаха важно откритие за математиката, теорията на машините и много други науки. Но технологиите се промениха много и продължават да се подобряват. Предполага се, че квантовите компютри могат да изпълняват много общи задачи с по-малко време от съвременните. Но остават въпроси, като например проблемът със спирането. Квантовият компютър не може да отговори. И според тезата на Чърч-Тюринг, нито едно друго изчислително устройство.
