Teza Kościoła-Turinga - Church–Turing thesis

W teorii obliczalności The Hipoteza Churcha-Turinga (znany również jako tezy obliczalności The tezy Turinga-Church The przypuszczenie Kościół-Turinga , praca Kościoła , przypuszczenie Kościoła , a tezy Turinga ) jest hipoteza o naturze funkcji obliczalnych . Stwierdza, że funkcja na liczbach naturalnych może być obliczona metodą efektywną wtedy i tylko wtedy, gdy jest obliczana przez maszynę Turinga . Praca nosi imię amerykańskiego matematyka Alonzo Churcha i brytyjskiego matematyka Alana Turinga . Przed dokładną definicją funkcji obliczalnej matematycy często używali nieformalnego terminu skutecznie obliczalnego, aby opisać funkcje obliczalne metodami papieru i ołówka. W latach trzydziestych podjęto kilka niezależnych prób sformalizowania pojęcia obliczalności :

  • W 1933 Kurt Gödel wraz z Jacquesem Herbrandem sformalizował definicję klasy ogólnych funkcji rekurencyjnych : najmniejszą klasę funkcji (z dowolnie wieloma argumentami), która jest zamknięta w ramach składu , rekurencji i minimalizacji i zawiera zero , następcę i wszystkie projekcje .
  • W 1936 roku Alonzo Church stworzył metodę definiowania funkcji zwaną rachunkiem λ . W rachunku λ zdefiniował kodowanie liczb naturalnych, zwane cyframi kościelnymi . Funkcja na liczbach naturalnych nazywana jest obliczalną λ, jeśli odpowiadającą jej funkcję na liczbach Churcha można przedstawić za pomocą wyrazu z rachunku λ.
  • Również w 1936 roku, przed zapoznaniem się z pracą Churcha, Alan Turing stworzył teoretyczny model maszyn, obecnie nazywanych maszynami Turinga, które mogły przeprowadzać obliczenia na podstawie danych wejściowych, manipulując symbolami na taśmie. Biorąc pod uwagę odpowiednie kodowanie liczb naturalnych jako sekwencji symboli, funkcja na liczbach naturalnych nazywa się obliczalną Turinga, jeśli jakaś maszyna Turinga oblicza odpowiednią funkcję na zakodowanych liczbach naturalnych.

Church, Kleene i Turing dowiedli, że te trzy formalnie zdefiniowane klasy funkcji obliczalnych pokrywają się: funkcja jest obliczalna λ wtedy i tylko wtedy, gdy jest obliczalna według Turinga i wtedy i tylko wtedy, gdy jest ogólnie rekurencyjna . To doprowadziło matematyków i informatyków do przekonania, że ​​pojęcie obliczalności jest dokładnie scharakteryzowane przez te trzy równoważne procesy. Inne formalne próby scharakteryzowania obliczalności później wzmocniły to przekonanie (patrz poniżej ).

Z drugiej strony teza Churcha-Turinga stwierdza, że ​​powyższe trzy formalnie zdefiniowane klasy funkcji obliczalnych pokrywają się z nieformalnym pojęciem funkcji efektywnie obliczalnej. Chociaż teza ta cieszy się niemal powszechną akceptacją, nie można jej formalnie udowodnić, ponieważ pojęcie efektywnej kalkulacji jest zdefiniowane tylko nieformalnie.

Od momentu powstania pojawiły się wariacje na temat pierwotnej tezy, w tym stwierdzenia o tym, co może fizycznie zrealizować komputer w naszym wszechświecie ( fizyczna teza Churcha-Turinga ), a co można skutecznie obliczyć ( teza Churcha-Turinga (teoria złożoności) ). Te różnice nie są spowodowane przez Churcha czy Turinga, ale wynikają z późniejszych prac nad teorią złożoności i fizyką cyfrową . Teza ma również implikacje dla filozofii umysłu (patrz niżej ).

Oświadczenie w słowach Churcha i Turinga

