Czy istnieje fizyczna analogia do maszyny Turinga?

Ostatnio w mojej klasie CS zapoznałem się z Maszyną Turinga.

Po zajęciach spędziłem ponad 2 godziny, próbując dowiedzieć się, jaki jest związek między taśmą a maszyną.

Byłem całkowicie nieświadomy istnienia taśm komputerowych lub tego, jak taśmy i maszyny współdziałały do ​​dziś. Nadal nie rozumiem, dlaczego maszyna odczytuje taśmy, ale skaner jest być może bliższą koncepcją maszyny Turinga, w której papier jest uważany za taśmę, a wszystko, co wchodzi do skanera, jest tym, co zrobi maszyna Turinga.

Ale w każdym razie, czy pomysł maszyny Turinga nie jest dość archaiczny? W naszym biurze lub salonie mamy tak wiele fizycznych (a nie hipotetycznych) urządzeń, które wydają się robić to, co robi Maszyna Turinga.

Czy ktoś może podać lepszy przykład czerpiąc z rzeczywistości, aby uchwycić podstawowe funkcje tej hipotetycznej koncepcji?

Maszyny Turinga są jednym z „oryginalnych” kompletnych modeli obliczeniowych Turinga, wraz z rachunkiem i rekurencyjnie zdefiniowanymi funkcjami rekurencyjnymi. Obecnie w wielu obszarach informatyki teoretycznej stosuje się inny model, maszynę RAM, która jest znacznie bliższa rzeczywistym komputerom. Ponieważ oba modele są równoważne p (symulują się nawzajem z co najwyżej wielomianowym powiększeniem), z punktu widzenia pytań takich jak P vs. NP, oba modele są równoważne.$\lambda$

AFAIK Maszyna Turinga wzorowana jest na idei człowieka z długopisem i papierem. Człowiek ma pewien stan w mózgu, patrzy na papier, jakby maszyna patrzyła na taśmę, i zapisuje coś na papierze lub porusza się, by spojrzeć w inne miejsce, tak jak robi to maszyna.

TM jest archaiczna jak arytmetyka liczb naturalnych Peano. TM jest bezużyteczna do praktycznych obliczeń i oczywiście nie jest przeznaczona do tego. To tylko prosty sposób na aksjatyzację obliczeń, abyśmy mogli rozumować, co jest obliczalne, a co nie - tak jak arytmetyka Peano jest przydatna do definiowania na podstawie pierwszych zasad, czym są liczby naturalne i jakie są ich właściwości - ale byłoby śmieszne spróbuj wykonać arytmetykę, ręcznie manipulując liczbami Peano zgodnie z teoretycznymi definicjami.

Pomyśl tylko, jak trudno byłoby udowodnić inne twierdzenia z teorii złożoności i obliczalności (np. Udowodnić, że problem zatrzymania jest nierozstrzygalny), gdybyś musiał udowodnić je przy użyciu semantyki języka programowania C ++ zamiast maszyny Turinga. Wasze dowody byłyby absurdalne lub niemożliwe - tak absurdalne, jak dowodzenie skojarzenia mnożenia liczb naturalnych za pomocą metody szkoły podstawowej stosowanej do liczb całkowitych dziesiętnych jako definicji tego, czym jest mnożenie.

Wiele bardzo różnych kompletnych modeli obliczeniowych Turinga jest fizycznie wykonalnych (aż do uznania nieskończoności za bezgraniczność). Dlatego nie może to mieć sensu przy wyborze modelu.

Odpowiedź @jkff jest właściwa w stwierdzeniu, że Maszyna Turinga jest przeznaczona jako urządzenie teoretyczne do matematycznego celu badania obliczalności i sprawdzalności (powstającego właściwie w kontekście Entscheidungsproblem Hilberta ). Ale nie jest to całkiem dokładne powody wyboru prostego formalizmu.

