Prawdziwe komputery mają tylko skończoną liczbę stanów, więc jakie jest znaczenie maszyn Turinga dla prawdziwych komputerów?

Prawdziwe komputery mają ograniczoną pamięć i tylko skończoną liczbę stanów. Są to w zasadzie skończone automaty. Dlaczego informatycy teoretyczni używają maszyn Turinga (i innych równoważnych modeli) do badania komputerów? Jaki jest sens studiowania tych znacznie silniejszych modeli w odniesieniu do prawdziwych komputerów? Dlaczego model automatów skończonych nie wystarczy?

Rozważając to pytanie, istnieją dwa podejścia: historyczne dotyczące sposobu odkrywania pojęć i techniczne, które wyjaśniają, dlaczego niektóre pojęcia zostały przyjęte, a inne porzucone, a nawet zapomniane.

Historycznie Maszyna Turinga jest być może najbardziej intuicyjnym modelem kilku opracowanych prób odpowiedzi na Entscheidungsproblem . Jest to ściśle związane z wielkim wysiłkiem podejmowanym w pierwszych dekadach XX wieku w celu całkowitej aksjatyzacji matematyki. Nadzieja polegała na tym, że gdy udowodnisz, że mały zestaw aksjomatów jest poprawny (co wymagałoby znacznego wysiłku), możesz następnie zastosować systematyczną metodę, aby uzyskać dowód na logiczne stwierdzenie, które Cię interesuje. Nawet jeśli ktoś uznałby za skończone automaty w tym kontekście zostaną szybko zwolnieni, ponieważ nie obliczą nawet prostych funkcji.

Technicznie stwierdzenie, że wszystkie komputery są automatami skończonymi, jest fałszywe. Automat skończony ma stałą pamięć, której nie można zmienić w zależności od wielkości wejścia. Nie ma żadnych ograniczeń, ani w matematyce, ani w rzeczywistości, które uniemożliwiały dostarczenie dodatkowej taśmy, dysków twardych, pamięci RAM lub innych form pamięci po użyciu pamięci w maszynie. Wierzę, że często stosowano to we wczesnych dniach obliczeń, kiedy nawet proste obliczenia mogły wypełnić pamięć, podczas gdy teraz w przypadku większości problemów i przy nowoczesnej infrastrukturze, która pozwala na znacznie bardziej wydajne zarządzanie pamięcią, w większości przypadków nie stanowi to problemu .

EDYCJA: Rozważyłem obie kwestie poruszone w komentarzach, ale postanowiłem nie uwzględniać ich zarówno zwięzłości, jak i czasu, który miałem na zanotowanie odpowiedzi. Oto moje rozumowanie, dlaczego uważam, że te punkty nie zmniejszają skuteczności maszyn Turinga w symulacji współczesnych komputerów, szczególnie w porównaniu do automatów skończonych:

• Pozwól mi najpierw zająć się fizycznym problemem ograniczenia pamięci przez wszechświat. Po pierwsze, tak naprawdę nie wiemy, czy wszechświat jest skończony, czy nie. Co więcej, koncepcja obserwowalnego wszechświata, który z definicji jest skończony, jest również z definicji nieistotna dla użytkownika, który może podróżować do dowolnego punktu obserwowalnego wszechświata w celu wykorzystania pamięci. Powodem jest to, że obserwowalny wszechświat odnosi się do tego, co możemy obserwować z określonego punktu, a mianowicie Ziemi, i byłoby inaczej, gdyby obserwator mógł podróżować w inne miejsce we wszechświecie. Zatem wszelka argumentacja dotycząca obserwowalnego wszechświata przechodzi w kwestię skończoności wszechświata. Załóżmy jednak, że poprzez jakiś przełom zdobywamy wiedzę, że wszechświat jest rzeczywiście skończony. Chociaż miałoby to ogromny wpływ na kwestie naukowe, Wątpię, by miałoby to jakikolwiek wpływ na korzystanie z komputerów. Mówiąc najprościej, może być tak, że w zasadzie komputery są rzeczywiście automatami skończonymi, a nie maszynami Turinga. Ale dla większości obliczeń i najprawdopodobniej każdego obliczenia, którym ludzie są zainteresowani, maszyny Turinga i powiązana teoria oferują nam lepsze zrozumienie. W prostym przykładzie, chociaż wiemy, że fizyka newtonowska jest zasadniczo błędna, wątpię, aby inżynierowie mechanicy używali przede wszystkim fizyki kwantowej do projektowania samochodów lub maszyn fabrycznych; przypadki narożne, w których jest to potrzebne, można rozpatrywać na poziomie indywidualnym. Ale dla większości obliczeń i najprawdopodobniej każdego obliczenia, którym ludzie są zainteresowani, maszyny Turinga i powiązana teoria oferują nam lepsze zrozumienie. W prostym przykładzie, chociaż wiemy, że fizyka newtonowska jest zasadniczo błędna, wątpię, aby inżynierowie mechanicy używali przede wszystkim fizyki kwantowej do projektowania samochodów lub maszyn fabrycznych; przypadki narożne, w których jest to potrzebne, można rozpatrywać na poziomie indywidualnym. Ale dla większości obliczeń i najprawdopodobniej każdego obliczenia, którym ludzie są zainteresowani, maszyny Turinga i powiązana teoria oferują nam lepsze zrozumienie. W prostym przykładzie, chociaż wiemy, że fizyka newtonowska jest zasadniczo błędna, wątpię, aby inżynierowie mechanicy używali przede wszystkim fizyki kwantowej do projektowania samochodów lub maszyn fabrycznych; przypadki narożne, w których jest to potrzebne, można rozpatrywać na poziomie indywidualnym.

