Co to znaczy obalić tezę Turinga?

Przepraszam za chwytliwy tytuł. Chcę zrozumieć, co należy zrobić, aby obalić tezę Turinga? Gdzieś czytam, że jest to matematycznie niemożliwe! Dlaczego?

Turing, Rosser itp. Użyli różnych terminów, aby rozróżnić: „co można obliczyć” i „co można obliczyć za pomocą maszyny Turinga”.

Definicja Turinga z 1939 r. Jest następująca: „Użyjemy wyrażenia„ funkcja obliczalna ”, aby oznaczać funkcję obliczalną przez maszynę, i pozwalamy, aby„ efektywnie obliczalna ”odnosiła się do intuicyjnej idei bez szczególnego identyfikowania się z którąkolwiek z tych definicji”.

Tak więc tezę Turinga można sformułować w następujący sposób: Każda skutecznie obliczalna funkcja jest funkcją obliczalną.

Więc ponownie, jak będzie wyglądać dowód, jeśli ktoś obali tę hipotezę?

Teza Kościoła-Turinga została udowodniona do wszystkich praktycznych celów.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.146.5402

Dershowitz i Gurevich, Bulletin of Symbolic Logic, 2008.

(Odniesienie to omawia historię pracy Churcha i Turinga i argumentuje za oddzieleniem „tezy Kościoła” od „tezy Turinga” jako odrębnych logicznych twierdzeń, a następnie dowodzi ich obu w ramach intuicyjnej aksjatyzacji obliczalności.)

Jest pewna subtelna kwestia, o której rzadko wspominam w tego rodzaju dyskusjach i która moim zdaniem zasługuje na większą uwagę.

$f$$f$

$f$$f$$f$. OK, dobrze, ale teraz załóżmy, że budujemy hiperkomputer i pytamy go, czy maszyna Turinga, która szuka sprzeczności w ZFC, kiedykolwiek się zatrzyma. Załóżmy ponadto, że hiper-komputer odpowiada „Nie”. Co wnioskujemy? Czy dochodzimy do wniosku, że hiperkomputer „obliczył” spójność ZFC? Jak możemy wykluczyć możliwość, że ZFC jest niespójny i właśnie przeprowadziliśmy eksperyment, który sfałszował naszą teorię fizyczną?

Kluczową cechą definicji Turinga jest to, że jej założenia filozoficzne są bardzo słabe. Zakłada, oczywiście, musi, pewne proste cechy naszego codziennego doświadczenia, takie jak podstawowa stabilność świata fizycznego i zdolność do wykonywania skończonych operacji w niezawodny, powtarzalny i weryfikowalny sposób. Te rzeczy każdy akceptuje (to znaczy poza klasą filozofii!). Wydaje się jednak, że akceptacja hiperkomputera wymaga nieskończonej ekstrapolacjiteorii fizycznej, a całe nasze doświadczenie z fizyką nauczyło nas nie dogadać się z zasadnością teorii w reżimie, który wykracza daleko poza to, co możemy eksperymentalnie zweryfikować. Z tego powodu wydaje mi się wysoce nieprawdopodobne, że kiedykolwiek dojdzie do jakiegokolwiek przeważającego konsensusu, że jakikolwiek konkretny hiperkomputer jest po prostu komputerowy, a nie hiperkomputerowy , tj. Robi coś, co można nazwać „komputerowym”, tylko jeśli zaakceptujesz jakieś kontrowersyjne filozofie lub fizyczne założenia o nieskończonych ekstrapolacjach.

Innym sposobem jest to, że obalenie tezy Church-Turinga wymagałoby nie tylko zbudowania urządzenia, które opisuje Andrej, ale także udowodnienia wszystkim satysfakcji, że urządzenie działa zgodnie z reklamą. Chociaż nie jest to nie do pomyślenia, jest to duże zamówienie. W dzisiejszych komputerach skończona natura obliczeń oznacza, że ​​jeśli nie wierzę w wynik „obliczeń” określonego komputera, mogę w zasadzie przeprowadzić skończoną sekwencję kroków w zupełnie inny sposób, aby sprawdzić wynik. Ten rodzaj „powrotu do zdrowego rozsądku i skończonej weryfikacji” nie jest dostępny, jeśli mamy wątpliwości co do hiperkomputera.