Udowodnienie w zasadzie problemu zatrzymania nie jest o wiele trudniejsze w przypadku bardziej zaawansowanych modeli. W rzeczywistości nasze „dowody” są często tylko konstrukcją rozwiązania. Nie zagłębiamy się w faktyczne (bardzo żmudne) argumenty, że te konstrukcje są poprawne. Ale każdy, kto pisze tłumacza dla kompletnego języka Turinga, robi tyle samo, co każda konstrukcja, uniwersalną maszynę. Cóż, C może być nieco skomplikowane i możemy chcieć nieco go usprawnić w tym celu.

Ważność posiadania prostego modelu zależy znacznie bardziej od sposobu wykorzystania modelu niż od ustalenia jego właściwości (takich jak problem zatrzymania, na przykład podany przez @jkff).

Zazwyczaj wielkie twierdzenie to często twierdzenia, które można wyrazić bardzo prosto i dotyczą szerokiego zakresu problemów. Ale niekoniecznie są to twierdzenia łatwe do udowodnienia.

W przypadku TM znaczenie prostoty polega na tym, że wiele wyników osiągnięto poprzez zredukowanie problemu zatrzymania lub innych problemów TM do problemów, którymi jesteśmy zainteresowani (takich jak ambiguty języków bezkontekstowych), ustanawiając w ten sposób nieodłączne ograniczenia rozwiązywania te problemy.

W rzeczywistości, choć bardzo intuicyjny (co jest prawdopodobnie głównym powodem jego popularności), model TM często nie jest wystarczająco prosty do użycia w takich dowodach. Jest to jeden z powodów, dla których ważne są inne, nawet prostsze modele, takie jak problem korespondencyjny , mniej intuicyjny w analizie, ale łatwiejszy w użyciu. Wynika to jednak z faktu, że te modele obliczeniowe są często stosowane w celu udowodnienia negatywnych wyników (co sięga pierwotnego Entscheidungsproblem).

Jednak gdy chcemy udowodnić pozytywne wyniki, takie jak istnienie algorytmu do rozwiązania danego problemu, TM jest zbyt uproszczonym urządzeniem. Znacznie łatwiej jest rozważyć zaawansowane modele trybu, takie jak komputer RAM lub komputer pamięci skojarzonej , lub jeden z wielu innych modeli, a nawet po prostu jeden z wielu języków programowania.

Następnie model TM stanowi jedynie punkt odniesienia, w szczególności do analizy złożoności, biorąc pod uwagę złożoność zredukowania tych modeli do modelu TM (zwykle wielomianowego). Prostota modelu TM nadaje wówczas dużą wiarygodność miarom złożoności (w przeciwieństwie do aby wziąć ekstremalny przykład, do redukcji rachunku Lambda).

Innymi słowy, model TM jest często zbyt uproszczony do projektowania i badania algorytmów (wyniki dodatnie), a często zbyt skomplikowany do badania obliczalności (wyniki ujemne).

Wydaje się jednak , że jest to właściwe miejsce, aby służyć jako centralne łącze do połączenia tego wszystkiego razem, z tą wielką zaletą, że jest dość intuicyjny.

Jeśli chodzi o analogie fizyczne, nie ma powodu, aby wybierać jeden model nad drugim. Wiele kompletnych modeli obliczeniowych Turinga jest fizycznie wykonalnych (aż do nieograniczenia nieskończoności pamięci), ponieważ nie ma powodu, aby uważać komputer wraz z jego oprogramowaniem za mniej fizyczny niż „nagi” komputer. W końcu oprogramowanie ma fizyczną reprezentację, która jest częścią zaprogramowanego komputera. Ponieważ wszystkie modele obliczeniowe są z tego punktu widzenia równoważne, równie dobrze moglibyśmy wybrać taki, który jest dogodny dla organizacji wiedzy.

Wyobraź sobie nowicjusza w geometrii, który pyta:

Czy istnieje fizyczna analogia do trójkąta?

Czy pomysł trójkąta nie jest dość archaiczny? W naszym biurze lub salonie mamy tak wiele fizycznych (a nie hipotetycznych) kształtów, które wydają się robić to, co robi trójkąt.

Co byś odpowiedział

Można powiedzieć, że te pytania ujawniają dwa podstawowe nieporozumienia dotyczące trójkątów:

