Wypełniając lukę między abstrakcyjnymi maszynami a komputerowymi osiągnięciami? [Zamknięte]

Zawsze czuję się odłączony między maszynami abstrakcyjnymi (takimi jak maszyny Turinga) a architekturami komputerowymi (w tym architekturami maszyn wirtualnych, achitektem von Neumanna). Chciałbym wiedzieć, w jaki sposób są one powiązane? Jak jedno wpływa na drugie? Doceniamy również referencje. Dzięki.

Maszyny Turinga i podobne „maszyny” są modelami obliczeniowymi , mają one na celu zbadanie takich problemów, jak:

• Co można obliczyć
• Klasa złożoności problemów
• Relacje między klasami złożoności
• Równoważność różnych sposobów obliczania czegoś

W tym celu sama maszyna musi być tak prosta, jak to możliwe. Wygoda programisty lub kłopotliwe implementacje nie mają znaczenia, ponieważ są to obiekty matematyczne i tylko bardzo niewiele programów jest napisanych dla nich bezpośrednio.

I odwrotnie, architektura maszyn wirtualnych i rzeczywista architektura maszyn opartych na krzemie koncentruje się na wykonywaniu danego programu . Maszyna jest bardziej skomplikowana niż absolutnie niezbędna z powyższych powodów, a z kolei potrzeba mniej (i bardziej oczywistych) instrukcji, aby robić interesujące rzeczy. Nie zbyt skomplikowane, ponieważ nadal muszą być zrozumiałe (i skutecznie wykonalne), ale bardziej skomplikowane.

Te dwa podejścia są zasadniczo sprzeczne. Poza tym, że oba są w dziedzinie informatyki, nie mają ze sobą wiele wspólnego.

Główny związek polega na tym, że można symulować konstrukcję teoretyczną w fizycznym.

Fakt, że fizyczny jest zdolny do wszystkich rzeczy teoretycznych, powoduje, że teoretyczne testy i analizy teoretycznej maszyny można uznać za możliwe do wdrożenia w świecie rzeczywistym.

Problem zatrzymania jest doskonałym przykładem czegoś, co zostało pokazane na maszynie Turinga jako nierozwiązywalne, a przez dowód na maszynie Turinga można zatem stwierdzić, że jest nierozwiązywalne na prawdziwej maszynie, która przestrzega praw maszyny Turinga.

Jest to różnica między sumowaniem rzeczy przez liczenie a robieniem tego przez pisanie na papierze. Udowodniono, że rzeczywistość liczenia spełnia te same zasady, co sumowanie na kawałku papieru. Więc kiedy symulujesz fizyczne liczenie rzeczy, twoje wyniki są uznawane za mające zastosowanie w prawdziwym świecie - dzięki czemu wiesz, ile kosztują dwa batoniki, mentalnie symulując liczenie, bez konieczności liczenia fizycznych pieniędzy, aby uzyskać wynik.

Obecnie ludzie pracują nad analizą i testowaniem modelu teoretycznego zwanego „maszyną do kwantowego Turinga”, aby sprawdzić, jakie udogodnienia będą dostępne w maszynach do obliczeń kwantowych. Ma sens, aby ludzie pracowali z tymi modelami, gdy fizyczna wersja ich modelu jest zarówno zbyt droga, jak i rzadka, a obecnych implementacji wciąż brakuje. Modele teoretyczne służą do pokazania, co możemy zrobić, gdy poprawimy nasze fizyczne wdrożenia.

Są one powiązane mniej więcej tak samo, jak prom kosmiczny jest związany z balonem, który nadmuchujesz oddechem, a następnie puszczasz i patrzysz, jak odlatuje.

Istnieje podstawowa zasada wyrzucania czegoś w jednym kierunku, aby napędzać coś w przeciwnym kierunku.

Tam kończą się podobieństwa.

Widzę maszyny teoretyczne jako wypełniające lukę między obliczeniami w świecie rzeczywistym a matematyką. Maszyna Turinga jest wystarczająco potężna, aby symulować dowolną architekturę lub język programowania, wystarczająco prostą, aby można ją było łatwo symulować, a co najważniejsze, wystarczająco prostą, aby stać się przedmiotem racjonalnie prostych rozumowań matematycznych i dowodów.

Ważne jest, aby wiedzieć, że definicja obliczeń nie obejmuje „tych rzeczy, które robią komputery”. Obliczenia sprzed komputerów. Komputery otrzymały swoją nazwę, ponieważ zostały stworzone, aby pomóc w obliczeniach, a nie dlatego, że je definiują.

Maszyna Turinga nie polega na tym, jak działają komputery. Chodzi o to, czy problem jest obliczalny - to znaczy, że można go rozwiązać za pomocą formalnego procesu logicznego / matematycznego. Nie mówi nic o tym, jak ten proces może zostać wdrożony. Jeśli jest to obliczalne, może być rozwiązane przez ludzi za pomocą ołówków i papieru, mając wystarczająco dużo czasu, lub za pomocą komputerów lub (to jest ważne) za pomocą dowolnego systemu, który może być ukończony przez Turinga .

Maszyna Turinga wykonuje dwie bardzo ważne rzeczy:

1. Zapewnia test obliczalności dowolnego problemu / zadania.
2. Udostępnia test dla dowolnego systemu, aby pokazać, czy może obliczyć dowolne zadanie obliczeniowe.

