Dlaczego maszyna Turinga jest popularnym modelem obliczeniowym?

Jestem studentem CS. Rozumiem, jak Turing wymyślił swoją abstrakcyjną maszynę (modelującą osobę wykonującą obliczenia), ale wydaje mi się to niewygodną, ​​nieelegacyjną abstrakcją. Dlaczego uważamy „taśmę” i maszynę piszącą symbole, zmieniającą stan, przesuwającą taśmę tam iz powrotem?

Jakie jest podstawowe znaczenie? DFA jest elegancki - wydaje się, że dokładnie przechwytuje to, co jest konieczne do rozpoznania zwykłych języków. Ale maszyna Turinga, według mojego nowicjatu, jest po prostu niezgrabnym abstrakcyjnym urządzeniem.

Po przemyśleniu wydaje mi się, że najbardziej wyidealizowanym modelem obliczeń byłoby stwierdzenie, że jakiś układ fizyczny odpowiadający łańcuchowi wejściowemu, po wprawieniu go w ruch, osiągnąłby równowagę statyczną, która przy interpretacji równoważna z tą, którą formowano system z oryginalnego ciągu odpowiadałby prawidłowemu ciągowi wyjściowemu. Uwzględnia to pojęcie „automatyzacji”, ponieważ system zmieniałby się deterministycznie wyłącznie na podstawie stanu pierwotnego.

Edytuj :

Po przeczytaniu kilku odpowiedzi zdałem sobie sprawę, że w maszynie Turinga mylę mnie to, że nie wydaje się minimalna. Czy kanoniczny model obliczeń nie powinien oczywiście przekazywać istoty obliczalności?

Ponadto, jeśli nie było jasne, wiem, że DFA nie są kompletnymi modelami obliczeniowymi.

Dziękuję za odpowiedzi.

Cóż, DFA to tylko maszyna Turinga, która może tylko przesuwać się w prawo i która musi zaakceptować lub odrzucić, gdy tylko zabraknie znaków wejściowych. Nie jestem więc pewien, czy naprawdę można powiedzieć, że DFA jest naturalny, ale maszyna Turinga nie.

Odkładając na bok pytanie, pamiętaj, że Turing działał, zanim istniały komputery. Jako taki, nie próbował skodyfikować tego, co robią komputery elektroniczne, ale ogólnie obliczenia. Moi rodzice mają słownik z lat 30. XX wieku, który definiuje komputer jako „kogoś, kto oblicza”, i to właśnie z tego pochodzi Turing: dla niego w tym czasie obliczenia dotyczyły zasad slajdów, tabel dzienników, ołówków i kawałków papieru. W takim nastawieniu przepisywanie symboli na papierowej taśmie nie wydaje się złą abstrakcją.

OK, w porządku, mówisz (mam nadzieję!), Ale nie jesteśmy już w latach 30. XX wieku, więc dlaczego nadal tego używamy? Tutaj nie sądzę, że istnieje jeden konkretny powód. Zaletą maszyn Turinga jest to, że są one dość proste, a my jesteśmy całkiem dobrzy w dowodzeniu na ich temat. Chociaż formalne określenie programu maszynowego Turinga do wykonania określonego zadania jest bardzo żmudne, po wykonaniu go kilka razy masz rozsądną intuicję co do tego, co mogą zrobić i nie musisz już pisać formalnych specyfikacji. Model można również łatwo rozszerzyć o inne naturalne funkcje, takie jak losowy dostęp do taśmy. Są to więc bardzo użyteczny model, który dobrze rozumiemy, a także całkiem niezłe rozumienie tego, jak odnoszą się do rzeczywistych komputerów.

Można użyć innych modeli, ale wówczas trzeba będzie dokonać ogromnej translacji między wynikami dla nowego modelu a ogromną ilością istniejących prac nad tym, co mogą zrobić maszyny Turinga. Nikt nie wymyślił zamiennika dla maszyn Turinga, które miałyby wystarczająco duże zalety, aby wyglądały na dobry pomysł.

Zadajesz kilka różnych pytań. Pozwólcie, że krótko odpowiem jeden po drugim.

Co jest tak ważne w modelu maszyny Turinga?

W początkowym okresie teorii obliczeń zasugerowano kilka modeli obliczeń w różnych kontekstach. Na przykład Gödel, który próbował zrozumieć, do których systemów dowodowych odnosi się jego twierdzenie o niekompletności, wymyślił formalizm ogólnych funkcji rekurencyjnych , a Kościół wymyślił rachunek jako próbę pozbawionych paradoksów podstaw matematyki. Sam Turing był motywowany problemem Hilberta, który poprosił o „czysto mechaniczny proces” w celu ustalenia prawdziwej wartości danego zdania matematycznego.$\lambda$