1. „Trójkąty są czysto hipotetyczne”. Źle! Choć są to byty matematyczne, platońskie ideały i hipotetyczne w tym sensie, trójkąty są prawdziwe : możemy je konstruować w prawdziwym świecie. To prawda, że ​​to, co konstruujemy, nigdy nie będzie idealnym trójkątem, ale nasza teoria matematyczna na ich temat dotyczy prawdziwego świata, prawa, które możemy wyprowadzić, dotyczą kształtów w prawdziwym świecie, teorię można wykorzystać jako podstawę do projektowania, konstruowanie i mierzenie kształtów w prawdziwym świecie; z tego powodu teoria została opracowana w pierwszej kolejności.
2. „Trójkąty są bezużyteczne, ponieważ nie opisują kształtów, których zwykle używamy”.Źle! Opisywanie rzeczywistych kształtów, które można znaleźć w prawdziwym świecie, nie jest ich celem. Jeśli w całym biurze lub salonie nie ma ani jednego trójkąta, nie oznacza to, że koncepcja trójkąta jest nierealna lub przestarzała i lepiej zastąpić ją czymś innym. Ich głównym celem jest elementarna konstrukcja, z której można zasadniczo zbudować wszystkie bardziej złożone kształty - i dla których możemy zatem wywodzić prawa, które mają zastosowanie do kształtów w ogóle. Rozumowanie trójkątów pozwala nam ogólnie rozumować kształty. Twój salon podlega tym samym prawom, które wyprowadziliśmy dla trójkątów, a nasza wiedza na temat tych praw została wykorzystana, bezpośrednio lub pośrednio, do jego budowy. W salonie prawdopodobnie nie ma ani jednego trójkąta, nie mówiąc już o idealnym, ale nie zależy nam na znalezieniu tam trójkątów; możemy. jednak zbuduj tam opis kształtów, przybliżając je trójkątami, a to - triangulacja - jest popularną i przydatną rzeczą do zrobienia. Tak więc trójkąty są elementami składowymi, które pomagają nam ogólnie myśleć o kształtach.

To samo dotyczy maszyn Turinga.

Minęło tak dużo czasu, odkąd zapoznałem się z geometrią, tak naprawdę nie mogę sobie przypomnieć, czy jakikolwiek nowicjusz rzeczywiście ma takie nieporozumienia na temat trójkątów. Ale jeśli chodzi o maszyny Turinga, spotykam Te nieporozumień cały czas . W rzeczywistości tak często wydaje się, że coś jest zasadniczo nie tak z tym, jak się je zwykle uczy. Być może podejście typu show and tell jest w porządku!

Tak więc, dla kompletności:

1. „Maszyny Turinga są czysto hipotetyczne”. Źle! Chociaż są to jednostki matematyczne, platońskie ideały i hipotetyczne w tym sensie, Maszyny Turinga są prawdziwe : możemy je konstruować w prawdziwym świecie. To prawda, że ​​to, co budujemy, nigdy nie będzie idealną Maszyną Turinga, ale nasza teoria matematyczna dotyczy ich prawdziwego świata, prawa, które możemy wyprowadzić, dotyczą urządzeń obliczeniowych w świecie rzeczywistym, teoria ta może być wykorzystana jako podstawa projektowanie, konstruowanie i mierzenie urządzeń obliczeniowych w świecie rzeczywistym; z tego powodu teoria została opracowana w pierwszej kolejności.
2. „Maszyny Turinga są bezużyteczne, ponieważ nie opisują urządzeń komputerowych, których zwykle używamy”.Źle! Opisywanie rzeczywistych urządzeń obliczeniowych, które można znaleźć w prawdziwym świecie, nie jest ich celem. Jeśli całe zaplecze biurowe lub domowe studio rozrywki nie zawiera pojedynczej maszyny Turinga, nie oznacza to, że koncepcja maszyny Turinga jest nierealna lub przestarzała i powinna zostać zastąpiona czymś innym. Ich głównym celem jest elementarna konstrukcja, z której można zasadniczo zbudować wszystkie bardziej złożone urządzenia obliczeniowe - i dla których możemy zatem wyprowadzić prawa, które mają zastosowanie do kształtów w ogóle. Rozumowanie maszyn Turinga pozwala nam ogólnie rozumować urządzenia obliczeniowe. Twój sprzęt komputerowy i oprogramowanie podlegają tym samym prawom, które uzyskaliśmy dla Maszyn Turinga, a nasza wiedza na temat tych praw została wykorzystana, bezpośrednio lub pośrednio, do ich budowy - nawet jeśli prawdopodobnie nie „ mieć w nich jedną Maszynę Turinga. Interesują nas prawa.