• Wszelkie ograniczenia techniczne, takie jak autobusy i adresowanie, są po prostu ograniczeniami technicznymi istniejącego sprzętu i można je przezwyciężyć fizycznie. Nie jest to prawdą w przypadku obecnych komputerów, ponieważ adresowanie 64-bitowe pozwoliło nam przesunąć górną granicę przestrzeni adresowej na wysokość kilku, jeśli jakiekolwiek aplikacje mogą to osiągnąć. Ponadto wdrożenie „rozszerzalnego” systemu adresowania może potencjalnie mieć wpływ na samą większość obliczeń, które nie będą go potrzebować, a zatem jego nieefektywność. Nic nie stoi na przeszkodzie, aby zorganizować hierarchiczny system adresowania, np. Dla dwóch poziomów pierwszy adres może odnosić się do dowolnego z banków pamięci a następnie każdy bank ma$2^{64}$$2^{64}$różne adresy. Zasadniczo tworzenie sieci to świetny sposób na to, ponieważ każda maszyna dba tylko o swoją pamięć lokalną, ale może obliczać razem.

Aby uzupełnić pozostałe odpowiedzi: Myślę, że Maszyna Turinga jest lepszą abstrakcją tego, co robią komputery, niż automatami skończonymi. Rzeczywiście, główna różnica między tymi dwoma modelami polega na tym, że w przypadku automatów skończonych oczekujemy traktowania danych, które są większe niż przestrzeń stanu, a Maszyna Turinga jest modelem na odwrót (przestrzeń stanu >> dane), tworząc stan przestrzeń nieskończona. Ta nieskończoność może być postrzegana jako abstrakcja „bardzo dużego przed wielkością danych”. Pisząc program komputerowy, próbujesz zaoszczędzić miejsce na wydajności, ale ogólnie zakładasz, że nie będziesz ograniczany przez całkowitą ilość miejsca na komputerze. Jest to jeden z powodów, dla których maszyny Turinga są lepszą abstrakcją komputerów niż automatów skończonych.

W komentarzach Andrej Bauer podał jeden ważny powód:

Ponieważ czasami jest lepszym przybliżeniem do niż .10000000000000000000000000000000 $\infty$$10000000000000000000000000000000$$10000000000000000000000000000000$

Pozwolę sobie uzupełnić pozostałe odpowiedzi niektórymi punktami, które prawdopodobnie były zbyt oczywiste, aby je wymienić:

• Jeśli Twoim celem jest badanie prawdziwych komputerów, to zarówno automaty skończone, jak i maszyny Turinga będą często zbyt prostymi modelami dla odpowiednich pytań. Prawdziwe komputery mają wiele rdzeni przetwarzających z hierarchią pamięci podręcznej (lub innym inteligentnym schematem zarządzania), dostępem do przyzwoitej ilości szybkiej pamięci, dostępem do ogromnej ilości wolnej pamięci zewnętrznej (dysków twardych) i mogą komunikować się z innymi podobnymi komputerami prędkość w przybliżeniu porównywalna z prędkością dostępu do wolnej pamięci zewnętrznej.
• Jeśli teraz zadajesz sobie pytanie, dlaczego potrzebujesz tych wszystkich szczegółów, okazuje się, że Twoim prawdziwym celem jest badanie instancji problemów i skuteczność ich rozwiązywania. Jeśli mówisz o prawdziwych komputerach, może to również oznaczać, że przeprowadzasz eksperymenty z rzeczywistymi instancjami problemów na różnych typach (prawdziwych) architektur komputerowych.
• Opisany powyżej model prawdziwych komputerów jest wciąż idealizowany, ponieważ ignoruje różne tryby awarii prawdziwych komputerów. Ponieważ awaria zasilania może występować częściej niż awaria dysku twardego (a dyski twarde i tak mogą mieć kopie zapasowe), niektóre domeny problemowe, takie jak niezawodne działanie bazy danych, mogą wymagać wzięcia tego pod uwagę.
• Jeśli teraz zaakceptujemy, że klasy problemów i instancje problemowe są tym, co naprawdę nas interesuje, to maszyny Turinga (a także automaty skończone) stają się matematycznymi (i językowymi) narzędziami do przedstawiania (i potwierdzania) interesujących propozycji dotyczących klas problemów i instancji problemów. Przykładowo, konkretny przykład problem może być Riemanna Hipoteza i założenie o tym to, że jest to równoważne z zdaniu$\Pi_1^0$ .

