Praktyczne znaczenie maszyn Turinga?

Jestem inżynierem elektrykiem i 26 lat temu miałem tylko jeden kurs CS na studiach. Jednak jestem również oddanym użytkownikiem Mathematica.

Mam wrażenie, że maszyny Turinga są bardzo ważne w informatyce. Czy znaczenie ma tylko w teorii informatyki? Jeśli istnieją praktyczne implikacje / zastosowania, jakie są niektóre z nich?

Znaczenie maszyn Turinga jest dwojakie. Po pierwsze, maszyny Turinga była jedna z pierwszych (jeśli nie jest to pierwsze) modele teoretyczne komputerów, pochodzący z 1936 roku drugie, dużo teoretycznej informatyki został opracowany z myślą o maszynach Turinga, a tak wiele z podstawowych wyników są w języku maszyn Turinga. Jednym z powodów jest to, że maszyny Turinga są proste i dlatego nadają się do analizy.

To powiedziawszy, maszyny Turinga nie są praktycznym modelem dla komputerów. Jako inżynier i użytkownik Mathematica w ogóle nie powinni cię martwić. Nawet w teoretycznej społeczności informatycznej bardziej realistyczne maszyny RAM są używane w obszarach algorytmów i struktur danych.

W rzeczywistości, z punktu widzenia teorii złożoności, maszyny Turinga są wielomianowo równoważne z wieloma innymi modelami maszyn, a zatem klasy złożoności, takie jak P i NP, można równoważnie zdefiniować w kategoriach tych modeli. (Inne klasy złożoności są delikatniejsze).

Maszyny Turinga były jednym z pierwszych modeli obliczeń, to znaczy zostały opracowane, gdy samo obliczenia nie były dobrze rozumiane (około 1940 r.). Chcę skupić się na dwóch aspektach, które (prawdopodobnie) doprowadziły do ​​tego, że były wówczas preferowanym modelem, co doprowadziło do tego, że stały się najbardziej ugruntowanym, a zatem ostatecznie standardowym modelem.

1. Prostota dowodów
   Jako model teoretyczny maszyny Turinga mają urok „prostoty” w tym sensie, że obecny stan maszyny ma tylko stały rozmiar. Wszystkie informacje potrzebne do ustalenia następnego stanu maszyny to jeden symbol i jeden (kontrolny) numer stanu. Zmiana stanu maszyny jest równie niewielka, dodając jedynie ruch głowicy maszyny. To znacznie upraszcza (formalne) dowody, w szczególności liczbę spraw, które należy rozróżnić.

   Porównaj ten aspekt z modelem RAM (gdy nie jest używany w minimalistycznej formie): następna operacja może być dowolną z kilku operacji, które mogą uzyskać dostęp do dowolnego (dwóch) rejestrów. Istnieje również wiele struktur kontrolnych.

2. 
   $\lambda$$\mu$

   Jednak w przypadku maszyn Turinga oba pojęcia są łatwe do zdefiniowania (i były w pierwszej pracy Turinga na temat jego modelu, jeśli dobrze pamiętam). Ponieważ względy wydajności wkrótce stały się bardzo ważne przy robieniu rzeczy, była to zdecydowana zaleta maszyn Turinga.

Zatem, maszyny Turinga zostały ustalone jak w modelu obliczeń, które mogłyby być postrzegane jako połączenie historycznej „wypadek”, a niektóre z jego kluczowych właściwości. Niemniej jednak wiele modeli zostało już zdefiniowanych i są chętnie stosowane, w szczególności w celu przezwyciężenia wad maszyn Turinga; na przykład nużące są „programowanie” (tj. definiowanie).

W praktyce nie znam żadnych bezpośrednich aplikacji. W szczególności praktyka obliczeń ewoluowała równolegle (i na początku głównie niezależnie od) teorii obliczeń. Języki programowania zostały opracowane bez formalnych modeli maszyn. Jest jednak jasne (z perspektywy czasu), że wiele postępów w praktyce obliczeń było możliwe dzięki teorii.

Ponadto należy pamiętać, że wartość koncepcji teoretycznej dla praktyki należy mierzyć, biorąc pod uwagę wszystkich potomków, to znaczy kontynuację pracy, wyniki i nowe pomysły możliwe dzięki tej koncepcji. I w tym względzie uważam, że słusznie jest powiedzieć, że koncepcja maszyn Turinga (między innymi) zrewolucjonizowała świat.

Jedynym względnie praktycznym zastosowaniem, o jakim mogę pomyśleć (w tym sensie, że faktycznie możesz wdrożyć maszynę Turinga), jest udowodnienie, że jakiś język ma wystarczającą moc.

Jeśli projektujesz jakiś język programowania (lub cokolwiek innego, co ma na celu obliczanie rzeczy), możesz chcieć upewnić się, że jest on kompletny w Turingu (tj. Jest w stanie obliczyć wszystko, co jest obliczalne) poprzez wdrożenie maszyny Turinga w tym.

Oczywiście można również zaimplementować wszystko inne, co jest kompletne Turinga (jak C lub logika kombinacyjna), ale czasami maszyna Turinga jest najłatwiejszą opcją.

Maszyna Turinga jest matematycznym modelem obliczeń. Jego zalety to:

1. Sprawdź rozstrzygalność Jeśli TM nie może rozwiązać problemu w odliczalnym czasie, nie może istnieć żaden algorytm, który mógłby rozwiązać ten problem (to znaczy, że problem jest nierozstrzygalny).

W przypadku problemu decyzyjnego, jeśli jego TM zatrzyma się w zliczalnym czasie dla wszystkich danych wejściowych o skończonej długości, możemy powiedzieć, że problem można rozwiązać za pomocą algorytmu w zliczalnym czasie.

2. Klasyfikuj problem TM pomaga klasyfikować rozstrzygalne problemy na klasy wielomianowej hierarchii.

Załóżmy, że stwierdziliśmy, że problem jest rozstrzygalny. Wtedy naszym celem staje się, jak skutecznie możemy go rozwiązać. Wydajność obliczono w liczbie kroków, wykorzystanej dodatkowej przestrzeni, długości kodu / rozmiaru FSM.

3. Projektowanie i wdrażanie algorytmu dla praktycznych maszyn TM pomaga propagować ideę algorytmu w innych praktycznych maszynach. Po pomyślnym sprawdzeniu 1,2 kryteriów możemy wykorzystać nasze praktyczne urządzenia / komputery do zaprojektowania i wdrożenia algorytmu.

Maszyny Turinga to ćwiczenia umysłowe przy niewielkim praktycznym zastosowaniu. Nie ma nic złego w tym, że go nie ma. Wszystkie zastosowania maszyny Turinga są intuicyjne lub religijne, ponieważ nie można ich udowodnić ani obalić.