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

39

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

użytkownik1561358
źródło
5
Pytania takie jak „czy X jest cechą charakterystyczną naszego ( sic ) wszechświata?” jest pytaniem z fizyki, ponieważ fizyka jest właśnie badaniem „praw wszechświata”. Informatyka dotyczy przedmiotów matematycznych, które czasami zdarzają się do wdrożenia za pomocą środków fizycznych.
Bakuriu
2
Poleciłbym zajrzeć
nobillygreen
1. Prosimy o zadawanie tylko jednego pytania na post. Jeśli masz inne pytania, możesz je opublikować osobno, po wyświetleniu odpowiedzi na to pytanie. Również pytania dotyczące cech charakterystycznych naszego wszechświata są pytaniami z fizyki i są tutaj nie na temat. Redaguję dodatkowe pytania, aby pomóc Ci skoncentrować się na jednym pytaniu. Możesz opublikować je osobno (zobacz historię zmian, aby je znaleźć ponownie). 2. Jakie badania przeprowadziłeś? Jakie są Twoje myśli? Pytanie w jednym zdaniu jest za krótkie. Spróbuj go edytować, aby go rozwinąć; które pomogą Ci uzyskać lepsze odpowiedzi.
DW
3. „Czy możemy założyć, że ....” - nie, oczywiście, że nie. Dlaczego myślisz, że możesz to założyć? Nie możesz po prostu założyć czegoś, ponieważ byłoby miło, gdyby to była prawda, lub wydaje się, że to może być prawda, lub ponieważ nie widzimy od razu powodu, dla którego byłoby to fałszywe. Informatyka to dowód, a nie tylko zakładanie rzeczy. Jakie jest twoje prawdziwe pytanie?
DW

Odpowiedzi:

26

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ę.

Yuval Filmus
źródło
Właściwie mam już zakładkę w Scotts. :) W każdym razie, odkąd teza TK jest nadal aktualna (chyba że coś się stało, nie jestem tego świadomy), wszystko, co pozostaje, to mówić o definicji komputera lub szukać maszyny, która w jakiś sposób obali CT.
user1561358,
3
„Jak omówiono w tym eseju, teoria złożoności wykroczyła daleko poza deterministyczne maszyny Turinga i obejmuje (na przykład) mechanikę kwantową, obliczenia równoległe i rozproszone oraz procesy stochastyczne, takie jak ewolucja darwinowska”. ( Dlaczego filozofowie powinni dbać o złożoność obliczeniową , autor: Scott Aaronson , s. 49)
reinierpost,
1
Myślę, że warto również zauważyć, że komputery kwantowe nie przyspieszają arbitralnego zadania AFAIK. I „tylko” przyspieszają go maksymalnie o 2 ^ N, gdzie N jest liczbą bitów kwantowych.
Mam nadzieję, że będzie
13

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”.

reinierpost
źródło
przez „obliczenia za pomocą pojedynczego procesora wykonującego kroki ściśle sekwencyjnie bez zewnętrznych zakłóceń”, czy masz na myśli, że jeśli komputer ma zewnętrzne zakłócenia lub może pracować równolegle, jest znacznie potężniejszy niż maszyna Turinga?
kate
1
Nie do końca. Jeśli wszystko, co chcesz wiedzieć, to jakie odwzorowania od skończonych danych wejściowych do skończonych danych wyjściowych można obliczyć, to dodanie ich nie da ci więcej mocy: nie będziesz w stanie obliczyć większej liczby mapowań niż wcześniej.
reinierpost
5

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ą ).

Π20 Ta wymówka powstała w wyniku rozmowy z innym Thomasem, czyli Thomasem Chustem.)

Thomas Klimpel
źródło