Formalizm jest przydatny lub nie, w oparciu o to, co ludzie chcą wykorzystać formalizm do modelowania i rozumienia.

Maszyna Turinga to formalizm przydatny do zrozumienia programów . Programy są warte zrozumienia; większość faktycznych obliczeń jest wykonywana przez programy, a nie przez maszyny specjalnego przeznaczenia. Formalizm maszyny Turinga pozwala nam modelować ważne problemy w świecie rzeczywistym, takie jak złożoność czasu i przestrzeni. O wiele mniej naturalne jest badanie tych pojęć za pomocą automatów skończonych.

Maszyny Turinga nie są zbyt przydatne, gdy próbujemy zbadać złożoność obliczania funkcji skończonych (powiedzmy funkcje, których domena składa się z danych wejściowych o długości co najwyżej 10 milionów). Złożoność obwodów jest znacznie lepsza w opisywaniu złożoności funkcji skończonych ... ale z kolei maszyny Turinga były bardzo przydatne w zrozumieniu złożoności obwodów.

Automaty skończone były również przydatne w zrozumieniu złożoności obwodu; wszystkie te modele mają swoje miejsce w arsenale matematycznym.

Odrzucam argument, że automaty skończone są lepszym modelem rzeczywistości wyłącznie dlatego, że komputery świata rzeczywistego mają tylko skończoną liczbę stanów wewnętrznych. Badanie automatów skończonych zasadniczo zajmuje się danymi wejściowymi pochodzącymi z nieskończonego zestawu ciągów, podczas gdy komputery w świecie rzeczywistym radzą sobie z danymi wejściowymi o określonej stałej maksymalnej długości (chyba że uważasz, że żyjemy w nieskończonym wszechświecie, albo pod względem przestrzeni lub czas).

Model należy oceniać pod kątem jego użyteczności w zrozumieniu tych aspektów rzeczywistości, na których nam zależy. Lub (alternatywnie) pod względem użyteczności w rozumieniu wszechświata matematycznego, który ludzie uważają za wystarczająco przekonujący, nawet jeśli ten wszechświat matematyczny nie ma oczywistych przejawów fizycznych.

Maszyny Turinga, maszyny o stanie skończonym oraz obwody (i inne modele oprócz tego) sprawdziły się.

Rzeczywiste komputery nie są FSA. Rzeczywisty komputer to komputer uniwersalny w tym sensie, że możemy opisać komputer, który ma być emulowany, a komputer będzie go emulował. Aby znaleźć wiele przykładów, wyszukaj „maszynę wirtualną”.

Możliwe jest zbudowanie Uniwersalnej Maszyny Turinga - TM, która otrzymuje opis innej TM, a następnie emuluje działanie tej TM na dostarczonym wejściu.

$n$$2^{2^n}$

Jako punkt wyjścia do literatury mogę polecić „ O istnieniu uniwersalnych automatów skończonych lub wypychających ”, który bada nieistnienie automatów uniwersalnych. Możesz także spojrzeć na jego odniesienia (i tak dalej).

To, co wyróżnia maszynę Turinga, to to, że będąc bardzo, bardzo prostym, może uruchamiać wszystkie (klasy) algorytmy, o których możemy myśleć. Nie ma znanej maszyny, która byłaby bardziej wydajna (ponieważ mogłaby obsługiwać algorytmy, do których nie jest zdolna maszyna Turinga).

Będąc mechanicznie prostym, łatwo jest wykazać, czy lub w jakim stopniu inne maszyny są równoważne maszynie Turinga. To z kolei sprawia, że ​​stosunkowo łatwo jest wykazać, czy dany komputer (lub język komputera) jest naprawdę uniwersalny (c / f „Turing-complete”).

Dlaczego model automatów skończonych nie wystarczy?

