Teoretyczne maszyny, które są mocniejsze niż maszyny Turinga

Czy są jakieś teoretyczne maszyny, które przekraczają możliwości maszyn Turinga w przynajmniej niektórych obszarach?

Teza Church-Turinga (w jednym sformułowaniu) stwierdza, że ​​wszystko, co można fizycznie obliczyć, można również obliczyć na maszynie Turinga. Zakładając, że wierzysz w te tezy i biorąc pod uwagę, że jesteś zainteresowany funkcjami, które takie maszyny mogłyby obliczyć (a nie, powiedzmy, w obliczeniach interaktywnych), to żadna hiperkalkulacja nie jest możliwa.

Teza Kościoła-Turinga dotyczy wyłącznie tego, co można obliczać, ale nie wydajności obliczeń. Wiadomo, że maszyny Turinga nie są tak wydajne, chociaż wielomianowo symulują klasyczne komputery. Uważa się, że komputery kwantowe są wykładniczo bardziej wydajne niż maszyny Turinga. W tym sensie możesz pokonać maszyny Turinga (jeśli tylko możesz zbudować skalowalny komputer kwantowy).

Scott Aaronson prawdopodobnie ma więcej do powiedzenia na ten temat - pozwolę ci to sprawdzić na własną rękę.

Tak, istnieją maszyny teoretyczne , które przewyższają maszyny Turinga pod względem mocy obliczeniowej, takie jak maszyny Oracle i maszyny Turinga z czasem nieskończonym . Modne hasło, które powinieneś przekazać Googleowi, to hiper-obliczenie .

Teza Kościoła-Turinga nie musi być traktowana jako artykuł wiary; prawdopodobnie bardziej sensowne jest uznanie go za opis, definicję tego , co rozumiemy przez pojęcie „obliczenia”, i jest to również dość wąskie pojęcie obliczeń: obliczenia przez pojedynczy procesor wykonujący kroki ściśle sekwencyjnie bez zewnętrznego ingerencja. Pewne aspekty obliczeń, które musimy uzasadnić, nie są objęte tym pojęciem, a wiele dodatkowych teorii matematycznych zostało opracowanych w dziedzinie informatyki w celu rozwiązania takich problemów.

Tak więc teza Kościoła-Turinga jest nie tyle charakterystyczną cechą naszego wszechświata, ale jest cechą charakterystyczną określonego sposobu robienia pewnych rzeczy w naszym wszechświecie.

Pod tym względem można go porównać do geometrii euklidesowej. Czy nasz wszechświat jest z natury euklidesowy? Dlaczego nasze metody pomiaru ziemi są ograniczone jej zasadami? Czy nie możemy mieć hipergeometrii, która umożliwia bardziej wydajny pomiar terenu? Odpowiedź brzmi: możemy i robimy, ale nie zawsze nazywamy wyniki „pomiarem terenu” lub „geometrią”.

Podobnie nasza teoria i praktyka w zakresie obliczeń wykraczają poza to, co mogą opisać maszyny Turinga (np. Istnieją obliczenia procesowe do opisywania systemów współbieżnych), ale niekoniecznie nazywamy te rozszerzenia „obliczeniami”.

Jedną z teoretycznych słabości maszyny Turinga jest jej przewidywalność. Wszechpotężny i wszechwiedzący przeciwnik może wykorzystać tę słabość, grając w jakąś grę przeciwko maszynie Turinga. Więc jeśli maszyna teoretyczna miałaby dostęp do losowego źródła, którego przeciwnik nie mógł przewidzieć (i mógł ukryć swój stan wewnętrzny przed przeciwnikiem), to ta maszyna teoretyczna byłaby potężniejsza niż maszyna Turinga.

Problemem z tego rodzaju maszyną teoretyczną w prawdziwym życiu nie jest to, czy losowe źródło jest całkowicie przypadkowe, czy nie (zakładanie, że jest całkowicie losowe, jest nieszkodliwą idealizacją), ale że nigdy nie możemy być pewni, czy udało nam się ukryć nasze wewnętrzne stan od naszego przeciwnika. W konkretnym przypadku nigdy nie można mieć pewności, czy idealna jest bieżąca instancja sytuacji przez taką maszynę. Jest to tylko nieznacznie lepsza sytuacja niż w przypadku większości rodzajów hiper-obliczeń, gdzie nie jest dla mnie jasne, które z wyidealizowanych sytuacji powinny być modelowane przez te (kiedyś odpowiedziałem: Więc potrzebuję jakiegoś rodzaju wszechwiedzącej cudownej maszyny do rozwiązania „RE”, Nie wiedziałem, że takie maszyny istnieją ).

$\Pi_2^0$ Ta wymówka powstała w wyniku rozmowy z innym Thomasem, czyli Thomasem Chustem.)