Dlaczego języki funkcjonalne Turing są kompletne?

Być może moje ograniczone rozumienie tematu jest nieprawidłowe, ale rozumiem do tej pory:

• Programowanie funkcjonalne oparte jest na rachunku Lambda Calculus opracowanym przez Alonzo Church.

• Programowanie imperatywne oparte jest na modelu maszyny Turinga, stworzonym przez Alana Turinga, ucznia Churcha.

• Rachunek Lambda jest tak potężny i zdolny jak Maszyna Turinga,
  co oznacza, że ​​są one równoważne pod względem mocy obliczeniowej.

Jeśli programowanie funkcjonalne opiera się na rachunku Lambda Calculus, a nie na maszynie Turinga, to dlaczego niektóre (lub wszystkie) z nich są opisane jako Turing zakończone, a nie Lambda kompletne czy coś w tym rodzaju? Czy termin „kompletność Turinga” jest w jakikolwiek sposób wyjątkowy dla maszyn Turinga, czy może to tylko słowo?

Wreszcie, jeśli imperatywne języki oparte są na maszynie Turinga, a komputery są w zasadzie maszynami Turinga bez nieskończonej pamięci, czy to oznacza, że ​​działają one lepiej niż funkcjonalne języki programowania na naszych nowoczesnych komputerach?

Jeśli tak jest, to jaki byłby odpowiednik maszyny do rachunku lambda?

Wiem, że wydaje się, że są to 3 osobne pytania, ale wszystkie są ze sobą ściśle powiązane i każde z nich zależy od tego, czy poprzednie pytanie było prawidłowym pytaniem na początek.

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

• Burroughs B5000 i jego następców (1960), które zostały przystosowane do skutecznego wdrażania rekursji, reprezentowany wówczas przez języka Algol 60 .

• Western Digital WD / 9000 Pascal mikrosilnik , a maszyny oparte na microprogrammed kodu bajtowego specjalizujące dla Pascala język programowania, w 1980 roku.

• Kilka marek Lisp Machines w latach 80.

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.

Turing-complete to tylko nazwa. Jeśli chcesz, możesz to nazwać Abdul-complete. Nazwy są ustalane historycznie i często są nazywane po „złych” ludziach. To proces socjologiczny, który nie ma jasnych kryteriów. Nazwa nie ma znaczenia poza oficjalną semantyką.

Języki imperatywne nie są oparte na maszynach Turinga. Opierają się na maszynach RAM. Twój komputer to pamięć RAM. Maszyny Turinga to niezły model teoretyczny, ale nie są to bardzo dobre modele rzeczywistych komputerów.

Języki programowania oparte na innych paradygmatach mogą być bardzo udane, nawet jeśli procesor nie obsługuje ich natywnie; na przykład drukarki używają języka stosu. Programowanie to coś więcej niż kod maszynowy.

Ponieważ „Turing-complete” oznacza po prostu „może obliczyć wszystko, co może obliczyć maszyna Turinga”.

Wydaje się, że na jedno z Twoich pytań jeszcze nie udzielono odpowiedzi:

Jeśli tak jest, to jaki byłby odpowiednik maszyny do rachunku lambda?

Maszyna Lisp . Sprzęt zaprojektowany specjalnie do modelu obliczeniowego LISP. Artykuł w Wikipedii mówi o produktach komercyjnych, ale mój dyrektor studiów na uniwersytecie miał ręcznie zbudowany w swoim biurze.

języki funkcjonalne w postaci rachunku lambda wymyślone przez Kościół okazały się kompletne. jest to faktyczny dowód matematyczny, który można znaleźć w opublikowanych pracach naukowych poprzez „zredukowanie” rachunku lambda do operacji / obliczeń na maszynach Turinga. mniej więcej w czasie pracy Turingsa w 1936 r. i później zaproponowano / rozpowszechniono różne „kompleksowe” modele obliczeń. to było nie od razu zrozumiał , że wszystkie były równoważne. dowody potwierdzające, że były one równoważne, opublikowano mniej więcej pod koniec lat 30. i 40. po pracy Turingsa.

maszyna Turinga jest koncepcyjnie (ale nie funkcjonalnie) prostsza niż inne modele i jest to prawdopodobnie znaczna część powodu, dla którego kompletność Turinga nosi jego imię. inne pomysły, takie jak rachunek lambda, są bardziej abstrakcyjne i powstały / powstały głównie w teorii matematyki / logiki. Turing zaproponował maszynę teoretyczną . „maszyna” jest dosłownie „fizyczne urządzenie”. jego niezwykły obiekt koncepcyjny / konstrukcja, która łączy / jednoczy dwa różne światy, zastosowany i teoretyczny. nadaje nowym abstrakcyjnym znaczeniom byty fizyczne, np. „czas i przestrzeń”. to nie przypadek, że matematycy czasami odnoszą się do „technologii”, „maszyny” lub „urządzeń” dowodów. Turingowi udało się to wszystko genialnie połączyć w swój konceptualny wynalazek. jego definicja jest dość prosta, ale jej analiza wykazuje jedne z najbardziej niezwykłych zachowań, jakie kiedykolwiek pojawiły się w historii myśli naukowej / matematycznej. Turing był pierwszym naukowcem / matematykiem, który uchwycił wiele z tego znaczenia / mocy / potencjału.