Podczas gdy inne odpowiedzi wspominały już o wielu istotnych aspektach, uważam, że główną zaletą maszyn Turinga nad automatami skończonymi jest separacja danych i programów . Pozwala to analizować dość skończony program i wypowiadać się na temat tego, jak program ten obsługiwałby różne dane wejściowe, bez ograniczania rozmiaru danych wejściowych.

Chociaż teoretycznie można opisać zarówno rzeczywisty komputer, jak i maszynę Turinga z taśmą skończoną jako maszynę stanu, nie jest to tak naprawdę wykonalne: liczba stanów jest wykładnicza w ilości pamięci, jaką ma maszyna, i ogólnie skończonej formalizm automatu państwowego wymaga wyraźnego wyszczególnienia przejść między tymi stanami. Tak więc w przypadku ogólnego automatu stanu skończonego o tej wielkości dokonywanie jakichkolwiek dedukcji na podstawie pełnego wyliczenia wszystkich przejść stanu jest całkiem niemożliwe.

Oczywiście na prawdziwym komputerze zmiany stanów nie mogą się zdarzyć arbitralnie. Nie ma polecenia zamiany jednej trzeciej bitów w pamięci w jednym kroku obliczeń. Możesz więc spróbować opracować bardziej zwartą specyfikację przejść stanu. Coś w rodzaju specyfikacji zestawu instrukcji dla twojej architektury. Oczywiście rzeczywiste architektury komputerów są skomplikowane ze względu na wydajność, więc można to jeszcze bardziej uprościć, tworząc bardzo prosty zestaw instrukcji, który wykonuje tylko bardzo małe kroki przy bardzo ograniczonym wejściu i wyjściu. W końcu może się okazać, że twoja architektura przypomina coś w rodzaju interpretera maszyny Turinga: używając kawałków kodu programu i jednego bitu danych wejściowych, wygeneruj trochę danych wyjściowych i poruszaj się w kodzie programu.

Alternatywą byłoby użycie stanów automatu stanu skończonego tylko do przedstawienia danych przetwarzanych przez program, przy jednoczesnym kodowaniu samego programu w stanach przejściowych. To pociągałoby za sobą ten sam problem, jak wyliczyć wszystkie stany, a zwarta reprezentacja może znów być zbliżona do tego, co robi maszyna Turinga.

Jaki jest sens studiowania tych znacznie silniejszych modeli w odniesieniu do prawdziwych komputerów?

Ogólnie rzecz biorąc, powiedziałbym, że maszyna Turinga ze skończoną taśmą byłaby prawdopodobnie lepszym modelem dla rzeczywistych komputerów. Jednak w przypadku wielu pytań naukowych rozróżnienie między skończoną, ale dużą i nieskończoną taśmą jest nieistotne, więc samo twierdzenie, że nieskończona taśma ułatwia. W przypadku innych pytań najważniejsza jest ilość zastosowanej taśmy, ale model z łatwością pozwala mówić o ilości zużytej taśmy bez konieczności określania, co się stanie, jeśli w obliczeniach zabraknie taśmy.

Większość problemów wymaga maszyn Turinga o skończonych rozmiarach

Chociaż założenie, że nieograniczona taśma jest użytecznym uproszczeniem, większość problemów / algorytmów w rzeczywistości wymaga skończonej ilości taśmy, a granice wymaganej pamięci (być może w zależności od rozmiaru wejścia) można analizować i często dowodzić.

Często uogólnia to również na inne typy komputerów (dla których związana analiza lub dowód może być znacznie bardziej nieporządny niż na maszynie Turinga) i pozwala oszacować ilość tymczasowej pamięci wymaganej dla konkretnego problemu - czy można to zrobić w określonej ilości przestrzeni? Proporcjonalny do wkładu? Czy wymaga to wykładniczej ilości miejsca w miarę wzrostu nakładów?

Jedną ważną cechą maszyn Turinga, których nie dzielą automaty skończone, jest to, że mogą skalować ilość pamięci potrzebnej do rozwiązania problemu wraz z rozmiarem problemu .

$n$$n\cdot2$

Chodzi o to, że wiele problemów ma naturalne rozwiązania, które zużywają więcej pamięci, im większy jest problem. Naturalne jest zatem opisywanie tych rozwiązań za pomocą reprezentacji, które mogą korzystać z nieskończonej pamięci - nie dlatego, że każde wystąpienie użyje nieskończonych ilości, ale dlatego, że istnieje instancja, która wykorzystuje każdą ilość. Możesz to zrobić za pomocą maszyn Turinga, ale także za pomocą sekwencji automatów skończonych.

Prawdziwe komputery mają ograniczoną pamięć i tylko skończoną liczbę stanów. Są to w zasadzie skończone automaty.

Maszyny Turinga są pochodnymi automatów skończonych. Maszyny Turinga są praktycznie architekturą von Nuemann.