Historyczne przyczyny przyjęcia maszyny Turinga jako podstawowego modelu obliczeń.

44

Rozumiem, że model Turinga stał się „standardem” przy opisywaniu obliczeń. Interesuje mnie, dlaczego tak jest - to znaczy, dlaczego model TM stał się szerzej stosowany niż inne teoretycznie równoważne (o ile mi wiadomo) modele, na przykład μ-Recursion Kleene'a lub rachunek lambda (rozumiem to pierwsze pojawiło się dopiero później, a drugie nie zostało pierwotnie zaprojektowane specjalnie jako model obliczeniowy, ale pokazuje, że od samego początku istniały alternatywy).

Mogę tylko myśleć, że model TM bardziej reprezentuje komputery, które faktycznie mamy, niż jego alternatywy. Czy to jedyny powód?

Evan
źródło
1
chociaż nie są bezpośrednio na ten sam temat, pytania cstheory.stackexchange.com/questions/625/… i cstheory.stackexchange.com/questions/1117/… badają związek między bazami TM a kalkulatorem i mają pewne historyczne elementy. λ
Suresh Venkat,
Tak, widziałem je. Rozumiem dosłownie historie różnych teorii, ale bardziej interesuje mnie rozwój wydarzeń w czasie, który doprowadził do obecnych „preferencji” w tej dziedzinie, jeśli wolisz.
Evan,
2
W rzeczywistości istnieją modele (prawdopodobnie) bliższe prawdziwym komputerom, patrz to pytanie . Zasadniczo najlepszy model zależy od potrzeb i różnią się w zależności od obszaru.
Kaveh

Odpowiedzi:

46

Wydaje się, że jest to prawdą w kontekście (niektórych dziedzin) informatyki, ale nie ogólnie.

Jednym z powodów jest teza Kościoła. Głównym powodem jest to, że niektórzy eksperci, tacy jak Godel, nie sądzili, że argumenty, że poprzednie / inne modele obliczeń zawierają dokładnie intuicyjną koncepcję obliczeń, były przekonujące. Istnieją różne argumenty, Kościół miał kilka, ale nie przekonali Godela. Z drugiej strony analiza Turinga przekonywał do Gödel tak to zostało zaakceptowane jako na wzór dla skutecznej obliczeń. Równoważności między różnymi modelami udowodniono później (tak sądzę Kleene).

λμ

μλ. Zobacz także te prace Viggo Stoltenberg-Hansen i Johna V. Tuckera I , II .)

Niektóre zasoby do dalszego czytania:

Robert I. Soare ma wiele artykułów na temat historii tych osiągnięć. Osobiście podoba mi się ten z Podręcznika teorii obliczeń. można znaleźć więcej, sprawdzając odniesienia w tym dokumencie.

Innym dobrym zasobem jest artykuł Neila Immermana na temat obliczeń SEP, patrz także artykuł Thesis Church-Turinga autorstwa B. Jacka Copelanda.

Zebrane prace Godela zawierają wiele informacji na temat jego poglądów. Szczególnie wprowadzenie do jego artykułów jest wyjątkowo dobrze napisane.

MetamathematicsKleene'a to bardzo fajna książka.

Na koniec, jeśli nadal nie jesteś zadowolony, sprawdź archiwa listy mailingowej FOM , a jeśli nie możesz znaleźć odpowiedzi w archiwum, wyślij wiadomość e-mail na listę mailingową.

Kaveh
źródło
Daj mi znać, jeśli coś jest nie tak.
Kaveh
1
Wow, to świetna informacja. Dzięki za zasoby, sprawdzę je (planowałem przeczytać Metamathematics - podniosę to w kolejce).
Evan,
Proszę bardzo, mam nadzieję, że nie pomyliłem się. :)
Kaveh
Nie było niedawne rozmowy przez Roberta Soare w ini. Jak rozumiem, główny powód przejścia na model Turinga i obliczalność z funkcji rekurencyjnych i teorii rekurencji jest dla niego następujący: trudno jest zrozumieć i pracować w teorii rekurencji do tego stopnia, że ​​nikt nie rozumiał, co się dzieje kilka zmian w obliczeniach znacznie ułatwiło zrozumienie i ożywiło ten obszar.
Kaveh
19

