Teza Churcha-Turinga odnosi się do koncepcji wydajnej, systematycznej lub mechanicznej metody w logice, matematyce i informatyce. Sformułowana jest jako opis intuicyjnej koncepcji obliczalności iw odniesieniu do ogólnych funkcji rekurencyjnych jest częściej nazywana tezą Churcha. Odwołuje się również do teorii funkcji obliczanych przez komputer. Teza pojawiła się w latach 30., kiedy same komputery jeszcze nie istniały. Został później nazwany na cześć amerykańskiego matematyka Alonso Churcha i jego brytyjskiego kolegi Alana Turinga.
Skuteczność metody do osiągnięcia wyniku
Pierwszym urządzeniem, które przypominało nowoczesny komputer, był Bombie, maszyna stworzona przez angielskiego matematyka Alana Turinga. Służył do odczytywania niemieckich wiadomości podczas II wojny światowej. Ale do swojej tezy i sformalizowania pojęcia algorytmu używał abstrakcyjnych maszyn, później nazwanych maszynami Turinga. Praca przedstawiazainteresowanie zarówno matematyków, jak i programistów, ponieważ ten pomysł zainspirował twórców pierwszych komputerów.
W teorii obliczalności teza Churcha-Turinga jest również znana jako przypuszczenie o naturze funkcji obliczalnych. Stwierdza, że dla każdej algorytmicznie obliczalnej funkcji na liczbach naturalnych istnieje maszyna Turinga zdolna do jej obliczenia. Innymi słowy, istnieje odpowiedni do tego algorytm. Dobrze znanym przykładem skuteczności tej metody jest test tabeli prawdy do testowania tautologii.
Sposób na osiągnięcie pożądanego rezultatu nazywa się „skutecznym”, „systematycznym” lub „mechanicznym”, jeśli:
- Metoda jest określona jako skończona liczba dokładnych instrukcji, każda instrukcja jest wyrażona przy użyciu skończonej liczby znaków.
- Będzie działał bez błędów, da pożądany rezultat w określonej liczbie kroków.
- Metoda może być wykonana przez człowieka bez pomocy jakiegokolwiek sprzętu innego niż papier i ołówek
- Nie wymaga zrozumienia, intuicji ani pomysłowości ze strony osoby wykonującej czynność
Wcześniej w matematyce nieformalny termin „efektywnie obliczalny” był używany w odniesieniu do funkcji, które można obliczyć za pomocą ołówka i papieru. Ale samo pojęcie obliczalności algorytmicznej było bardziej intuicyjne niż cokolwiek konkretnego. Teraz scharakteryzowano ją funkcją z argumentem naturalnym, dla której istnieje algorytm obliczeniowy. Jednym z osiągnięć Alana Turinga było:reprezentacja formalnie dokładnego predykatu, za pomocą którego możliwe byłoby zastąpienie nieformalnego predykatu, gdyby zastosowano warunek efektywności metody. Church dokonał tego samego odkrycia.
Podstawowe koncepcje funkcji rekurencyjnych
Zmiana predykatów Turinga na pierwszy rzut oka wyglądała inaczej niż ta, którą zaproponował jego kolega. Ale w rezultacie okazały się równoważne, w tym sensie, że każdy z nich wybiera ten sam zestaw funkcji matematycznych. Teza Churcha-Turinga to twierdzenie, że w zbiorze tym zawarta jest każda funkcja, której wartości można uzyskać metodą spełniającą warunki sprawności. Między tymi dwoma odkryciami była jeszcze jedna różnica. Chodziło o to, że Church rozważał tylko przykłady dodatnich liczb całkowitych, podczas gdy Turing opisał swoją pracę jako obejmującą funkcje obliczalne zmienną całkową lub rzeczywistą.
Powszechne funkcje rekurencyjne
Pierwotne sformułowanie Church'a mówi, że obliczenia można wykonać za pomocą rachunku λ. Jest to równoważne użyciu ogólnych funkcji rekurencyjnych. Teza Churcha-Turinga obejmuje więcej rodzajów obliczeń niż pierwotnie sądzono. Na przykład związane z automatami komórkowymi, kombinatorami, maszynami rejestrującymi i systemami substytucji. W 1933 roku matematycy Kurt Gödel i Jacques Herbrand stworzyli formalną definicję klasy zwanej ogólnymi funkcjami rekurencyjnymi. Używa funkcji, w których możliwy jest więcej niż jeden argument.
Tworzenie metodyRachunek λ
W 1936 r. Alonso Church stworzył metodę określania zwaną rachunkiem λ. Był kojarzony z liczbami naturalnymi. W ramach rachunku λ naukowiec określił ich kodowanie. W rezultacie nazywa się je numerami kościelnymi. Funkcję opartą na liczbach naturalnych nazwano obliczalną λ. Była inna definicja. Funkcja z tezy Churcha nazywana jest λ-obliczalną pod dwoma warunkami. Pierwsza brzmiała tak: jeśli została obliczona na elementach Kościoła, a drugim warunkiem była możliwość bycia reprezentowanym przez członka rachunku λ.
Również w 1936 roku, przed zapoznaniem się z pracą swojego kolegi, Turing stworzył model teoretyczny dla abstrakcyjnych maszyn nazwanych teraz jego imieniem. Mogli wykonywać obliczenia, manipulując znakami na taśmie. Dotyczy to również innych działań matematycznych występujących w informatyce teoretycznej, takich jak kwantowe obliczenia probabilistyczne. Funkcję z tezy Churcha dopiero później uzasadniono za pomocą maszyny Turinga. Początkowo opierali się na rachunku λ.
Obliczalność funkcji
Gdy liczby naturalne są odpowiednio zakodowane jako sekwencje znaków, mówi się, że funkcja na liczbach naturalnych jest obliczalna według Turinga, jeśli abstrakcyjna maszyna znalazła wymagany algorytm i wydrukowała tę funkcję na taśmie. Takie urządzenie, które w latach 30. nie istniało, w przyszłości będzie uważane za komputer. Abstrakcyjna maszyna Turinga i teza Kościoła zwiastowały erę rozwojuurządzenia komputerowe. Wykazano, że klasy funkcji formalnie zdefiniowane przez obu naukowców pokrywają się. W rezultacie oba stwierdzenia połączono w jedno. Funkcje obliczeniowe i teza Churcha miały również silny wpływ na koncepcję obliczalności. Stały się również ważnym narzędziem logiki matematycznej i teorii dowodu.
Uzasadnienie i problemy metody
Istnieją sprzeczne poglądy na temat pracy magisterskiej. Zebrano liczne dowody na „hipotezę roboczą” zaproponowaną przez Churcha i Turinga w 1936 roku. Jednak wszystkie znane metody lub operacje odkrywania nowych, efektywnie obliczalnych funkcji z danych, wiązały się z nieistniejącymi wówczas metodami budowy maszyn. Aby udowodnić tezę Churcha-Turinga, należy zacząć od tego, że każdy realistyczny model obliczeń jest równoważny.
Ze względu na różnorodność różnych analiz, jest to ogólnie uważane za szczególnie mocny dowód. Wszelkie próby dokładniejszego zdefiniowania intuicyjnego pojęcia funkcji efektywnie obliczalnej okazały się równoważne. Każda zaproponowana analiza okazała się wyróżniać tę samą klasę funkcji, a mianowicie te, które są obliczane przez maszyny Turinga. Ale niektóre modele obliczeniowe okazały się bardziej wydajne pod względem czasu i wykorzystania pamięci do różnych zadań. Później zauważono, że podstawowe koncepcje funkcji rekurencyjnych i teza Kościoła są raczej hipotetyczne.
Teza M
Ważne jest, aby odróżnić tezę Turinga od twierdzenia, że wszystko, co może zostać obliczone przez urządzenie obliczeniowe, może zostać obliczone przez jego maszynę. Druga opcja ma swoją własną definicję. Gandhi nazywa drugie zdanie „Tezą M”. Brzmi to tak: „Wszystko, co może obliczyć urządzenie, może zostać obliczone przez maszynę Turinga”. W wąskim sensie tezy jest to twierdzenie empiryczne, którego wartość prawdziwości jest nieznana. Teza Turinga i „Teza M” są czasami mylone. Druga wersja jest zasadniczo niepoprawna. Opisano różne maszyny warunkowe, które mogą obliczać funkcje, które nie są obliczalne przez Turinga. Należy zauważyć, że pierwsza teza nie pociąga za sobą drugiej, ale jest zgodna z jej fałszem.
Odwrotna implikacja tezy
W teorii obliczalności teza Churcha jest używana jako opis pojęcia obliczalności przez klasę ogólnych funkcji rekurencyjnych. Amerykanin Stephen Kleene podał bardziej ogólne sformułowanie. Nazwał częściowo rekurencyjne wszystkie częściowe funkcje obliczalne przez algorytmy.
Odwrotna implikacja jest powszechnie określana jako odwrócona teza Kościoła. Polega ona na tym, że każda funkcja rekurencyjna liczb całkowitych dodatnich jest efektywnie oceniana. W wąskim sensie teza po prostu oznacza taką możliwość. I w szerszym sensie, abstrahuje od pytania, czy ta warunkowa maszyna może w niej istnieć.
Komputery kwantowe
Koncepcje funkcji obliczalnych i teza Churcha stały się ważnym odkryciem dla matematyki, teorii maszyn i wielu innych nauk. Ale technologia bardzo się zmieniła i wciąż się poprawia. Zakłada się, że komputery kwantowe mogą wykonać wiele typowych zadań w krótszym czasie niż współczesne. Pozostają jednak pytania, takie jak problem zatrzymania. Komputer kwantowy nie może na nie odpowiedzieć. I, zgodnie z tezą Churcha-Turinga, nie ma też żadnego innego urządzenia komputerowego.
