Dlaczego kompletność Turinga jest słuszna?

15

Korzystam z komputera cyfrowego, aby napisać tę wiadomość. Taka maszyna ma właściwość, która, jeśli się nad tym zastanowić, jest naprawdę niezwykła: jest to jedna maszyna, która przy odpowiednim zaprogramowaniu może wykonać dowolne możliwe obliczenia .

Oczywiście kalkulatory tego rodzaju wracają do starożytności. Ludzie zbudowali maszyny, które wykonują dodawanie i odejmowanie (np. Liczydło), mnożenie i dzielenie (np. Reguła suwaka), a także maszyny bardziej specyficzne dla danej dziedziny, takie jak kalkulatory pozycji planet.

Uderzającą cechą komputera jest to, że może on wykonywać dowolne obliczenia. Wszelkie obliczenia w ogóle. A wszystko to bez konieczności ponownego okablowania maszyny. Dzisiaj wszyscy uważają ten pomysł za pewnik, ale jeśli przestaniesz i pomyślisz o tym, to niesamowite, że takie urządzenie jest możliwe.

Mam dwa aktualne pytania :

  1. Kiedy ludzkość odkryła, że ​​taka maszyna jest możliwa? Czy kiedykolwiek istniały poważne wątpliwości, czy można to zrobić? Kiedy to zostało uregulowane? (W szczególności, czy zostało to uregulowane przed pierwszym faktycznym wdrożeniem czy po nim?)

  2. Jak matematycy udowodnili, że kompletna maszyna Turinga może naprawdę wszystko obliczyć?

Ten drugi jest niespokojny. Każdy formalizm wydaje się mieć pewne rzeczy, których nie można obliczyć. Obecnie „funkcja obliczalna” jest definiowana jako „wszystko, co może obliczyć maszyna Turinga”. Ale skąd wiemy, że nie ma trochę bardziej wydajnej maszyny, która mogłaby obliczyć więcej rzeczy? Skąd wiemy, że maszyny Turinga są właściwą abstrakcją?

MathematicalOrchid
źródło
7
Komputery (i ich modele teoretyczne, takie jak maszyny Turinga) NIE MOGĄ obliczyć wszystkiego. Sprawdź na przykład problem zatrzymania .
2
Odpowiedź na drugie pytanie: nie udowadniamy tego; to kwestia definicji; Okazuje się, że to, co intuicyjnie myślimy o „obliczalności”, jest obliczalne przez maszyny Turinga (lub cokolwiek równoważnego). Twierdzenie to znane jest jako teza Churcha-Turinga .
sdcvvc
2
Maszyny takie jak komputer z ograniczoną pamięcią nie są odpowiednikami Turinga. Maszyny Turinga mają nieograniczoną taśmę, co oznacza, że ​​im dłużej trwa obliczenie, tym więcej pamięci mogą potencjalnie wykorzystać. Komputery nie mogą wykonywać obliczeń, które wymagają skończonego czasu, ale wymagają więcej miejsca niż są dostępne.
Mike Samuel
3
@MikeSamuel to pedantyczne rozróżnienie i podobne do powiedzenia „we wszechświecie jest skończona liczba cząstek, a zatem wszystko jest stanem skończonym”. To prawdziwe stwierdzenie, ale nieprzydatne. Rzadko przydatne jest modelowanie komputera rzeczywistego jako skończonej maszyny stanów.
Artem Kaznatcheev

Odpowiedzi:

17

Ludzkość sformalizowane obliczeń i opracowała dwa system do niej w 1936 roku z nasiennych papierach Alonzo Church naλ

Chociaż artykuł Churcha został opublikowany nieco wcześniej, Turing nie był tego świadomy, gdy rozwinął swoje pomysły, a podejście Turinga okazało się bardziej przydatne w projektowaniu maszyn w świecie rzeczywistym. Stało się tak, ponieważ pokazał, jak zaprojektować uniwersalną maszynę Turinga, którą można zaprogramować do wykonywania dowolnych obliczeń. Ta uniwersalna maszyna o konkretnej architekturze opartej na twórczości Johna von Neumanna jest podstawową ideą maszyny, na której czytasz moją odpowiedź.

Jak zauważyłeś, obliczalność jest definiowana jako „obliczalna na maszynie Turinga” i wszystkie inne rozsądne modele obliczeń okazały się równoważne pod względem mocy. Przekonanie, że wszystkie rozsądne modele obliczeń są równoważne w rozwiązywaniu problemów decyzyjnych, które mogą rozwiązać, jest znane jako teza Kościoła Turinga . W swojej oryginalnej formie prawie całkowicie wierzy temu uczona społeczność. W rzeczywistości nie jest całkowicie jasne, co to znaczy udowodnić / obalić tezę Turinga ; na wiele sposobów staje się pytaniem empirycznym.

