Dlaczego kompletność Turinga jest słuszna?

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ą?

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

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.

$\lambda$ 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

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.