Fizyczną analogią, o której myśli Turing, jest komputer rozwiązujący problemy z ołówkiem, papierem i gumką. Powinieneś zrozumieć, że w 1936 r. „Komputer” był osobą zatrudnioną do obliczeń. Oczywiście w 1936 r. Większość komputerów używałaby maszyn do dodawania, ale Turing nie wspomina o nich, ponieważ są one nieistotne. Oto, co mówi, w odniesieniu do taśmy, próbując uzasadnić, że „liczby„ obliczalne ”[tj. Te, które mogłaby obliczyć maszyna Turinga] obejmują wszystkie liczby, które naturalnie można by uznać za obliczalne”

Obliczenia zwykle wykonuje się, pisząc określone symbole na papierze. Możemy przypuszczać, że ten papier jest podzielony na kwadraty jak dziecięca księga arytmetyczna. W elementarnej arytmetyki czasami stosuje się dwuwymiarowy charakter papieru. Ale takiego zastosowania zawsze można uniknąć i myślę, że zostanie uzgodnione, że dwuwymiarowy charakter papieru nie jest niezbędny do obliczeń. Zakładam, że obliczenia są wykonywane na papierze jednowymiarowym, tj. Na taśmie podzielonej na kwadraty.

Chociaż komputer nie jest już zajęciem, ostatnim razem, gdy sprawdzałem, dzieci uczyły się wykonywania algorytmów za pomocą ołówka i papieru jako nośnika pamięci. Tak więc, chociaż ta analogia może wydawać się staromodna, a nawet archaiczna, nie jest jeszcze przestarzała.

Aby uzyskać więcej informacji, zobacz Liczby obliczalne z zastosowaniem do entscheidungsproblem , zwłaszcza w sekcjach 1 i 9.

@jkff ma pomysł, że the Turing Machine is modeled on the idea of a human with a pen and papernie jest całkowicie poprawny. Ale jest wiele sytuacji, w których można to uznać za prawidłowe.

Pomyśl o człowieku jako maszynie Turinga pod pewną projekcją stanów. Innymi słowy, jeśli widzisz człowieka tylko podczas jego godzin pracy, wtedy podczas jego godzin pracy wykonuje pewne zadania. Te zadania są podstawowymi zadaniami dla zadania.

Jeśli nie obchodzi cię jego życie osobiste, to, co robi w domu, w swoim pokoju itp., Możesz to uznać za rzutowanie jego funkcji przejścia na nową funkcję przejścia, w której stany niezwiązane z pracą są ignorowane. Innymi słowy, możesz pominąć wszystkie stany i zadania, które nie mają nic wspólnego z twoją troską i perspektywą.

W tym modelu maszyna Turinga jest modelowana po człowieku za pomocą pióra, papier wykonujący ustalone zadanie (tj. Widok w ustalonej perspektywie). Taśma zapisuje na papierze (ignorując wszystkie papiery lub pisząc na papierze, którego nie pisze dla zadania)

Teraz, jeśli weźmiecie pod uwagę inne zadania, które on wykonuje, wówczas macie połączenie wielu maszyn Turinga u człowieka. Ale co jeśli zmieni pracę i wykona inne zadanie. Następnie jego stan mózgu zmienia się na inną maszynę Turinga, gdy patrzy się z innej perspektywy w różnych ramach czasowych.

Jeśli chcesz dobrą odpowiedź na swoje pytanie, myślę, że Yuval Filmus odpowiedział na nie dobrze. Użyj modelu RAM. Trzymać się tego.