λ rachunek, maszyny Turinga, systemy oparte na znacznikach, automaty komórkowe itp. Są równoważne w ramach rozszerzonej tezy. Jednak niedawny rozwój obliczeń kwantowych poddaje w wątpliwość rozszerzoną tezę. Chociaż większość ludzi pracujących na komputerach kwantowych (w tym ja) uważa, że ​​są bardziej wydajni niż komputery klasyczne, kwestia ta jest przedmiotem debaty naukowej . Zauważ, że pod względem zgrubnego pojęcia tego, co jest obliczalne (w przeciwieństwie do wydajnego

Artem Kaznatcheev
źródło
1
Artykuł Turinga z 1936 r., W porównaniu z ówczesną pracą Churcha, był znacznie bardziej przekonujący w swoim argumencie, że dowolną funkcję numeryczną, którą człowiek może obliczyć algorytmicznie, można obliczyć za pomocą maszyny Turinga. Formalizm Kościoła nie miał oczywiście tej właściwości i do dziś redukcja innych systemów obliczeniowych do maszyn Turinga jest niezbędna ze względu na pierwotną analizę Turinga, jaką maszyny Turinga mogą obliczyć.
Carl Mummert
1
@CarlMummert Zdecydowanie się zgadzam, ale praca Kościoła musi być wspomniana dla kompletności. Nie jest to wcale nieistotne, podczas gdy większość teorii A jest zbudowana wokół baz TM, teoria B jest znacznie bardziej przyjazna dla lambda. Jest to więc częściowo różnica kultur.
Artem Kaznatcheev
Czekaj - więc mówisz, że nie udowodniono, że nie ma już potężnego systemu obliczeniowego? To tylko założenie ?
MathematicalOrchid
@MathematicalOrchid wszystkie rozsądne modele obliczeń (rozsądne z grubsza oznacza: kiedyś pracowałem tylko nad skończonymi sekcjami obiektów i wykonałem tylko jedną z wielu skończonych opcji), które znam, które były znane jako maszyny Turinga.
Artem Kaznatcheev
2
@MathematicalOrchid Aby zapewnić potencjalnie prostszą odpowiedź na twoje dalsze pytanie: prawda, nikt nie udowodnił, że nie ma jakiegoś rozsądnego modelu obliczeń o większej mocy niż TM. „Wniebowzięcie” to jedno słowo; „hipoteza” to kolejna. Moglibyśmy obudzić się jutro i zobaczyć o nowym, lepszym modelu obliczeń w CNN. To mało prawdopodobne, ale możliwe.
Patrick87,
-2

Istnieje powód, który nazywa się Maszyną Turinga, i dlatego, że został wymyślony przez Alana Turinga. Zrobił na nim artykuł z 1936 r., Ustanawiając te koncepcje. Jeśli chcesz dowiedzieć się więcej o maszynach Turinga, sprawdź papier. Poważnie wątpiono, zanim zaprojektował i zbudował taki, który złamał Enigmę, że ta koncepcja może faktycznie zadziałać. Jednak Brytyjczycy byli dość zdesperowani, a on był geniuszem, więc zaufali mu i to ogromnie się opłaciło.

Jednak gdy się nad tym zastanowić, to wcale nie jest takie niesamowite. Na długo przed Turingem wiadomo było, że całą matematykę można zredukować do pewnego zestawu aksjomatów. Wszystko, co musicie zrobić, to dać zestawowi instrukcji możliwość wykonywania tych aksjomatów i gotowe.

Szczeniak
źródło
Turing nie zaprojektował ani nie stworzył zagadki (chociaż zaprojektował inny komputer, który nigdy nie został zbudowany). Drugi akapit jest dobrze zrobiony: wiele emocji związanych z czasem Turinga (i to był właśnie punkt jego własnej pracy) związanych z granicami obliczeń.
Marcin
Ufaliśmy mu? Dopóki publicznie nie udowodniono, że jest homoseksualistą, zabiliśmy go za to. Udowodniono również, że istnieje zbiór problemów, które można stwierdzić w ramach dowolnej struktury aksjomatycznej, których nigdy nie można udowodnić za pomocą tych aksjomatów.
@TonyHopkinson: Wiem. Jednak zadaniem TM nie jest obliczanie wszystkiego , a jedynie obliczanie tego, co można obliczyć. Twoje stwierdzenie mówi tylko, że istnieją pewne obliczenia, których nie można udowodnić, że są poprawne. To nie znaczy, że nie można tego zrobić.
@Marcin: Nigdy nie sugerowałem, że Turing zaprojektował lub zbudował Enigmę. Powiedziałem, że odegrał kluczową rolę w maszynie, która złamała Enigmę.
7
Ta odpowiedź jest zła . Turing nie zaprojektował TM do złamania zagadki, pomógł zaprojektować Bombe, która była specjalistyczną maszyną do atakowania szyfru Enigmy, a nie uniwersalną. Ponadto nie było wiadomo, że matematykę można sprowadzić do pewnego zestawu aksjomatów. W rzeczywistości w 1931 roku Godel udowodnił coś przeciwnego i to na ideach tego dowodu opiera się praca Turinga. Nawet wstępny komentarz na temat czytania oryginalnej pracy Turinga wprowadza w błąd. Chociaż papier jest świetny, jeśli chcesz tylko nauczyć się podstaw, lepsze są nowoczesne podręczniki, takie jak Sipser.
Artem Kaznatcheev