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

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?

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

$\lambda$$\mu$

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

„ Metamathematics ” Kleene'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ą.

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.

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.

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.

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.