JB Rosser  ( 1939 ) odnosi się do pojęcia „efektywnej obliczalności” w następujący sposób: „Oczywiście istnienie CC i RC (dowody Churcha i Rossera) zakłada dokładną definicję „efektywnej”. sens metody, której każdy krok jest dokładnie z góry określony i która z pewnością przyniesie odpowiedź w skończonej liczbie kroków”. Tak więc przysłówek-przymiotnik „skuteczny” jest używany w znaczeniu „1a: wywołujący zdecydowany, decydujący lub pożądany efekt” i „zdolny do wytworzenia rezultatu”.

W dalszej części słowa „skutecznie obliczalne” będą oznaczać „wyprodukowane za pomocą jakichkolwiek intuicyjnie „skutecznych” środków”, a „skutecznie obliczalne” będą oznaczać „wyprodukowane przez maszynę Turinga lub równoważne urządzenie mechaniczne”. „Definicje” Turinga podane w przypisie w jego doktoracie z 1938 r. Teza Systemy logiki oparte na porządkach , nadzorowane przez Kościół, są praktycznie takie same:

Będziemy używać wyrażenia „funkcja obliczalna” w znaczeniu funkcji obliczalnej przez maszynę, a „efektywnie obliczalna” odnosi się do idei intuicyjnej bez szczególnego utożsamiania się z którąkolwiek z tych definicji.

Tezę można sformułować następująco: Każda efektywnie obliczalna funkcja jest funkcją obliczalną . Church stwierdził również, że „żadna procedura obliczeniowa nie będzie uważana za algorytm, chyba że można ją przedstawić jako maszynę Turinga”. Turing stwierdził to w ten sposób:

Stwierdzono ..., że "funkcja jest skutecznie obliczalna, jeśli jej wartości można znaleźć za pomocą jakiegoś czysto mechanicznego procesu". Możemy wziąć to dosłownie, rozumiejąc, że poprzez czysto mechaniczny proces, który może być wykonany przez maszynę. Rozwój ... prowadzi do ... utożsamienia obliczalności ze skuteczną obliczalnością. [ to przypis cytowany powyżej.]

Historia

Jednym z istotnych problemów dla logików w 1930 roku był Entscheidungsproblem od Davida Hilberta i Wilhelm Ackermann , który zapytał, czy istnieje procedura mechanicznego oddzielania prawdy od fałszu matematyczne matematycznych. To poszukiwanie wymagało sprecyzowania pojęcia „algorytmu” lub „skutecznej kalkulacji”, przynajmniej na tyle dobrze, aby poszukiwanie mogło się rozpocząć. Ale od samego początku próby Alonzo Churcha rozpoczęły się debatą, która trwa do dziś. Czy pojęcie „skutecznej obliczalności” miało być (i) „aksjomatem lub aksjomatami” w systemie aksjomatycznym, (ii) jedynie definicją, która „zidentyfikowała” dwa lub więcej twierdzeń, (iii) hipotezą empiryczną, którą należy zweryfikować przez obserwację zdarzeń naturalnych, lub (iv) po prostu propozycja dla argumentacji (tj. "teza").

Około 1930–1952

W trakcie badania tego problemu Church i jego uczeń Stephen Kleene wprowadzili pojęcie funkcji λ-definiowalnych i byli w stanie udowodnić, że kilka dużych klas funkcji często spotykanych w teorii liczb jest λ-definiowalnych. Debata rozpoczęła się, gdy Church zaproponował Gödelowi, że należy zdefiniować funkcje „efektywnie obliczalne” jako funkcje definiowalne przez λ. Gödel nie był jednak przekonany i nazwał tę propozycję „całkowicie niezadowalającą”. Raczej, w korespondencji z Churchem (ok. 1934-35), Gödel zaproponował aksjomatyzację pojęcia „skutecznej kalkulacji”; rzeczywiście, w liście do Kleene z 1935 roku Church donosił, że:

Jedyną jego [Gödla] ówczesną ideą było to, że możliwe byłoby, w kategoriach efektywnej obliczalności jako pojęcia nieokreślonego, sformułowanie zbioru aksjomatów, które zawierałyby ogólnie przyjęte własności tego pojęcia i zrobienie czegoś na tej podstawie. .

