W skrócie :
To, co charakteryzuje imperatywne języki programowania jako bliskie maszynom Turinga i zwykłym komputerom, takim jak komputery PC (same w sobie bardziej zbliżone do maszyn o swobodnym dostępie (RAM) niż do maszyn Turinga) to koncepcja jawnej pamięci, którą można modyfikować w celu przechowywania (wyniki pośrednie ). Jest to widok obliczeń automatów z koncepcją stanu (obejmującego zarówno kontrolę stanu skończonego, jak i zawartość pamięci), która może się zmieniać w trakcie obliczania.
Większość innych modeli jest bardziej abstrakcyjna. Chociaż mogą wyrażać obliczenia jako kolejne etapy transformacji oryginalnej struktury, transformacje te są stosowane w pewnego rodzaju wewnętrznym wszechświecie znaczeń matematycznych. Może to zachować właściwości, takie jak przejrzystość referencyjna, które mogą uprościć analizę matematyczną. Ale jest bardziej odległy od naturalnych modeli fizycznych, które opierają się na konkludowaniu pamięci.
W związku z tym nie ma naturalnych funkcjonalnych maszyn, chyba że w szerszym znaczeniu, jak wyjaśniono poniżej, ponieważ oprogramowania nie da się tak naprawdę oddzielić od sprzętu.
Odwołanie się do Turinga jako kryterium obliczalności wynika prawdopodobnie z faktu, że jego model, maszyna Turinga była najbliższa temu ograniczeniu fizycznej wykonalności, co czyniło go bardziej intuicyjnym modelem obliczeń.
Dalsze uwagi :
Istnieje wiele modeli obliczeń, które zostały zaprojektowane tak, aby uchwycić w jak najogólniejszy sposób koncepcję obliczeń. Należą do nich maszyny Turinga, w rzeczywistości w wielu różnych smakach, rachunek lambda (także smaki), systemy przepisywania semi-Thue, funkcja częściowej rekurencji, logika kombinacyjna.
Wszystkie zawierają niektóre aspekty różnych technik stosowanych przez matematyków do wyrażania lub przeprowadzania obliczeń. I większość z nich była do pewnego stopnia wykorzystywana jako podstawa do projektowania języka programowania (np. Snobol do przepisywania systemów, APL do kombinacji, Lisp / Scheme do rachunku lambda) i często można je łączyć na różne sposoby we współczesnych językach programowania.
Jednym z głównych rezultatów jest to, że wszystkie te modele obliczeniowe okazały się równoważne, co doprowadziło do tezy Churcha-Turinga, że żaden fizycznie wykonalny model obliczeniowy nie może zrobić więcej niż którykolwiek z tych modeli. Model obliczeniowy mówi się, że Turing jest kompletny, jeśli można udowodnić, że jest równoważny z jednym z tych modeli, a zatem równoważny z nimi wszystkimi.
Nazwa mogła być inna. Wybór maszyny Turinga (TM) jako odniesienia wynika prawdopodobnie z faktu, że jest to prawdopodobnie najprostszy z tych modeli, dokładnie naśladując (choć w uproszczeniu) sposób, w jaki człowiek oblicza i dość łatwo go wdrożyć (w ograniczonej formie skończonej) ) jako urządzenie fizyczne, do tego stopnia, że maszyny Turinga zostały zbudowane z zestawów Lego . Podstawowa idea nie wymaga matematycznego wyrafinowania. Prawdopodobnie to prostota i wykonalność modelu dały mu tę pozycję odniesienia.
W czasie, gdy Alan Turing stworzył swoje urządzenie komputerowe, pojawiły się inne propozycje, które miały służyć jako formalna definicja obliczalności, kluczowa kwestia dla podstaw matematyki (patrz
Entscheidungsproblem ). Propozycja Turinga była uważana przez ówczesnych ekspertów za najbardziej przekonującą obejmującą znane prace nad tym, jaka powinna być obliczalność (patrz Obliczalność i rekurencja , RI Soare, 1996, patrz sekcja 3.2). Różne propozycje okazały się równoważne, ale propozycje Turinga były bardziej przekonujące. [z komentarzy Yuval Filmus]
Należy zauważyć, że z punktu widzenia sprzętowego nasze komputery nie są maszynami Turinga, lecz raczej tak zwanymi maszynami o dostępie swobodnym (RAM) , które również są kompletne.
Czysto imperatywny język (cokolwiek to może znaczyć) to prawdopodobnie formalizm stosowany w najbardziej podstawowych modelach, takich jak maszyny Turinga lub język asemblera (pomijający kodowanie binarne) komputerów. Oba są notorycznie nieczytelne i bardzo trudno pisać znaczącymi programami. W rzeczywistości nawet język asemblera ma pewne funkcje wyższego poziomu, aby nieco ułatwić programowanie, w porównaniu do bezpośredniego użycia instrukcji maszynowych. Podstawowe modele imperatywne są zamknięte dla światów fizycznych, ale niezbyt przydatne.
Doprowadziło to szybko do opracowania modeli obliczeniowych wyższego poziomu, które zaczęły mieszać różne techniki obliczeniowe, takie jak podprogramy i wywołania funkcji, nazewnictwo lokalizacji pamięci, określanie nazw, kwantyfikacja i zmienne zastępcze, już używane w jakiejś formie w matematyce i logice, a nawet bardzo abstrakcyjnych pojęciach, takich jak refleksja ( Lisp 1958).
Klasyfikacja języków programowania na paradygmat programowania, taki jak imperatywny, funkcjonalny, logiczny, zorientowany obiektowo, opiera się na pierwszeństwie niektórych z tych technik w projektowaniu języka oraz obecności lub braku niektórych funkcji obliczeniowych, które wymuszają niektóre właściwości programów lub fragmenty programu napisane w języku.
Niektóre modele są wygodne dla fizycznych maszyn. Niektóre inne są wygodniejsze dla opisu algorytmów na wysokim poziomie, który może zależeć od rodzaju algorytmu, który ma zostać opisany. Niektórzy teoretycy nawet używają niedeterministycznej specyfikacji algorytmów, a nawet że cn można tłumaczyć na bardziej konwencjonalne terminy programowania. Ale nie ma problemu z niedopasowaniem, ponieważ opracowaliśmy zaawansowaną technologię kompilatora / interpretera, która może przełożyć każdy model na inny w razie potrzeby (która jest również podstawą tezy Kościoła-Turinga).
Teraz nigdy nie powinieneś patrzeć na swój komputer jako na surowy sprzęt. Zawiera układ logiczny, który wykonuje bardzo elementarne przetwarzanie. Ale większość z nich jest napędzana przez mikroprogramy wewnątrz komputera, o których nigdy się nie dowiesz. Następnie masz system operacyjny, który sprawia, że twoja maszyna wygląda nawet inaczej niż to, co robi sprzęt. Ponadto możesz mieć maszynę wirtualną, która wykonuje kod bajtowy, a następnie język wysokiego poziomu, taki jak Pyva i Jathon lub Haskell lub OCaml, które można skompilować w kod bajtowy.
Na każdym poziomie widzisz inny model obliczeniowy. Bardzo trudno jest oddzielić poziom sprzętu od poziomu oprogramowania, aby przypisać konkretny model obliczeniowy do maszyny. A ponieważ wszystkie są tłumaczalne, idea ostatecznego modelu obliczeń sprzętowych jest w zasadzie iluzją.
Maszyna rachunku lambda istnieje: jest to komputer, który może redukować wyrażenia rachunku lambda. Reklama, którą łatwo zrobić.
O wyspecjalizowanych architekturach maszyn
W rzeczywistości, w uzupełnieniu odpowiedzi Petera Taylora i w następstwie przeplatania się sprzętu / oprogramowania, wyprodukowano specjalistyczne maszyny, aby lepiej je dostosować do określonego paradygmatu, a ich podstawowe oprogramowanie zostało napisane w języku programowania opartym na tym paradygmacie.
Obejmują one
Zasadniczo są to również niezbędne struktury sprzętowe, ale zminimalizowane dzięki specjalnym funkcjom oprogramowania harware lub mikroprogramowanym tłumaczom, aby lepiej dostosować się do zamierzonego paradygmatu.
W rzeczywistości sprzęt wyspecjalizowany w określonych paradygmatach nie wydaje się być skuteczny na dłuższą metę. Powodem jest to, że technologia kompilacji do implementacji dowolnego paradygmatu na sprzęcie waniliowym stała się coraz bardziej skuteczna, tak że specjalistyczny sprzęt nie był tak bardzo potrzebny. Ponadto wydajność harware szybko się poprawiała, ale koszt ulepszeń (w tym ewolucja podstawowego oprogramowania) był łatwiej amortyzowany na sprzęcie waniliowym niż na sprzęcie specjalistycznym. Specjalistyczny sprzęt nie może konkurować na dłuższą metę.
Niemniej jednak i chociaż nie mam na ten temat dokładnych danych, podejrzewam, że przedsięwzięcia te pozostawiły pewne pomysły, które wpłynęły na ewolucję architektury maszyn, pamięci i zestawów instrukcji.
(a -> a) -> a.