W tym czasie próba zdefiniowania obliczalności przez Turinga wydawała się najbardziej satysfakcjonująca. W końcu okazało się, że wszystkie opisane powyżej modele obliczeń są równoważne - wszystkie opisują to samo pojęcie obliczalności. Z przyczyn historycznych model Turinga okazał się najbardziej kanonicznym sposobem definiowania obliczalności. Model jest również bardzo szczątkowy i bardzo łatwy w obsłudze, w porównaniu do wielu innych modeli, w tym wymienionych powyżej.

Zwykła informatyka uczy maszyn Turinga jako definicji obliczalności, a następnie wykorzystuje je również do badania teorii złożoności. Ale algorytmy są analizowane w odniesieniu do bardziej realistycznego modelu znanego jako maszyna RAM, chociaż ten problem jest zwykle zamiatany pod dywan jako tajemnica dla kognitywistów.

Czy DFA nie są lepszym modelem?

Taka była pierwotna motywacja słynnego artykułu Rabina i Scotta, automatów skończonych i ich problemów decyzyjnych:

Maszyny Turinga są powszechnie uważane za abstrakcyjny prototyp komputerów cyfrowych; jednak pracownicy w terenie coraz bardziej odczuwali, że pojęcie maszyny Turinga jest zbyt ogólne, aby służyć jako dokładny model rzeczywistych komputerów. Dobrze wiadomo, że nawet w przypadku prostych obliczeń niemożliwe jest ustalenie a priori górnej granicy ilości taśmy, której maszyna Turinga będzie potrzebować do danego obliczenia. Właśnie ta cecha sprawia, że ​​koncepcja Turinga jest nierealna.

W ostatnich latach w literaturze pojawiła się idea skończonego automatu. Są to maszyny posiadające tylko skończoną liczbę stanów wewnętrznych, których można użyć do pamięci i obliczeń. Wydaje się, że ograniczenie skończoności lepiej przybliża ideę fizycznej maszyny. Oczywiście takie maszyny nie są w stanie zrobić tyle, co maszyny Turinga, ale przewaga wynikająca z możliwości obliczenia dowolnej ogólnej funkcji rekurencyjnej jest wątpliwa, ponieważ bardzo niewiele z tych funkcji pojawia się w praktycznych zastosowaniach.

Okazało się jednak, że podczas gdy maszyny Turinga są zbyt silne, DFA są zbyt słabe . W dzisiejszych czasach teoretycy wolą pojęcie wielomianowego obliczania czasu , chociaż nie jest to również pozbawione problemów. To powiedziawszy, DFA i NFA nadal mają swoje zastosowania, głównie w kompilatorach (wykorzystywanych do analizy leksykalnej) i urządzeniach sieciowych (wykorzystywanych do niezwykle wydajnego filtrowania).

Czy model maszyny Turinga nie jest zbyt ograniczony?

Hipoteza Churcha-Turinga stwierdza, że maszyny Turinga uchwycić fizycznej pojęcie obliczalności. Jurij Gurewicz przeprowadził próbę udowodnienia tej tezy, formułując bardziej ogólną klasę urządzeń obliczeniowych zwanych abstrakcyjnymi maszynami stanów i wykazując, że są one równoważne pod względem mocy z maszynami Turinga. Być może te maszyny są analogiczne do twojego wyidealizowanego modelu.

Podstawowe znaczenie ma idea równoważności Turinga. Dokładny model nie jest ważny, o ile jest on odpowiednikiem Turinga. Ale lepiej jest użyć prostszego modelu, aby łatwiej było udowodnić równoważność z innymi modelami.

Mówiąc dokładniej, łatwiej jest symulować ten model w innych modelach, ponieważ wiemy, że większość zaawansowanych języków programowania jest odpowiednikiem Turinga (z pewnymi założeniami dotyczącymi adresów pamięci) i może być używana do symulacji innych modeli.

Istnieją inne modele, takie jak rachunek lambda i gramatyka (przepisywanie ciągów). Ale łatwiej jest zdefiniować ograniczenia czasu i przestrzeni w maszynie Turinga. Możesz także użyć języka programowania, takiego jak Brainfuck, ale wymaga to niepotrzebnej pracy, na przykład przedefiniowania symboli, aby czasami uzyskać logicznie trywialną modyfikację.

Tak więc maszyna Turinga wydawała mi się odpowiednia, jeśli musisz nauczyć się jednego modelu do wszystkiego. Ale jeśli i tak zamierzasz nauczyć się wielu modeli, nie widzę nic złego w nauce rachunku lambda dla idei równoważności Turinga, Brainfuck do udowodnienia innych modeli równoważności Turinga i praktycznych języków programowania (lepiej z dostępnym stosem i bez ukrytych zmiennych) ze względu na ograniczenia czasowe / przestrzenne i rozważ maszynę Turinga tylko jako narzędzie do udowodnienia równoważności tych rzeczy, jeśli nikt nie będzie chciał znaleźć sposobu na obejście tego. Dzieje się tak naturalnie, jeśli nie zacząłeś najpierw od poznania podstawowej teorii, ale zrobiłeś to tylko wtedy, gdy uznasz ją za przydatną.