Ale Gödel nie zaoferował dalszych wskazówek. W końcu zasugerowałby swoją rekurencję, zmodyfikowaną przez sugestię Herbranda, którą Gödel szczegółowo opisał w swoich wykładach w Princeton w 1934 r. (Kleene i Rosser dokonali transkrypcji notatek). Nie sądził jednak, że te dwie idee można zadowalająco zidentyfikować „z wyjątkiem heurystyki”.

Następnie konieczne było zidentyfikowanie i udowodnienie równoważności dwóch pojęć efektywnej obliczalności. Wyposażony w rachunek λ i „ogólną” rekurencję, Stephen Kleene z pomocą Churcha i J. Barkley Rossera przedstawił dowody (1933, 1935), aby wykazać, że te dwa rachunki są równoważne. Church następnie zmodyfikował swoje metody, aby uwzględnić użycie rekurencji Herbranda-Gödla, a następnie udowodnił (1936), że problem Entscheidungs jest nierozwiązywalny: nie ma algorytmu, który mógłby określić, czy dobrze uformowana formuła ma „postać normalną”.

Wiele lat później w liście do Davisa (ok. 1965) Gödel powiedział, że „w czasie tych [1934] wykładów wcale nie był przekonany, że jego koncepcja rekurencji obejmuje wszystkie możliwe rekurencje”. W latach 1963-64 Gödel wypierałby się rekurencji Herbranda-Gödla i rachunku λ na rzecz maszyny Turinga jako definicji „algorytmu” lub „procedury mechanicznej” lub „systemu formalnego”.

Hipoteza prowadząca do prawa naturalnego? : Pod koniec 1936 roku artykuł Alana Turinga (dowodzący również, że Entscheidungsproblem jest nierozwiązywalny) został dostarczony ustnie, ale nie ukazał się jeszcze w druku. Z drugiej strony gazeta Emila Posta z 1936 roku ukazała się i została poświadczona niezależnie od pracy Turinga. Post zdecydowanie nie zgodził się z „identyfikacją” Churcha efektywnej obliczalności za pomocą rachunku λ i rekurencji, stwierdzając:

W rzeczywistości praca już wykonana przez Kościół i innych przenosi tę identyfikację znacznie poza etap hipotezy roboczej. Ale zamaskowanie tej identyfikacji pod definicją… przesłania nam potrzebę jej nieustannej weryfikacji.

Uważał raczej pojęcie „efektywnej kalkulacji” jedynie za „hipotezę roboczą”, która może prowadzić przez rozumowanie indukcyjne do „ prawa naturalnego ”, a nie przez „definicję lub aksjomat”. Pomysł ten został „ostro” skrytykowany przez Kościół.

W ten sposób Post w swoim artykule z 1936 r. również dyskontował sugestię Kurta Gödla dla Kościoła w latach 1934-35, że tezę można wyrazić jako aksjomat lub zbiór aksjomatów.

Turing dodaje kolejną definicję, Rosser zrównuje wszystkie trzy : w krótkim czasie ukazał się artykuł Turinga z lat 1936-37 „O liczbach obliczalnych, z zastosowaniem do Entscheidungsproblem”. W nim przedstawił inne pojęcie „efektywnej obliczalności” wraz z wprowadzeniem swoich maszyn a (obecnie znanych jako abstrakcyjny model obliczeniowy maszyny Turinga ). A w szkicu dowodowym dodanym jako „dodatek” do jego pracy z lat 1936-37, Turing wykazał, że klasy funkcji zdefiniowane przez rachunek λ i maszyny Turinga pokrywają się. Church szybko zorientował się, jak przekonująca była analiza Turinga. W swojej recenzji artykułu Turinga wyjaśnił, że pojęcie Turinga uczyniło „identyfikację ze skutecznością w zwykłym (nie wyraźnie zdefiniowanym) sensie natychmiast ewidentną”.

Za kilka lat (1939) Turing zaproponował, podobnie jak Church i Kleene przed nim, że jego formalna definicja mechanicznego agenta obliczeniowego jest poprawna. Tak więc do roku 1939 zarówno Church (1934), jak i Turing (1939) indywidualnie zaproponowali, aby ich „systemy formalne” były definicjami „efektywnej obliczalności”; żaden z nich nie sformułował swoich twierdzeń jako tezy .

