Dlaczego języki funkcjonalne Turing są kompletne?


22

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.


6
Nie odpowiedź, ale wspomniałeś, że nie wszystkie wersje rachunku lambda są Turing Complete. Prosty typ rachunku Lambda oraz silniejsze wersje Coq i Agda oparte na sprawdzaniu zakończenia nie są Turing Complete (ponieważ mają znaczące problemy z zatrzymaniem). Języki o silnym typie, takie jak Haskell i SML, radzą sobie z tym, pozwalając na dowolną rekurencję za pomocą kombinacji punktów stałych, czyli terminu typu (a -> a) -> a.
jmite

Po prostu błędem jest mówić „zdefiniowane jako ukończenie Turinga”. Czy możemy zmienić tytuł?
Andrej Bauer,

@AndrejBauer Dziękuję za edycję tytułu, ale jestem ciekawy, dlaczego ( zdefiniowany jako Turning Complete ) jest nieprawidłowy? Czy to dlatego, że jest przymiotnikiem? Czy opisane słowo byłoby lepsze niż określenie?
Abdul

1
@Abdul Cóż, problemem jest słowo „zdefiniowane”. Jeśli powiesz, że „języki funkcjonalne są zdefiniowane jako Turing complete”, oznacza to, że albo definicja „języka funkcjonalnego”, albo definicja „Turinga kompletnego” stwierdza, że ​​języki funkcjonalne są Turinga kompletne. W rzeczywistości żadna definicja tego nie mówi.
Tanner Swett

Odpowiedzi:


20

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.


Wybór maszyny Turinga jako odniesienia, w zakresie, w jakim faktycznie została wykonana, jest motywowany głównie historycznie: Turing jako pierwszy wymyślił satysfakcjonującą definicję obliczalności.
Yuval Filmus,

@YuvalFilmus I dlaczego była to bardziej „satysfakcjonująca definicja obliczalności”?
babou

Tak myślał Gödel. Bob Soare ma kilka słów do powiedzenia na ten temat: cs.uchicago.edu/~soare/Publications/compute.ps .
Yuval Filmus,

@YuvalFilmus To jest 46 stron. Mam na myśli kilka powodów, dla których powinna być bardziej satysfakcjonująca. Mogą być naiwni. Jeśli jest coś bardziej przekonującego, który tłumaczy sukces, warto to wyraźnie zaznaczyć.
babou,

Spójrz na rozdział 3.2. Były wcześniejsze definicje obliczalności, ale nie były przekonujące. Turing był pierwszym, który był przekonujący, przynajmniej dla niektórych kluczowych osób.
Yuval Filmus,

21

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.


„Maszyny Turinga to niezły model teoretyczny, ale nie są to bardzo dobre modele rzeczywistych komputerów”. Oprócz braku nieskończonej pamięci, jakie są inne powody, dla których nie jest to dobry model dla rzeczywistych komputerów? Czy też miałem rację, sądząc, że języki funkcjonalne oparte są na rachunku lambda?
Abdul,

5
λ

11
Języki nadrzędne mają tendencję do umożliwienia dostępy tablicy w stałym czasie, w ° C A[x]. Maszyny Turinga nie mogą tego robić w stałym czasie. Dlatego nawet w informatyce teoretycznej czas działania algorytmów jest analizowany na modelu maszyny RAM, a nie na modelu maszyny Turinga.
Yuval Filmus,

14
W rzeczywistości maszyny Turinga dobrymi komputerami… poza tym, że kiedy Turing napisał swój artykuł, „komputer” był opisem pracy człowieka pracującego za pomocą pióra i papieru. Głowica do odczytu / zapisu to model długopisu, taśma to model nieskończonego stosu arkuszy papieru (wystarczy pokroić je na małe paski i skleić je ze sobą), alfabet jest modelem naszego, dobrze, alfabetu , a skończone przejścia są modelem ograniczonej liczby reguł, które można zachować w głowie.
Jörg W Mittag,

3
To był najlepszy wgląd, jaki kiedykolwiek miałem, dlaczego do diabła Turing wybrał maszynę Turinga. Zawsze zastanawiałem się „dlaczego wybrał taki gówniany model obliczeń”. Zawsze myślałem, że gdyby wymyślono teorię obliczeń, pozostawiono mi (Boże, pomóżcie nam; nie bylibyśmy daleko), prawdopodobnie wybrałbym lepszy model obliczeń. Teraz rozumiem, skąd pochodził, a to ma o wiele więcej sensu.
Jake,

10

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


Nazwę Turinga-zupełnego można również nazwać na cześć Turinga (osoby), który wymyślił pierwszą filozoficznie satysfakcjonującą definicję obliczalności; lub może być nazwany na cześć pracy Turinga, w której opisuje tę koncepcję.
Yuval Filmus,

1
@YuvalFilmus: może być nazwany na cześć mamy Alana Turinga, ale tutaj twierdzenie jest takie, że tak nie jest ;-)
Steve Jessop

@YuvalFilmus Może być (chociaż, o ile mi wiadomo, nie jest). Ale skąd ten termin ma drugorzędne znaczenie. Liczy się tutaj to, co oznacza ten termin .
David Richerby,

2
To jest krótkie i słodkie, ale może trochę za krótkie. Co „robi” maszyna Turinga? Dobrze, że „czytają” i zapisują taśmy, których nie wyrażają lambda. Lepiej byłoby „Turing-kompletne modele obliczeń pozwalają na obliczenie wszystkich funkcji obliczeniowych”.
Theodore Norvell,

@TheodoreNorvell Myślę, że twój komentarz jest podobny do tego, o czym myślałem. Wiedziałem, że rachunek lambda i maszyna Turinga są równoważne pod względem mocy, ale różnią się mechanizmem (i teraz dowiedziałem się, że istnieją inne), ale zastanawiałem się, czy termin „kompletność Turinga” był w jakikolwiek sposób specjalny dla maszyny Turinga, czy jeśli to tylko nazwa.
Abdul

6

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.


0

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.


innymi słowy można powiedzieć, że Turing był pierwszym, który zidentyfikował / „rozpoznał” znaczenie zjawiska kompletności Turinga, a z kolei CS „rozpoznał” go za to monumentalne osiągnięcie poprzez użycie tego terminu.
vzn

X
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.