Chciałbym odpowiedzieć na tę część pytania, dodaną w edycji:

„Czy kanoniczny model obliczeń nie powinien oczywiście przekazywać istoty obliczalności?”

Jedną z niezwykłych rzeczy, które Turing zrobił w swoim oryginalnym artykule - tym, który przedstawił to, co teraz nazywamy „maszynami Turinga” - było to, że zbudował jedną maszynę Turinga, która może symulować każdą inną maszynę Turinga. Po zbudowaniu tej „uniwersalnej maszyny Turinga” działa ona przez wykonanie taśmy wejściowej, która ma dwie niezależne cechy: po pierwsze, kodowanie maszyny Turinga , którą chce się symulować; następnie kopia taśmy wejściowej, którą należałoby włożyć do maszyny Turinga , gdyby przypadkiem ktoś miał siedzącego w pobliżu. W semimodernistycznym żargonie: najpierw wstawia się program, który kompiluje uniwersalna maszyna Turinga; następnie wstawia się wejście, które uruchamia uniwersalna maszyna Turinga za pomocą skompilowanego programu.T $T$$T$$T$

Jest to jedna z esencji obliczalności: niezależnie od ogólnego pojęcia obliczalności, powinna istnieć jedna maszyna, która to wszystko zrobi. To właśnie robi uniwersalna maszyna Turinga. To samo robią współczesne komputery (podlegające nierealistycznej idealizacji posiadania nieskończonej pamięci).

Innym sposobem przedstawienia tego, co bezpośrednio odnosi się do obawy, że maszyny Turinga nie są minimalne, jest to, że są tak minimalne, jak mogą być, z zastrzeżeniem wymogu opisania ogólnego pojęcia obliczalności, dla którego istnieje maszyna uniwersalna.

Maszyny Turinga nie powinny być używane dosłownie; programowanie w nich jest czymś, co można zrobić tylko raz jako ćwiczenie, aby zrozumieć, jak działają.

Nie są specjalnie stworzone do „robienia” czegokolwiek. Nie muszą być minimalne, nie muszą być wygodne w pracy.

Są po prostu modelem maszyny, którą można zbudować, która byłaby tak wyrazista i potężna, jak każda inna maszyna, jaką kiedykolwiek można zbudować we wszechświecie fizycznym (o ile wiemy dzisiaj).

Zostały zdefiniowane przez Turinga takimi, jakie są z następujących głównych powodów:

• Aby móc udowodnić, że obejmują one dowolny algorytm, jaki kiedykolwiek wymyśliliśmy.
• Aby pracować nad problemem zatrzymania / problemem decyzyjnym.
• Aby móc zredukować dowolną inną maszynę / język do tego.

Czy można wybrać inny język? Na pewno! Można użyć dowolnego z kompletnych języków, które znamy dzisiaj. Ale o wiele trudniej byłoby zbudować podstawy teoretyczne na bardziej złożonej maszynie.

Twierdziłbym, że nie są nawet „popularnym modelem obliczeń”; nikt nigdy nie obliczałby niczego za pomocą Maszyny Turinga. Jest to czysto teoretyczna koncepcja stworzona przez teoretycznych informatyków dla tcs.

Dlaczego jest popularny, a może najbardziej popularny? Musisz pamiętać, że Turing wynalazł tę „maszynę” wiele lat przed komputerami elektronicznymi. TM obsługiwana jest za pomocą papieru, długopisu, gumy i wreszcie ludzkiego mózgu. Dzięki temu każdy może uruchomić „obliczenia” na tym komputerze. Każdy oznacza osobę, która nigdy nie nauczyła się komputerów, programuje języki. Jest prosty w użyciu. Kiedy się nad tym zastanowić, odkrywa się paradoks: ta maszyna jest zbiorem prawie nic, ale można sterować wszystkim. Moim zdaniem paradoks „prawie nic / kontra / wszystko” jest powodem, dla którego jest popularny. Zauważyłbym, że TM nie wyjaśnia wprost rekurencji, TM zajmuje się tylko „skokiem”. Ta funkcja (wyraźnie mówiąc o rekurencji) może być źródłem bólu głowy dla początkujących, na przykład w rachunku lambda koncepcja kombinatora Y jest prawie niezrozumiała; Mówiąc dokładniej, TM jest popularny, ponieważ paradoks „prawie nic / kontra / wszystko” bez rekurencyjnego bólu głowy.