Chciałbym osłabić twierdzenie, że bazy TM są podstawowym modelem obliczeń lub przynajmniej wskazują na inny wymiar pytania. Najwyraźniej bazy TM są dominujące w bardziej informatycznych i zorientowanych algorytmicznie częściach informatyki, ale w teorii i praktyce języka programowania nie są one szczególnie dominujące. Przyczyny tego są różne, ale być może najważniejsze jest to, że bazy TM lub programy działające na bazach TM (w przeciwieństwie np. Rachunek lambda lub rachunek procesowy) nie są budowane w sposób algebraiczny. Utrudnia to opracowywanie teorii typów, które stanowiły podstawę teorii języka programowania.

Martin Berger
źródło
2
Ponadto programy TM, czyli tabele przejścia, nie są tak naprawdę czytelne dla ludzi.
Raphael,
13

Jedną z fajnych rzeczy w maszynach Turinga jest to, że pracują na ciągach zamiast liczb naturalnych lub terminów lambda, ponieważ dane wejściowe i wyjściowe wielu problemów mogą być naturalnie sformułowane jako ciągi. Nie wiem jednak, czy liczy się to jako „historyczny” powód, czy nie.

Tsuyoshi Ito
źródło
13

Oprócz faktu, że maszyny Turinga są przekonującym modelem obliczeń pisanych i pisanych na papierze („intuicyjne pojęcie obliczeń”), myślę, że posiadają one szereg funkcji, które są często przydatne, szczególnie przy dowodzeniu twierdzeń na ich temat:

  • łatwo je formalnie opisać i mają prostą semantykę operacyjną;
  • łatwo jest podać konkretną definicję złożoności czasu i przestrzeni;
  • bardziej realistyczne (i złożone) modele komputerów elektronicznych, takie jak maszyny o dostępie swobodnym, mogą być symulowane przez TM z wielomianem i odwrotnie.
Antonio E. Porreca
źródło
Czasami łatwość opisywania wydaje się utrudniać przydatność baz TM, ponieważ opisy mogą szybko przekształcić się w zwykłe angielskie wyjaśnienia, jeśli nie jesteś ostrożny (przynajmniej jeśli nie jestem ostrożny ... Przyznaję, że jestem nowicjuszem).
Evan,
Twoje powody nie wykluczają na przykład rejestrowania maszyn.
Raphael
Zależy to od dokładnego pojęcia „maszyny rejestrującej”, którą rozważasz. Na przykład osoby posiadające tylko operacje zwiększania, zmniejszania i przeskakiwania nie mogą symulować baz TM w czasie wielomianowym.
Antonio E. Porreca,
1
λλ
Jestem po stronie PL, ale czysty rachunek lambda nie jest oczywistym modelem obliczeń arytmetycznych (pomyśl o poprzedniej funkcji). W rachunku lambda masz mniej definicji, ale potrzeba więcej wysiłku, aby zrozumieć implikacje definicji.
Blaisorblade,
0

Jako pierwszy miał wpływ i dlatego został ustanowiony, szczególnie w teorii złożoności. To słaby powód, ale ludzie tak pracują. Najpierw pracujemy nad starymi otwartymi problemami, zamiast deklarować nowe.

Raphael
źródło
8
„Najpierw pracujemy nad starymi otwartymi problemami, zamiast deklarować nowe”. <- Myślę, że w przeciwnym razie prawda jest odwrotna, szczególnie w dziedzinie, w której stare pytania są niezwykle trudne. Na przykład stosunkowo niewiele osób pracuje na złożoności obwodów (choć być może teraz będzie ich więcej!). Ludzie muszą pracować nad problemami, które mogą rozwiązać, aby publikować; generuje to stały przepływ nowo zadeklarowanych możliwych do rozwiązania problemów.
Aaron Sterling
Byłem tam trochę pochopny. Wydaje mi się, że często ludzie raczej trzymają się ustalonego modelu niż budują nowy (i udowadniają jego podstawowe właściwości), jeśli nie ma tego przeważającego powodu. To uczucie może być wyłączone. W szczególności są przede wszystkim ludzie, którzy polują na modele.
Raphael
Najpierw był rachunek lambda. Ale Turing wykazał, że maszyny Turinga dokładnie modelują podstawy ludzi wykonujących obliczenia; zostało to zrobione tylko w przypadku rachunku lambda podczas potwierdzania równoważności. Co więcej, ta równoważność dotyczy tylko obliczeń pierwszego rzędu: cstheory.stackexchange.com/q/1117/989 - dane wyższego rzędu tak naprawdę nie istnieją na papierze. Nie istnieje nawet w pamięci komputera, ale można go idealnie symulować.
Blaisorblade