Pierwszy punkt pozwala nam myśleć o problemach bez rozpraszania się rzeczywistymi implementacjami. Jest to dobre, ponieważ prawdziwy sprzęt często rozprasza uwagę ludzi nieistotnymi szczegółami (np. „Co się stanie, jeśli zabraknie pamięci lub miejsca do przechowywania?”, Ponieważ maszyny Turinga mają nieskończone zasoby). Sprawdzone rozwiązanie teoretyczne można opracować dla maszyny Turinga, a następnie wszystko, co trzeba zrobić, to przełożyć ją na coś, co zadziała na danej architekturze.

Drugi punkt pozwala nam zweryfikować możliwości dowolnej implementacji bez konieczności przeprowadzania na niej wielu różnych testów. Jeśli może symulować Maszynę Turinga, może zrobić wszystko, co Maszyna Turinga może zrobić. Ponieważ maszyny Turinga mogą obliczyć wszystko, co można obliczyć, to i on.

Co oznacza, że ​​związek między Maszyną Turinga a jakąkolwiek naprawdę praktyczną architekturą komputerową (nawet wirtualną) to tylko jedno: potrafią obliczać.

Architektura Von Neumanna była próbą stworzenia szablonu projektu dla efektywnych elektronicznych komputerów ogólnego przeznaczenia . Praca Turinga dostarczyła dowodu jej ważności

Jeśli się nad tym zastanowić, architektury to abstrakcyjne maszyny. Opisują, jak powinien zachowywać się kawałek starannie wykonanego krzemu. Różnica między architekturą a maszynami Turinga jest bardziej kwestią skali niż zasadniczej zmiany podejścia.

Zaletą maszyn Turinga jest to, że istnieje zestaw przydatnych dowodów, które są bardzo łatwe do wykonania przy użyciu maszyny Turinga. Łatwo jest udowodnić, że każda maszyna wystarczająco mocna, aby symulować maszynę Turinga, może rozwiązać każdy problem, który może ona zrobić (duh). Jednak staje się bardziej interesujące, gdy zdefiniujesz funkcję obliczalną . Okazuje się, że istnieje wiele zgodnych definicji funkcji obliczalnej. Jeśli potrafisz zdefiniować wszystkie swoje zachowania jako funkcje obliczalne, możesz być symulowany w maszynie Turinga.

Powiedzmy, że masz architekturę, która bezpośrednio obsługuje programy w stylu LISP, a inną, taką jak x86, która jest bardziej proceduralna. Twój przyjaciel twierdzi, że „LISP jest bardziej ekspresyjny, więc możesz pisać programy na tym komputerze, których nigdy nie możesz pisać na swoim x86”. Jest to brutalne, aby temu zaradzić (zwłaszcza, że ​​prawdopodobnie nie znasz wystarczająco dużo LISP). Można jednak nadużywać kilka abstrakcyjnych maszyn, takich jak maszyna Turinga:

• Twoja maszyna LISP może być fantazyjna, ale wszystko, co może zrobić, można sprowadzić do rachunku lambda. Twój przyjaciel chętnie kiwa głową. Rachunek lambda to kultowa rzecz dla programistów funkcjonalnych.
• Mój x86 może być fantazyjny, ale wszystko, co może zrobić, można zredukować do maszyny rejestrującej. Jeszcze raz, żadne pytanie od twojego przyjaciela. Rejestry są SO we współczesnej teorii komputerów!
• Dowolną maszynę rejestrującą można modelować jako maszynę Turinga symulującą tę maszynę rejestrującą. Teraz twój przyjaciel zastanawia się, dlaczego wracasz do ery taśm.
• A twoją maszynę do rachunku lambda można również zredukować do maszyny Turinga. * Twój przyjaciel sprzeciwia się, ale wskazujesz go na tezę Turinga Kościoła, a oni zawstydzają głowę.
• Tak więc moje pudełko x86 może zrobić wszystko, co może zrobić Twoja wymyślna maszyna oparta na LISP!

Istnieje oczywiście wiele innych przykładów. Udowodniono, że gra Conway Game of Life jest ukończona, co oznacza, że ​​teoretycznie może zrobić wszystko, co może zrobić komputer. Najłatwiejszym sposobem na to było zbudowanie maszyny Turinga w życiu . Mówię o tym, ponieważ byłby to przypadek, który nazwałeś abstrakcyjną maszyną traktowaną jako dosłowna architektura! Możesz sobie wyobrazić, jak trudne byłoby twierdzenie o obliczalności w Life bez pomocy abstrakcyjnych modeli (jestem pewien, że do cholery nie modeluję x64, wraz z podglądaniem pamięci podręcznej, tylko po to, aby udowodnić, że Życie jest obliczalne!)

Ostatecznie duża różnica między architekturami a maszynami abstrakcyjnymi polega na tym, że architektury zwykle zajmują się wydajnością. Architekci chcą wiedzieć, jak szybko możesz coś zrobić. Maszyny abstrakcyjne zazwyczaj zadowalają się wiedzą, czy potrafisz. Zastanów się nad Universal Constructor opracowanym dla automatów stanowych von Neumana. To wystarczyło, aby udowodnić, że UC może działać, nieważne jednak, że autorzy nigdy nie mieli wystarczającej mocy obliczeniowej, aby to przejrzeć.

Architekci cen płacą za wykazanie, jak szybko potrafią pracować, ponieważ często bardzo trudno jest udowodnić, że potrafią wszystko obliczyć . W tym celu architektury skręcają w prawo i zaczynają korzystać z abstrakcyjnych maszyn.