Chociaż trudno jest udowodnić tezę Turinga ze względu na nieformalny charakter „skutecznie obliczalnej funkcji”, możemy sobie wyobrazić, co to znaczy obalić. Mianowicie, jeśli ktoś zbuduje urządzenie, które (niezawodnie) obliczy funkcję, której nie da się obliczyć żadną maszyną Turinga, obaliłoby tezę Churcha-Turinga, ponieważ ustaliłoby istnienie efektywnie obliczalnej funkcji, która nie byłaby obliczalna przez maszynę Turinga.

Obalenie tezy Kościoła-Turinga wydaje się rzeczywiście niezwykle mało prawdopodobne i koncepcyjnie bardzo trudne do wyobrażenia. Istnieją różne „hipotetyczne światy fizyczne”, które są w pewnym stopniu napięte z tezą Kościoła Turinga (ale to, czy same sobie przeczą, jest ciekawym pytaniem filozoficznym). Artykuł Pitowskiego „Thes the Physical Church's Thes and Physical Computational Complexity”, Iyun 39, 81-99 (1990) dotyczy takich hipotetycznych światów fizycznych. Zobacz także artykuł Itamar Pitowsky i Oron Shagrir: „Thes -Turing Thesis and Hyper Computation ”, Minds and Machines 13, 87-101 (2003). Oron Shagrir napisał kilka artykułów filozoficznych na temat tezy Kościoła Turinga na swojej stronie internetowej . (Zobacz także ten post na blogu .)

Skuteczna lub wydajna teza Church-Turinga jest nieskończenie silniejszym stwierdzeniem niż pierwotne twierdzenie Church-Turinga, które stwierdza, że ​​każde możliwe obliczenie może być skutecznie symulowane przez maszynę Turinga. Komputery kwantowe rzeczywiście pokażą, że efektywna teza Churcha-Turinga jest nieprawidłowa (modulo pewne domysły matematyczne o złożoności obliczeniowej, a modulo „interpretacja asymptotyczna”). Myślę, że skuteczna hipoteza Kościoła Turinga została sformułowana po raz pierwszy w 1985 r. Przez Wolframa, artykuł cytowany w artykule Pitowsky'ego powiązanym powyżej. W rzeczywistości nie potrzebujesz nawet uniwersalnych komputerów kwantowych, aby obalić efektywną tezę CT, a interesującą linią badań (między innymi badań Aaronsona) jest zaproponowanie możliwie najprostszej demonstracji przewagi obliczeniowej układów kwantowych.

Jest to również interesujący problem, jeśli istnieją prostsze sposoby wykazania wyższości obliczeniowej komputerów kwantowych w obecności szumu, zamiast posiadania pełnoprawnej kwantowej tolerancji na uszkodzenia (która umożliwia uniwersalne obliczenia kwantowe). (Scott A. jest rzeczywiście zainteresowany również tym problemem).

O ile rozumiem, „niemożność” udowodnienia lub obalenia tezy polega na tym, że nie ma formalnej definicji „skutecznie obliczalnej”. Dziś uważamy, że jest to dokładnie „obliczalne przez maszynę Turinga”, ale to raczej nasuwa pytanie.

Modele obliczeń, które są znacznie potężniejsze niż maszyna Turinga, zostały zbadane, spójrz na http://en.wikipedia.org/wiki/Hypercomputation na kilka przykładów. Lub po prostu weź maszynę Turinga z wyrocznią dla problemu zatrzymania maszyn Turinga. Taka maszyna będzie miała swój własny problem zatrzymania, ale może dobrze rozwiązać oryginalny problem zatrzymania. Oczywiście nie mamy takiej wyroczni, ale nie ma nic matematycznie niemożliwego w tym pomyśle.

Występy hiperkomputerów ogólnie zakładają ważność granicy Bekensteina, która określa szczególny limit ilości informacji, które może zawierać skończona ilość miejsca. Są pewne kontrowersje dotyczące tego ograniczenia, ale myślę, że większość fizyków to akceptuje.

