W istocie pytasz o różnicę między mocą obliczeniową a tak zwaną potęgą ekspresyjną (lub po prostu ekspresyjnością ) języka (lub systemu obliczeniowego).
Moc obliczeniowa
Moc obliczeniowa odnosi się do jakiego rodzaju problemów język może obliczyć. Najbardziej znaną klasą mocy obliczeniowej jest ta, która jest równoważna z uniwersalną maszyną Turinga . Istnieje wiele innych systemów obliczeniowych, takich jak Random Access Maszyn , X-rachunku , SK combinator rachunku , funkcji ľ-rekurencyjne , WHILEprogramy i wiele innych. Jak się okazuje, wszystkie one mogą się symulować, co oznacza, że wszystkie mają taką samą moc obliczeniową.
Daje to podstawę do Hipoteza Churcha-Turinga (nazwany Alonzo Church , który stworzył X nazębnego i Alana Turinga , który stworzył Universal Turing Machine). Teza Churcha-Turinga jest hipotezą o obliczalności z dwoma aspektami:
- wszystkie systemy obliczeniowe zdolne do obliczeń ogólnych są równie wydajne, i
- człowiek postępujący zgodnie z algorytmem może dokładnie obliczyć funkcje, które może obliczyć Maszyna Turinga (a więc każdy inny system).
Drugi jest jednak ważniejszy w dziedzinie filozofii umysłu niż informatyki.
Są jednak dwie rzeczy, których nie mówi teza Kościoła-Turinga , które są bardzo istotne dla twojego pytania:
- jak skuteczne są różne symulacje i
- jak wygodne jest kodowanie problemu.
Prosty przykład dla (1): na maszynie o swobodnym dostępie kopiowanie tablicy zajmuje czas proporcjonalny do długości tablicy. Na maszynie Turinga zajmuje to jednak czas proporcjonalny do kwadratu długości macierzy, ponieważ maszyna Turinga nie ma losowego dostępu do pamięci, może przemieszczać się po taśmie tylko jedna komórka na raz. Dlatego musi przesuwać się przez n elementów tablicy n razy, aby je skopiować. Różne modele obliczeń mogą mieć różne charakterystyki wydajności, nawet w przypadku asymptotycznym, w którym staramy się oderwać od szczegółów implementacji.
Mnóstwo przykładów (2): zarówno rachunek λ, jak i Python są kompletne według Turinga. Ale czy wolisz napisać program w języku Python lub w rachunku λ?
Jest też trzecia zmarszczka, którą omijałem do tej pory: wszystkie te oryginalne systemy zostały zaprojektowane przez logików, filozofów lub matematyków, a nie przez informatyków… po prostu dlatego, że komputery, a więc informatyka, nie istniały. Te wszystkie wrócić do początku 1930 roku, jeszcze przed Konrad Zuse „s bardzo pierwsze eksperymenty (które nie były programowalne i / lub Turing-complete tak). Mówią tylko o „funkcjach obliczalnych na liczbach naturalnych”.
Teraz, jak się okazuje, wiele funkcji można wyrazić jako funkcje liczb naturalnych - w końcu nasze nowoczesne komputery radzą sobie nawet z dużo mniejszą liczbą (w zasadzie 3-4 funkcje na liczbach 0 i 1 i to wszystko ), ale na przykład jaką funkcję oblicza system operacyjny?
To pojęcie I / O, efektów ubocznych, interakcji z otoczeniem, nie jest ujęte w idei „funkcji ponad liczbami naturalnymi”. A jednak jest to trochę ważne, ponieważ, jak to kiedyś ujął Simon Peyton Jones , „czystą funkcją bez efektów ubocznych jest rozgrzanie procesora” , na co członek publiczności odpowiedział „właściwie, to jest strona -efekt też! ”
Edwin Brady , projektant Idris , (tylko połowa) żartobliwie używa (nie wiem, czy to wynalazł) terminu „Tetris-complete”, aby wyrazić tę różnicę między „potrafi obliczyć dowolną funkcję obliczalną na liczbach naturalnych” i „potrafi być używane do pisania niebanalnych programów, które współdziałają ze środowiskiem ". Jeszcze bardziej ironicznie, demonstruje to, wdrażając klon Space Invaders w Idris , ale mówi, że jest pewien, że Tetris sprowadza się do Space Invaders.
Inną rzeczą, na którą należy zwrócić uwagę, jest to, że nie tylko ekwiwalent Turinga niekoniecznie wystarcza, aby mówić o pisaniu „przydatnych” programów, ale OTOH może nawet nie być konieczny . Np. SQL stał się odpowiednikiem Turinga tylko z ANSI SQL: 1999 , ale przedtem był użyteczny. W rzeczywistości niektórzy mogą twierdzić, że uczynienie go ekwiwalentem Turinga wcale nie zwiększyło jego przydatności. Istnieje wiele języków specyficznych dla domeny, które nie są odpowiednikami Turinga. Dane Opis Język zwykle nie jest (i nie powinien być). Total Languages oczywiście nie może być odpowiednikiem Turinga, ale nadal można w nich pisać pętle zdarzeń, serwery sieciowe lub systemy operacyjne. Istnieją również języki, które są odpowiednikami Turinga, ale w rzeczywistości uważa się to za błąd.
Podsumowując, równoważność Turinga nie jest szczególnie interesująca, chyba że chcesz statystycznie analizować programy.
Wyrazistość
Zakładając, że nasz system obliczeniowy ma wystarczającą moc obliczeniową, aby w ogóle rozwiązać nasz problem, musimy następnie wyrazić nasz algorytm rozwiązania tego problemu w formie formalnej notacji dla tego systemu. Innymi słowy: musimy napisać program w jakimś języku komputerowym. Właśnie tutaj pojawia się pojęcie ekspresji .
Odnosi się zasadniczo do tego, jak „łatwe” lub „przyjemne” jest pisanie naszego programu w naszym konkretnym języku programowania. Jak widać, pojęcie jest dość niejasne, subiektywne i bardziej psychologiczne niż techniczne.
Istnieją jednak próby dokładniejszych definicji. Najsłynniejszy (i najbardziej rygorystyczny, jaki znam) to Matthias Felleisen w swoim artykule O ekspresyjnej mocy języków programowania (pierwsze dwie strony zawierają łagodne wprowadzenie, reszta artykułu jest bardziej mięsista).
Główna intuicja jest taka: podczas tłumaczenia programu z języka na inny język niektóre zmiany, które należy wprowadzić, są lokalnie zawarte (takie jak np. Przekształcanie FORpętli w WHILEpętle lub pętle w warunkowe GOTO), a niektóre wymagają zmiany w globalnym struktura programu.
Jeśli możesz zastąpić jedną cechę jednego języka inną cechą innego języka tylko lokalnymi transformacjami, wówczas mówi się, że te funkcje nie mają wpływu na siłę ekspresji. Nazywa się to cukrem syntaktycznym .
Z drugiej strony, jeśli wymaga to zmiany globalnej struktury programu, mówi się, że język, na który tłumaczysz, nie jest w stanie wyrazić tej funkcji. Mówi się, że język, z którego się tłumaczy, jest bardziej wyrazisty (w odniesieniu do tej funkcji).
Zauważ, że daje to obiektywnie mierzalną definicję ekspresji. Zauważ też, że pojęcie zależy od kontekstu i jest porównawcze. Tak więc, jeśli każdy program w języku A można przetłumaczyć na język B tylko z lokalnymi zmianami, a istnieje co najmniej jeden program w języku B, którego nie można przetłumaczyć na język A tylko z lokalnymi zmianami, to język B jest bardziej wyrazisty niż język ZA. Jednak bardziej prawdopodobnym scenariuszem jest to, że wiele programów w obu językach może być tłumaczonych tam iz powrotem, ale istnieją pewne programy w obu językach, których nie można przetłumaczyć na inny. Oznacza to, że żaden język nie jest bardziej wyrazisty niż inny, mają tylko różne funkcje, które pozwalają na różne wyrażenia różnych programów.
Daje to formalną definicję tego, co znaczy być „bardziej ekspresyjnym”, ale wciąż nie uchwyca psychologicznych pojęć tego zjawiska. Na przykład cukier składniowy, zgodnie z tym modelem, nie zwiększa mocy ekspresyjnej języka, ponieważ można go przetłumaczyć przy użyciu tylko lokalnych zmian. Jednak z doświadczenia wiemy, że posiadanie FOR, WHILEi IFdostępne, nawet jeśli są one po prostu cukier syntaktyczny dla warunkowych GOTOmarek wyrażając naszą intencją łatwiejsze .
Faktem jest, że różne języki mają różne funkcje, dzięki którym wyrażanie różnych sposobów myślenia o problemie jest łatwiejsze lub trudniejsze. I niektórzy ludzie mogą znaleźć jeden sposób wyrażenia swoich zamiarów łatwiej, a inni inny sposób.
Przykład, który znalazłem w tagu Ruby na StackOverflow: wielu użytkowników, którzy śledzą tag Ruby, twierdzą, że pętle są łatwiejsze do zrozumienia niż rekurencja, a rekurencja dotyczy tylko zaawansowanych funkcjonalnych programistów, a pętle są bardziej intuicyjne dla początkujących, ale widziałem wiele przypadków kompletni nowicjusze, którzy intuicyjnie piszą taki kod:
def rock_paper_scissors
get_user_input
determine_outcome
print_winner
rock_paper_scissors # start from the top
end
Co zwykle prowadzi do tego, że kilka osób komentuje, że „to nie działa” i „robią to źle”, a „poprawny sposób” jest następujący:
def rock_paper_scissors
loop do
get_user_input
determine_outcome
print_winner
end
end
Oczywiście są ludzie, dla których rekurencja ogona jest bardziej naturalnym sposobem wyrażenia koncepcji „zapętlenia” niż konstrukcji pętli.
Podsumowanie
Fakt, że dwa języki są odpowiednikami Turinga, mówi jedną i dokładnie jedną rzecz: że mogą one obliczyć ten sam zestaw funkcji na liczbach naturalnych, co maszyna Turinga. Otóż to.
Nie mówi nic o tym, jak szybko obliczają te funkcje. Nie mówi nic o łatwości wyrażania tych funkcji. I nie mówi nic o tym, co mogą zrobić poza funkcjami obliczania liczb naturalnych (np. Łączenie z bibliotekami C, odczytywanie danych wejściowych od użytkownika, zapisywanie danych wyjściowych na ekranie).
czy to oznacza, że klasa problemów, które każdy język programowania może faktycznie rozwiązać, różni się w zależności od języka, mimo że wszystkie te języki są w pełni gotowe?
Tak.
- Istnieją problemy, których nie obejmuje termin „Turing-complete” (który dotyczy wyłącznie funkcji obliczeniowych na liczbach naturalnych), np. Drukowanie na ekranie. Dwa języki mogą być kompletne Turinga, ale jeden umożliwia drukowanie na ekranie, a drugi nie.
- Nawet jeśli oba języki mogą rozwiązać te same problemy, nie mówi to nic o tym, jak skomplikowane jest kodowanie i jak łatwo jest je wyrazić. Np. C może rozwiązać każdy problem, który potrafi Haskell, po prostu pisząc interpreter Haskell w C… ale najpierw musisz napisać interpreter Haskell, aby rozwiązać problem w ten sposób!