Rosser (1939) formalnie zidentyfikował trzy pojęcia-definicje:

Wszystkie trzy definicje są równoważne, więc nie ma znaczenia, która z nich zostanie użyta.

Kleene proponuje Tezę I : Pozostawiło to Kleene'owi jawne wyrażenie „tezy”. W 1943 Kleene zaproponował swoją „TEZĘ I”:

Ten heurystyczny fakt [ogólne funkcje rekurencyjne można skutecznie obliczyć] ... skłonił Churcha do sformułowania następującej tezy. Ta sama teza jest zawarta w opisie maszyn liczących Turinga.

TEZA I. Każda efektywnie obliczalna funkcja (efektywnie rozstrzygalny predykat) jest generalnie rekurencyjna [kursywa Kleene'a]

Ponieważ brakuje precyzyjnej matematycznej definicji terminu skutecznie obliczalnego (skutecznie rozstrzygalnego), możemy przyjąć tę tezę ... jako jej definicję ...

...teza ma charakter hipotezy – punkt podkreślany przez Posta i Churcha. Jeśli uznamy tezę i jej odwrotność za definicję, to hipoteza jest hipotezą o zastosowaniu teorii matematycznej rozwiniętej z definicji. Dla przyjęcia hipotezy istnieją, jak sugerowaliśmy, całkiem przekonujące podstawy.

Teza Kościoła-Turinga : Stephen Kleene, we Wstępie do metamatematyki , w końcu formalnie nazywa „Tezę Kościoła” i „Tezę Turinga”, używając swojej teorii rekurencyjnej realizacji. Kleene przeszedł od prezentacji swojej pracy w terminologii definiowania lambda Church-Kleene'a do rekurencyjności Gödla-Kleene'a (częściowe funkcje rekurencyjne). W tym przejściu Kleene zmodyfikował ogólne funkcje rekurencyjne Gödla, aby umożliwić dowody nierozwiązywalności problemów w intuicjonizmie EJ Brouwera. W jego podyplomowym podręczniku logiki wprowadza się „tezę Kościoła” i okazuje się, że podstawowe wyniki matematyczne są niewykonalne. Następnie Kleene przystępuje do przedstawienia „tezy Turinga”, w której wyniki okazały się nieobliczalne, wykorzystując uproszczone wyprowadzenie maszyny Turinga na podstawie pracy Emila Posta. Obie tezy są udowodnione jako równoważne za pomocą „Twierdzenia XXX”.

Teza I. Każda efektywnie obliczalna funkcja (efektywnie rozstrzygalny predykat) jest generalnie rekurencyjna .

Twierdzenie XXX: Następujące klasy funkcji częściowych są korozległe, tj. mają te same elementy: (a) częściowe funkcje rekurencyjne, (b) funkcje obliczalne ...

Teza Turinga: Teza Turinga, że ​​każda funkcja, która naturalnie byłaby uważana za obliczalną, jest obliczalna według jego definicji, tj. przez jedną z jego maszyn, jest równoważna tezie Churcha z Twierdzenia XXX.

Kleene w końcu po raz pierwszy używa terminu „teza Kościoła Turinga” w części, w której pomaga wyjaśnić pojęcia z pracy Alana Turinga „The Word Problem in Semi-Groups with Cancellation”, zgodnie z wymaganiami krytyka Williama Boone'a.

Późniejsze wydarzenia

Próba lepszego zrozumienia pojęcia „efektywnej obliczalności” skłoniła Robina Gandy'ego (ucznia i przyjaciela Turinga) w 1980 roku do analizy obliczeń maszynowych (w przeciwieństwie do obliczeń wykonywanych przez człowieka przez maszynę Turinga). Ciekawość i analiza automatów komórkowych (w tym gry w życie Conwaya ), paralelizmów i automatów krystalicznych doprowadziły Gandy'ego do zaproponowania czterech „zasad (lub ograniczeń)… które, jak twierdzi, musi spełniać każda maszyna”. Jego najważniejsza czwarta, „zasada przyczynowości” opiera się na „skończonej prędkości propagacji efektów i sygnałów; współczesna fizyka odrzuca możliwość natychmiastowego działania na odległość”. Z tych zasad i pewnych dodatkowych ograniczeń: (1a) dolne ograniczenie liniowych wymiarów którejkolwiek z części, (1b) górne ograniczenie prędkości propagacji (prędkości światła), (2) dyskretny postęp maszyny, oraz (3) zachowanie deterministyczne – tworzy twierdzenie, że „to, co można obliczyć za pomocą urządzenia spełniającego zasady I–IV, jest obliczalne”.

Pod koniec lat 90. Wilfried Sieg przeanalizował pojęcia „efektywnej kalkulacji” Turinga i Gandy'ego z zamiarem „wyostrzenia nieformalnego pojęcia, sformułowania jego ogólnych cech w sposób aksjomatyczny i zbadania ram aksjomatycznych”. W swojej pracy z 1997 i 2002 roku Sieg przedstawia szereg ograniczeń dotyczących zachowania komputera — „ludzkiego agenta komputerowego, który postępuje mechanicznie”. Te ograniczenia ograniczają się do:

  • „(B.1) (Ograniczenie) Istnieje stałe ograniczenie liczby konfiguracji symbolicznych, które komputer może natychmiast rozpoznać.
  • „(B.2) (Boundedness) Istnieje stałe ograniczenie liczby stanów wewnętrznych, w jakich może znajdować się komputer.
  • „(L.1) (Lokalność) Komputer może zmieniać tylko elementy obserwowanej konfiguracji symbolicznej.
  • „(L.2) (Lokalność) Komputer może przenosić uwagę z jednej symbolicznej konfiguracji na inną, ale nowe obserwowane konfiguracje muszą znajdować się w ograniczonej odległości od bezpośrednio obserwowanej konfiguracji.
  • „(D) (Określenie) Natychmiast rozpoznawalna (pod)konfiguracja jednoznacznie określa następny krok obliczeń (i id [bezzwłoczny opis])”; stwierdził w inny sposób: „Wewnętrzny stan komputera wraz z obserwowaną konfiguracją ustala jednoznacznie kolejny krok obliczeniowy i następny stan wewnętrzny”.

Sprawa pozostaje przedmiotem aktywnej dyskusji w środowisku akademickim.

Teza jako definicja

Tezę można traktować jako zwykłą matematyczną definicję. Komentarze Gödla na ten temat sugerują ten pogląd, np. „prawidłowa definicja mechanicznej obliczalności została ustalona ponad wszelką wątpliwość przez Turinga”. Argument za postrzeganiem tezy jako nic więcej niż definicji jest wyraźnie sformułowany przez Roberta I. Soare'a , w którym twierdzi się również, że definicja obliczalności Turinga jest nie mniej poprawna niż definicja epsilon-delta funkcji ciągłej .

Sukces pracy magisterskiej

Inne formalizmy (oprócz rekurencji, rachunku λ i maszyny Turinga ) zostały zaproponowane do opisu efektywnej obliczalności/obliczalności. Stephen Kleene (1952) dodaje do listy funkcji " zaliczalne w systemie S 1 " od Kurt Gödel 1936, a Emil posta (1943, 1946) "„s kanonicznych [zwanych również normalnych ] systemów ". W latach pięćdziesiątych Hao Wang i Martin Davis znacznie uprościli jednotaśmowy model maszyny Turinga (patrz maszyna Post-Turinga ). Marvin Minsky rozszerzył model do dwóch lub więcej taśm i znacznie uprościł taśmy do „liczników góra-dół”, które Melzak i Lambek rozwinęli dalej w to, co jest obecnie znane jako model maszyny licznikowej . Pod koniec lat 60. i na początku lat 70. badacze rozszerzyli model maszyny liczącej na maszynę rejestrującą , bliską kuzynkę nowoczesnego pojęcia komputera . Inne modele obejmują logikę kombinacyjną i algorytmy Markowa . Gurevich dodaje model maszyny wskaźnikowej Kołmogorowa i Uspienskiego (1953, 1958): „… chcieli tylko… przekonać samych siebie, że nie ma sposobu na rozszerzenie pojęcia funkcji obliczalnej”.

Wszystkie te wkłady obejmują dowody, że modele są równoważne obliczeniowo z maszyną Turinga; takie modele są uważane za kompletne pod względem Turinga . Ponieważ wszystkie te różne próby sformalizowania pojęcia „efektywnej obliczalności/obliczalności” przyniosły równoważne rezultaty, obecnie przyjmuje się ogólnie, że teza Kościoła-Turinga jest poprawna. W rzeczywistości Gödel (1936) zaproponował coś silniejszego niż to; zauważył, że coś jest „absolutna” o pojęcie „zaliczalne w S 1 ”:

Może to również zostanie wykazane, że jest to funkcja, która obliczeniowy [ „zaliczalne”] W jednym z systemów S I , lub nawet w systemie typu pozaskończoną jest już obliczeniowy [zaliczalne] W S 1 . Zatem pojęcie „policzalny” [„obliczalny”] jest w pewnym określonym sensie „absolutny”, podczas gdy praktycznie wszystkie inne znane pojęcia metamatematyczne (np. dowodliwe, definiowalne itp.) zależą całkiem zasadniczo od systemu, w którym są zdefiniowane. .

Nieformalne użycie w dowodach

Dowody w teorii obliczalności często odwołują się do tezy Churcha-Turinga w sposób nieformalny, aby ustalić obliczalność funkcji, unikając (często bardzo długich) szczegółów, które byłyby zaangażowane w rygorystyczny, formalny dowód. Aby ustalić, że funkcja jest obliczalna przez maszynę Turinga, zwykle uważa się, że wystarczy podać nieformalny angielski opis, w jaki sposób można skutecznie obliczyć funkcję, a następnie stwierdzić „według tezy Churcha-Turinga”, że funkcja jest obliczalna przez Turinga (równoważnie , częściowa rekurencyjna).

Dirk van Dalen podaje następujący przykład, aby zilustrować to nieformalne wykorzystanie tezy Kościoła-Turinga:

PRZYKŁAD: Każdy nieskończony zbiór RE zawiera nieskończony zbiór rekurencyjny .

Dowód: Niech A będzie nieskończone RE. Wymieniamy elementy A efektywnie, n 0 , n 1 , n 2 , n 3 , ...

Z tej listy wyciągamy rosnącą podlistę: umieść m 0 =n 0 , po skończonych wielu krokach znajdujemy n k takie, że n k > m 0 , umieść m 1 =n k . Powtarzamy tę procedurę, aby znaleźć m 2 > m 1 , itd. Daje to efektywne wyliczenie podzbioru B={m 0 ,m 1 ,m 2 ,...} z A o własności m i < m i+ 1 .

Roszczenie . B jest rozstrzygalne. Aby przetestować k w B, musimy sprawdzić, czy k=m i dla jakiegoś i. Ponieważ ciąg m i 's rośnie, musimy wyprodukować co najwyżej k+1 elementów listy i porównać je z k. Jeśli żaden z nich nie jest równy k, to k nie jest w B. Ponieważ ten test jest skuteczny, B jest rozstrzygalne i, zgodnie z tezą Churcha , rekurencyjne.

Aby powyższy przykład był całkowicie rygorystyczny, należałoby starannie skonstruować maszynę Turinga, czyli funkcję λ, albo ostrożnie przywołać aksjomaty rekurencji, albo w najlepszym razie sprytnie przywołać różne twierdzenia teorii obliczalności. Ale ponieważ teoretyk obliczalności uważa, że ​​obliczalność Turinga poprawnie ujmuje to, co można skutecznie obliczyć, i ponieważ skuteczna procedura jest napisana w języku angielskim w celu decydowania o zbiorze B, teoretyk obliczalności przyjmuje to jako dowód, że zbiór jest rzeczywiście rekurencyjny.

Wariacje

Powodzenie tezy Kościoła Turinga skłoniło do zaproponowania wariantów tej tezy. Na przykład fizyczna teza Churcha-Turinga stwierdza: „Wszystkie fizycznie obliczalne funkcje są obliczalne według Turinga”.

Teza Churcha-Turinga nie mówi nic o skuteczności, z jaką jeden model obliczeniowy może symulować inny. Udowodniono na przykład, że (wielotaśmowa) uniwersalna maszyna Turinga ma tylko logarytmiczny czynnik spowolnienia w symulowaniu dowolnej maszyny Turinga.

Odmiana tezy Churcha-Turinga dotyczy tego, czy można skutecznie symulować arbitralny, ale „rozsądny” model obliczeń. Nazywa się to tezą wykonalności , znaną również jako ( klasyczna ) teoria złożoności Church-Turinga lub rozszerzona teza Churcha-Turinga , która nie jest spowodowana przez Churcha czy Turinga, ale jest realizowana stopniowo w rozwoju teorii złożoności . Stwierdza: „ Probabilistyczna maszyna Turinga może wydajnie symulować dowolny realistyczny model obliczeniowy”. Słowo „efektywnie” oznacza tu do redukcji wielomianowej . Teza ta została pierwotnie nazwana teorią złożoności obliczeniowej Kościoła-Turinga przez Ethana Bernsteina i Umesha Vazirani (1997). Teoria teorii złożoności Churcha-Turinga zakłada zatem, że wszystkie „rozsądne” modele obliczeń dają tę samą klasę problemów, które można obliczyć w czasie wielomianowym. Zakładając przypuszczenie, że czas wielomianu probabilistycznego ( BPP ) równa się czasowi wielomianu deterministycznemu ( P ), słowo „probabilistyczny” jest opcjonalne w tezie Kościoła-Turinga opartej na teorii złożoności. Podobną tezę, zwaną tezą o niezmienności , postawili Cees F. Slot i Peter van Emde Boas. Stwierdza: „Rozsądne” maszyny mogą symulować się nawzajem w ramach narzutu ograniczonego wielomianem w czasie i narzutu o stałym współczynniku w przestrzeni”. Teza pierwotnie pojawiła się w artykule w STOC '84, który był pierwszym artykułem, w którym wykazano, że narzut w czasie wielomianowym i narzut w przestrzeni stałej można jednocześnie osiągnąć dla symulacji maszyny o dostępie swobodnym na maszynie Turinga.

Gdyby okazało się, że BQP jest ścisłym nadzbiorem BPP , unieważniłoby to teorię złożoności Kościoła Turinga. Innymi słowy, istniałyby wydajne algorytmy kwantowe, które wykonują zadania, które nie mają wydajnych algorytmów probabilistycznych . Nie unieważniłoby to jednak oryginalnej tezy Churcha-Turinga, ponieważ komputer kwantowy może zawsze być symulowany przez maszynę Turinga, ale unieważniłoby klasyczną teorię Churcha-Turinga oparte na teorii złożoności ze względu na wydajność. W związku z tym teoria Kościoła Turinga dotycząca teorii złożoności kwantowej stwierdza: „ Kwantowa maszyna Turinga może skutecznie symulować dowolny realistyczny model obliczeniowy”.

Eugene Eberbach i Peter Wegner twierdzą, że teza Churcha-Turinga jest czasami interpretowana zbyt szeroko, twierdząc, że „Chociaż [...] maszyny Turinga wyrażają zachowanie algorytmów, szersze twierdzenie, że algorytmy precyzyjnie wychwytują to, co można obliczyć, jest nieważne”. Twierdzą oni, że formy obliczeń nieujęte w tezie są dziś aktualne, terminy, które nazywają obliczeniami superturingowymi .

Implikacje filozoficzne

Filozofowie zinterpretowali tezę Kościoła Turinga jako mającą implikacje dla filozofii umysłu . B. Jack Copeland stwierdza, że ​​kwestią empiryczną jest otwarte pytanie, czy istnieją rzeczywiste deterministyczne procesy fizyczne, które na dłuższą metę wymykają się symulacji przez maszynę Turinga; ponadto stwierdza, że ​​kwestią otwartą empirycznie jest to, czy jakiekolwiek takie procesy są zaangażowane w pracę ludzkiego mózgu. Jest też kilka ważnych pytań otwartych, które dotyczą relacji między tezą Kościoła–Turinga a fizyką oraz możliwości hiperobliczeń . W odniesieniu do fizyki teza ma kilka możliwych znaczeń:

  1. Wszechświat jest odpowiednikiem maszyny Turinga; tak więc obliczanie funkcji nierekurencyjnych jest fizycznie niemożliwe. Zostało to nazwane silną tezą Kościoła-Turinga lub zasadą Kościoła-Turinga-Deutscha i jest podstawą fizyki cyfrowej .
  2. Wszechświat nie jest odpowiednikiem maszyny Turinga (tj. prawa fizyki nie są obliczalne według Turinga), ale nieobliczalne zdarzenia fizyczne nie są „nadające się do wykorzystania” do budowy hiperkomputera . Na przykład wszechświat, w którym fizyka obejmuje losowe liczby rzeczywiste , w przeciwieństwie do obliczalnych liczb rzeczywistych , należy do tej kategorii.
  3. Wszechświat jest hiperkomputerem i możliwe jest zbudowanie urządzeń fizycznych, które wykorzystują tę właściwość i obliczają funkcje nierekurencyjne. Na przykład kwestią otwartą jest, czy wszystkie zdarzenia mechaniki kwantowej są obliczalne według Turinga, chociaż wiadomo, że rygorystyczne modele, takie jak kwantowe maszyny Turinga, są równoważne z deterministycznymi maszynami Turinga. (Niekoniecznie są one wydajnie równoważne; patrz wyżej). John Lucas i Roger Penrose zasugerowali, że ludzki umysł może być wynikiem jakiegoś rodzaju wzmocnionych kwantowo-mechanicznie, „niealgorytmicznych” obliczeń.

Istnieje wiele innych technicznych możliwości, które wykraczają poza te trzy kategorie lub mieszczą się pomiędzy tymi trzema kategoriami, ale służą one do zilustrowania zakresu koncepcji.

Filozoficzne aspekty pracy, dotyczące zarówno komputerów fizycznych, jak i biologicznych, zostały również omówione w podręczniku Odifreddiego z 1989 r. dotyczącym teorii rekurencji.

Funkcje nieobliczalne

Można formalnie zdefiniować funkcje, które nie są obliczalne. Dobrze znanym przykładem takiej funkcji jest funkcja Busy Beaver . Ta funkcja pobiera dane wejściowe n i zwraca największą liczbę symboli, jaką maszyna Turinga z n stanami może wydrukować przed zatrzymaniem, gdy jest uruchomiona bez danych wejściowych. Znalezienie górnej granicy dla zajętej funkcji bobra jest równoważne rozwiązaniu problemu zatrzymania , problemu znanego jako nierozwiązywalny przez maszyny Turinga. Ponieważ funkcja zajętego bobra nie może być obliczona przez maszyny Turinga, teza Churcha-Turinga stwierdza, że ​​funkcja ta nie może być skutecznie obliczona żadną metodą.

Kilka modeli obliczeniowych pozwala na obliczenie (Church-Turing) funkcji nieobliczalnych. Są one znane jako hiperkomputery . Mark Burgin twierdzi, że superrekurencyjne algorytmy, takie jak indukcyjne maszyny Turinga, obalają tezę Churcha-Turinga. Jego argumentacja opiera się na definicji algorytmu szerszej niż zwykła, tak że funkcje nieobliczalne uzyskane z niektórych indukcyjnych maszyn Turinga nazywamy obliczalnymi. Ta interpretacja tezy Churcha-Turinga różni się od interpretacji powszechnie przyjętej w teorii obliczalności, omówionej powyżej. Argument, że algorytmy superrekurencyjne są rzeczywiście algorytmami w rozumieniu tezy Churcha-Turinga, nie znalazł szerokiej akceptacji w środowisku badaczy obliczalności.

Zobacz też

Przypisy

Bibliografia

Zewnętrzne linki