Jeśli granica Bekensteina jest poważnie naruszona i nie ma ograniczenia co do ilości informacji zawartych w danym regionie (powiedzmy, czarnej dziury lub nieskończenie drobnego i solidnego grawerowania), i istnieją dowolnie dające się przewidzieć mechanizmy do badania zawartości tego region (powiedzmy, uważnie badając promieniowanie emitowane, gdy starannie skonstruowany przedmiot wpada do czarnej dziury lub przesuwając rysikiem po rowkach grawerowania), można przypuszczać, że akurat istnieje już artefakt, który koduje wyrocznię zatrzymującą .

Wszystko to jest bardzo mało prawdopodobne, ale pokazuje, że twierdzenie, że hiperkalkulacja jest niemożliwa, nie jest prawdą matematyczną, ale opiera się na fizyce. To znaczy, że Andrej ma rację, gdy mówi, że możemy sobie wyobrazić, co to znaczy obalić [tezę Kościoła-Turinga]. Mianowicie, jeśli ktoś zbudował urządzenie, które (niezawodnie) obliczyło funkcję, której nie może obliczyć żadna maszyna Turinga .

W odniesieniu do rozszerzonej tezy Church-Turinga (rozumianej jako „probabilistyczna maszyna Turinga może skutecznie symulować dowolną fizycznie obliczalną funkcję.”):

Jedną z możliwości jest różnica między komputerami klasycznymi a komputerami kwantowymi. W szczególności pytanie: „Czy istnieje zadanie, które komputery kwantowe mogą wykonać, czego nie potrafią komputery klasyczne?” Niedawny raport ECCC autorstwa Scotta Aaronsona (patrz Przypuszczenie 9 na stronie 5) podkreśla przypuszczenie, które, jeśli zostanie udowodnione, dostarczy mocnych dowodów przeciwko rozszerzonej tezie Kościoła-Turinga.

Gdyby ktoś obalił rozszerzoną tezę Kościoła-Turinga, mogłoby to wyglądać tak - w szczególności, poprzez wykazanie wydajnie obliczalnego zadania, którego (klasyczna) maszyna Turinga nie jest w stanie skutecznie obliczyć.

Nowy artykuł prezentowany na DCM2011 : Formalizacja i dowód rozszerzonej tezy kościelnej (Nachum Dershowitz i Evgenia Falkovich)

Następujące artykuły Selim Akl mogą być interesujące i istotne dla dyskusji:

Akl, SG, „Trzy kontrprzykłady dla obalenia mitu o uniwersalnym komputerze”, Parallel Processing Letters, t. 16, nr 3, wrzesień 2006, s. 381–403.

Akl, SG, „Nawet maszyny przyspieszające nie są uniwersalne”, International Journal of Unconventional Computing, tom. 3, nr 2, 2007, s. 105–121.

Nagy, M. i Akl, SG, „Równoległość w przetwarzaniu informacji kwantowej pokonuje komputer uniwersalny”, Listy przetwarzania równoległego, wydanie specjalne na temat niekonwencjonalnych problemów obliczeniowych, t. 17, nr 3, wrzesień 2007, s. 233–262.

Oto streszczenie pierwszego:

Pokazano, że koncepcja uniwersalnego komputera nie może zostać zrealizowana. W szczególności pokazano przykłady funkcji obliczalnej F, której nie można obliczyć na żadnej maszynie U, która jest w stanie wykonać tylko skończoną i stałą liczbę operacji na krok. Jest to prawdą, nawet jeśli maszyna U jest wyposażona w nieskończoną pamięć i zdolność do komunikowania się ze światem zewnętrznym podczas próby obliczenia F. Pozostaje to również prawdą, jeśli dodatkowo U ma się czas obliczeń na czas nieokreślony F. Wynik ten dotyczy nie tylko wyidealizowanych modeli obliczeniowych, takich jak Maszyna Turinga itp., Ale także wszystkich znanych komputerów ogólnego przeznaczenia, w tym istniejących komputerów konwencjonalnych (zarówno sekwencyjnych, jak i równoległych), a także rozważanych niekonwencjonalnych, takich jak jako komputery biologiczne i kwantowe.

Jak to może być prawda? Klasyczny komputer nie może skutecznie symulować komputera kwantowego. Istnieją algorytmy kwantowe, które zapewniają wykładnicze przyspieszenie w stosunku do klasycznych komputerów z klasycznymi algorytmami: jeden jest algorytm Shora.