Dlaczego niektóre języki programowania Turing są kompletne, ale brakuje im umiejętności innych języków?

42

Napotkałem dziwny problem podczas pisania interpretera, który (powinien) zaczepia się o zewnętrzne programy / funkcje: Funkcje w „C” i „C ++” nie mogą przechwytywać funkcji variadic , np. Nie mogę utworzyć funkcji, która wywoła „printf” z dokładnie tymi samymi argumentami, które otrzymał, i zamiast tego musi wywołać alternatywną wersję, która przyjmuje obiekt variadic. Jest to bardzo problematyczne, ponieważ chcę być w stanie wykonać obiekt z anonimowym hakiem.

Pomyślałem więc, że to dziwne, ponieważ Forth , JavaScript i być może mnóstwo innych języków może to zrobić bardzo łatwo, bez konieczności uciekania się do języka asemblera / kodu maszynowego. Skoro inne języki potrafią to zrobić tak łatwo, czy to oznacza, że ​​klasa problemów, które każdy język programowania może rozwiązać, różni się w zależności od języka, nawet jeśli wszystkie te języki są w Turingu kompletne ?

Pan Minty Fresh
źródło
33
Powinieneś zajrzeć do turingów plandek . Są fascynującym rodzajem języka programowania, który celowo udostępnia jak najmniej operacji, a jednocześnie jest w pełni ukończony. Większość z nich nie ma podstawowych typów danych, funkcji, a nawet prostych rzeczy, takich jak deklarowanie zmiennych. Osobiście uważam, że kodowanie w nich jest świetną zabawą, ponieważ zmusza cię do opuszczenia strefy komfortu, aby spróbować czegoś niepotrzebnie trudnego.
DJMcMayhem
8
Spójrz na to, co robi maszyna Turinga, a zobaczysz, że „Turing-complete” jest bardzo niewielką przeszkodą do usunięcia. Zasadniczo wszystko, co potrafi „czytać”, „pisać” i „skakać”, a jednocześnie obsługuje podstawową arytmetykę, jest całkowicie Turinga. To znacznie poniżej poziomu funkcji językowych, na które patrzysz.
aroth
2
Aby być jeszcze bardziej niedorzecznym: instrukcja MOV na procesorze x86 jest kompletna według Turinga. Szczegółowe informacje można znaleźć w cl.cam.ac.uk/~sd601/papers/mov.pdf .
Gareth McCaughan
3
Nawet gra karciana Magic: The Gathering jest kompletna. Kompletność Turinga nie ma prawie nic wspólnego z cechami języka.
Maszt
2
BTW są też bardzo skomplikowane języki programowania, które nie są kompletne, takie jak te sprawdzające dowody.
盛安安

Odpowiedzi:

68

Turing pełne języki mogą obliczyć ten sam zestaw funkcji , który jest zbiorem ogólnych rekurencyjnych funkcji cząstkowych. Otóż ​​to.NkN

To nic nie mówi o funkcjach językowych. Maszyna Turinga ma bardzo ograniczone właściwości kompozycyjne. Bez typu -calculus jest znacznie bardziej kompozycyjny, ale brakuje mu wiele cech powszechnie spotykane w nowoczesnych językach.λ

Kompletność Turinga nie mówi nic o posiadaniu typów, wbudowanych tablicach / liczbach całkowitych / słownikach, możliwościach wejścia / wyjścia, dostępu do sieci, wielowątkowości, alokacji dynamicznej, ...

Tylko dlatego, że Java nie ma funkcji X (powiedzmy makr, typów wyższej rangi lub typów zależnych), nie przestaje nagle być ukończonym Turingiem.

Kompletność Turinga i ekspresja językowa to dwa różne pojęcia.

chi
źródło
42
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ę obliczeniową na liczbach naturalnych” i „potrafi być używane do pisania niebanalnych programów, które współdziałają ze środowiskiem ".
Jörg W Mittag
12
Możesz także wspomnieć, że możesz mieć te rzeczy w C / C ++. Musisz po prostu napisać kod, który działa jako kompilator w C / C ++ dla innego języka, który ma je tam, gdzie kod kompiluje ciąg w kodzie C / C ++. Następnie możesz po prostu programować w języku Java w swoim pliku C. To wszystko wymagałoby dużo pracy, ale jest to możliwe (oczywiście dlatego, że C / C ++ jest Turing Complete).
Shufflepants
4
@Shufflepants Zastanawiam się jednak, czy naprawdę przydatne jest powiedzenie „mogę to zrobić w C ++, ponieważ potrafię interpretować inny język”. Pod tym względem Java, ML, C ++ są równoważne. TM z wyrocznią dla wywołań systemowych (I / O) są również równoważne. Obawiam się, że zgodnie z tym rozumowaniem praktycznie wszystkie języki są równie ekspresyjne. Jeśli tak, porównywanie języków nie jest użyteczne.
chi
9
@chi Masz rację, są one równoważne. To właśnie oznacza być Turing Complete. Wszystko, co można zrobić za pomocą jednego systemu Turing Complete, można zrobić w innym systemie Turing Complete. Może nie być to wygodne w określonym systemie. A wygoda robienia różnych rzeczy to podstawowy sposób porównywania różnych języków programowania. Ale nie o to pytało.
Shufflepants
5
@ Rhymoid Jeśli C nie jest Turing Complete ze względu na dostęp do pamięci lub ponieważ możliwość wysyłania dowolnych sygnałów do podłączonego urządzenia, które ma dowolnie dużą pamięć, się nie liczy, można argumentować, że żaden język ani urządzenie Turinga nie jest kompletne . Ale nie wydaje mi się, żeby to była bardzo produktywna linia rozumowania.
Shufflepants
47

Kompletność Turinga jest abstrakcyjną koncepcją obliczalności. Jeśli język jest kompletny Turinga, jest on w stanie wykonać dowolne obliczenia, które może wykonać każdy inny kompletny język Turinga.

Nie oznacza to jednak, jak wygodne jest to zrobić. Niektóre funkcje, które są łatwe w niektórych językach, mogą być bardzo trudne w innych, ze względu na wybór projektu. Kompletność Turinga po prostu mówi, że można wykonać obliczenia. Jako skrajny przykład może być trudne zaczepienie funkcji varadycznych w C ++, ale możliwe jest napisanie interpretera JavaScript w C ++, który może zaczepić funkcje variadic.

Projektowanie języka jest dość interesującą sztuką. Jednym z głównych kroków, które należy podjąć, jest określenie, jakie zachowania mają stanowić kręgosłup twojego języka. Te zachowania są łatwe do zrobienia w twoim języku, ponieważ są wbudowane w parter. Podejmujemy decyzje projektowe dotyczące tego, które funkcje należy uwzględnić w każdym języku.

Jeśli chodzi o twój konkretny przykład, kiedy C został opracowany, został zaprojektowany tak, aby działał bardzo blisko sposobu, w jaki działały języki asemblera dnia. Funkcje variadic po prostu wypychały argumenty na stos, z bardzo małym bezpieczeństwem typów. Wdrożenie tych różnych funkcji pozostawiono kompilatorowi, aby zapewnić maksymalną przenośność. W związku z tym poczyniono bardzo niewiele założeń dotyczących możliwości sprzętu. Zanim pojawił się JavaScript, scena się zmieniła. Działa już na maszynie wirtualnej jako język interpretowany, więc równowaga przesuwa się w kierunku wygody. Umożliwienie łączenia funkcji różnorodnych staje się rozsądne. Nawet w przypadku JavaScript, który jest kompilowany Just In Time, nasze kompilatory są skłonne przechowywać znacznie więcej dodatkowych informacji na temat argumentów niż kompilatory C z przeszłości.

Cort Ammon
źródło
1
@Wildcard Uważam (praktycznie) wszystkie kompilatory za niepoprawne. Większość języków jest kompletna z Turinga, ale ostatecznie musi zostać zinterpretowana przez / skompilowana do asemblera, co nie jest. Jest to jednak konieczne ograniczenie fizyczne - sprzęt nigdy nie jest potężny w Turingu. Mimo to obliczalność oferuje wiele przydatnych pojęć, które w praktyce odnoszą się do komputerów w świecie rzeczywistym.
chi
3
@Wildcard W tym trywialnym znaczeniu. Zestaw (i C) ma wskaźniki o stałym rozmiarze, które mogą adresować tylko ograniczoną ilość pamięci. Teoretycznie moglibyśmy zdefiniować zestaw, w którym wskaźniki są nieograniczonymi naturalistami, ale nie nazwałbym tego „zgromadzeniem” - nazwałbym to URM lub coś takiego. W praktyce po prostu udajemy, że fizyczne granice są wystarczająco duże, aby umożliwić uruchamianie naszych programów, więc nawet jeśli komputer jest tylko maszyną skończoną (co oznacza, że ​​nie może np. Wykonać dodawania), myślimy o nim bardziej jak o maszynie Turinga ( więc dodawanie jest wykonalne).
chi
4
@chi To nie jest całkiem dokładne. Po pierwsze, praktycznie wszyscy uważają, że C jest Turingem kompletnym, ponieważ zwykle przypisujemy to sformułowanie wokół założenia, że ​​„masz wystarczającą ilość pamięci”. W przypadku bardzo małej liczby osób, które muszą się martwić bardziej rygorystycznymi sformułowaniami, w których takie założenia są nieważne, C nie określa rozmiaru wskaźnika i nie określa ograniczenia ilości pamięci, którą można zaadresować. Tak więc nawet w absolutnie ścisłym znaczeniu „Turing zakończony”, C rzeczywiście jest Turing ukończony.
Cort Ammon
3
@CortAmmon Muszę się nie zgodzić. Gdybyśmy sformalizowali semantykę języka C, próbując osadzić założenie „wystarczającej ilości pamięci”, ponieślibyśmy porażkę, ponieważ sizeof(void *)zgodnie z normą ISO C jest to wymagane. To zmusza nas do ograniczenia ilości pamięci dla dowolnego programu, do czegoś dużego - ale wciąż ograniczonego. Np. Nie mogę napisać programu, którego semantyką jest dodawanie dwóch dowolnych naturałów. C może być jeszcze bardziej wydajny Turinga poprzez I / O, używając plików takich jak taśmy TM (jak wskazano powyżej @ Hurkyl). Zgadzam się, że w praktyce nie stanowi to problemu.
chi
7
Sugeruję nowy język C-inf, który jest dokładnie jak C, z wyjątkiem sytuacji, gdy za dużo pamięci jest przydzielane przez rekurencję lub alokację sterty, program jest przerywany, rekompilowany z większą wartością sizeof (void *) i sizeof (size_t), i zaczyna biec od początku.
gnasher729,
26

Pomyśl o językach programowania jako o różnych pojazdach lądowych: rowerach, samochodach, poduszkowcach, pociągach.

Turing Completeness mówi: „ten pojazd może jechać wszędzie, gdzie może się udać dowolny pojazd”. Oznacza to, że możesz obliczyć wszystkie te same funkcje. Wejście do wyjścia, od początku do końca.

Ale to stwierdzenie nic nie mówi o tym, jak się tam dostałeś. Może być na szynach, może być na drogach, może być w powietrzu. W ten sam sposób Turing Completeness nic nie mówi o tym , jak obliczasz funkcję. Możesz użyć rekurencji, iteracji lub dziwnych automatów komórkowych. Możesz używać typów lub nie, możesz używać technik dynamicznych lub statycznych. Ale jeśli wszystko, co rozważasz, to funkcje (lub zestawy / języki formalne), które możesz obliczyć, o ile masz Turing Complete, te funkcje dają ci tę samą moc.

jmite
źródło
4
To świetna analogia. Ładnie rozciąga się również na pytanie, które widziałem gdzie indziej na tej stronie, czy mogą istnieć inne modele obliczeń przewyższające maszynę Turinga: W tej analogii samoloty i statki kosmiczne są czymś więcej niż Turing Complete, a łodzie motorowe są kolejnym typ maszyny całkowicie. :)
Wildcard,
2
Podróż szybsza niż lekka jest prawdopodobnie lepszą analogią do obliczeń super-Turinga. Może to być możliwe, ale większość ludzi uważa, że ​​tak nie jest.
jmite
@jmite Oczywiście nadal nie ma dobrych dowodów sugerujących, że nasze mózgi są super-turingowymi komputerami. Może to wynikać z naszej (pozornej) niezdolności do rozważenia maszyn nieutwardzających, choć niekoniecznie jest to bariera nie do pokonania. Samoloty są właściwie całkiem dobrą analogią - po prostu lecą „prosto” między dwoma punktami, ignorując teren. Gdybyśmy mogli zignorować topologię samej czasoprzestrzeni, moglibyśmy latać również szybciej niż światło. Nie mówię, że można zignorować topologię czasoprzestrzeni, pamiętajcie :)
Luaan 30.09.16
1
@Luaan Racja, ale nasz mózg niekoniecznie musi być super-Turingiem, aby zrozumieć komputer super-Turinga. Potrafię opisać semantykę maszyny Turinga za pomocą słabszego języka kończącego, takiego jak prosty typ rachunku Lambda, pisząc funkcję, która pobiera TM i jej stan, i przechodzi do następnego stanu. Nie mogę uruchomić maszyny w tym języku (ponieważ może to wymagać nieskończonych kroków), ale mogę napisać, jak wygląda każdy krok.
jmite
@Luaan, „wciąż nie ma dobrych dowodów sugerujących, że nasze mózgi to super-turingowe komputery” - być może, ale nie ma również dowodów sugerujących, że ludzki umysł jest tylko maszyną Turinga. Ponieważ nie ma maszyny Turinga, na którą można by wskazywać w dowolnym miejscu, którego nie można by przypisać ideom zrodzonym przez ludzki umysł - wciąż istnieje różnica, że życie może powstać z idei, a mechanicznych pomysłów nie. Ale jeśli chodzi o modele obliczeń, myślę, że maszyny Turinga z powodzeniem obejmują wszystko, co można racjonalnie nazwać „obliczeniami”, ideami i marzeniami i tak dalej.
wieloznaczne
17

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:

  1. wszystkie systemy obliczeniowe zdolne do obliczeń ogólnych są równie wydajne, i
  2. 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:

  1. jak skuteczne są różne symulacje i
  2. 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.

  1. 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.
  2. 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!
Jörg W Mittag
źródło
7

Wszystkie kompletne języki programowania Turinga mogą implementować ten sam zestaw algorytmów. Jeśli więc zauważysz, że niektóre algorytmy są bardzo trudne do zaimplementowania w określonym języku, nie oznacza to, że jest to niemożliwe.

Pamiętaj, że język składa się ze składni i semantyki. Czasami zestaw słów należących do jakiegoś języka nie jest minimalny, aby uznać go za kompletny, istnieją funkcje, które ułatwiają (dlatego nazywane są funkcjami ). Jeśli wyłączysz te funkcje, język nadal będzie kompletny.

Niektóre z nich mogą być interesujące:

Ogromny
źródło
5

Wszystkie języki kompletne Turinga mogą obliczać te same rzeczy.

Jeśli spróbujesz wdrożyć nowoczesny język, zauważysz, że większość jego funkcji nie dodaje żadnych możliwości obliczeniowych. Wiele z tych funkcji można sprowadzić do prostszych, które już istnieją w tym samym języku.

Oto kilka przykładów:

  • Jeśli nie masz wyliczeń, możesz użyć liczb całkowitych.
  • Jeśli nie masz buforów znających ich rozmiar, możesz utworzyć typ zawierający rozmiar i bufor, który nie zna jego rozmiaru.
  • Jeśli nie masz sprawdzania granic buforów, możesz po prostu sprawdzić indeks za każdym razem, gdy ich używasz.
  • Jeśli nie masz funkcji variadic, możesz utworzyć funkcję, która pobiera bufor znający jego rozmiar i odczytuje z tego bufora te same informacje, które można uzyskać z formalnych argumentów.
  • Jeśli nie masz operatorów, możesz użyć funkcji.
  • Jeśli nie masz typów, które mogą się dziedziczyć, możesz tworzyć typy, które się zawierają, i uzyskać do nich dostęp poprzez dodatkowy poziom pośredni, przy czym podtyp jest po prostu transformacją typu uchwyt do całego typu na uchwyt do typu zamkniętego.
  • Jeśli nie masz delegatów, ale masz wskaźniki funkcji, możesz utworzyć typ zawierający obiekt referencyjny i wskaźnik funkcji.
  • Jeśli nie masz delegatów, ale masz interfejsy, możesz zadeklarować interfejs zawierający jedną metodę z żądanym podpisem.
  • Jeśli nie masz typów ogólnych, możesz użyć typów ogólnych, które zakładają jedynie górne lub dolne granice, którymi jesteś zainteresowany (i być może wykonuj odpowiednie rzuty w miejscach użycia, aby utrzymać kompilator w dobrej formie).
  • Jeśli nie masz systemu liniowego / afinicznego, możesz po prostu uniknąć używania dowolnej zmiennej więcej niż raz.
  • ...i tak dalej.

Projektowanie język nurt koncentruje się na funkcji, które sprawiają, że łatwiej i bardziej wygodne dla nas, aby obliczyć rzeczy szybciej rozpoznawać nasze błędy wcześniej programu przed nieznanymi komponentów sprawiają, że równoległości bezpieczniejsze, i tak dalej.

Rzeczy czysto obliczeniowe zostały przybite dawno temu.

Theodoros Chatzigiannakis
źródło
4

Istniejące odpowiedzi słusznie wskazują, że kompletność Turinga nie jest dobrym sposobem na porównanie języków. Rzeczywiście, prawie wszystkie języki są kompletne. („Jeśli każdy jest wyjątkowy, to nikt nie jest wyjątkowy”, jak mawiał Iniemamocni).

Jednak to jest możliwe porównanie wyrazistość języków z matematyczną precyzją. Spójrz na ekspresyjną moc języków programowania Felleisen . Z grubsza chodzi o to, aby zadać następujące pytanie: Czy mogę przekonwertować dowolny program w języku A na program w języku B, wprowadzając tylko lokalne zmiany? Innymi słowy, Felleisen nadaje twojej intuicji matematycznie precyzyjną formę.

rgrig
źródło
2

Oprócz odpowiedzi innych osób, oto kolejna analogia.

Do prania ubrań potrzebne są trzy rzeczy: zbiornik, w którym znajduje się woda, pewnego rodzaju detergent i mechanizm mieszania. Można to zrealizować na wiele sposobów. Zbiornik wodny to wszystko, co utrzymuje wystarczającą ilość wody (np. Wanna, jezioro, rzeka). Mechanizmem mieszającym może być urządzenie mechaniczne, zmywarka, a nawet kamień, o który ubijane są ubrania. I detergenty są również w różnych postaciach.

Jaka jest różnica między nowoczesną skomputeryzowaną pralką a kamieniem nad rzeką?

Sprowadza się do trzech rzeczy: wydajności, bezpieczeństwa i wygody. Niektóre metody prania zużywają mniej energii, mniej zanieczyszczają środowisko, zużywają mniej wody i tak dalej. Niektóre metody prania wymagają mniej powtarzalnych czynności manualnych (które powodują obrażenia) lub przebywania na zewnątrz w niesprzyjających warunkach pogodowych. Niektóre metody prania nie wymagają od człowieka opieki nad tym procesem.

Języki programowania Turing-complete są uniwersalne, więc są stawiane przed więcej niż jednym zadaniem. Niemniej jednak, dla danego zadania, niektóre języki programowania są bardziej wydajne, wygodniejsze i bezpieczniejsze (w tym sensie, że mniej może się nie udać, gdy program jest faktycznie używany) niż inne.

Pseudonim
źródło
2

Inni udzielili wielu dobrych odpowiedzi, ale nie wspominają jednoznacznie o jednym zastrzeżeniu, które kiedyś bardzo mnie pomieszało: kompletność Turinga nie oznacza, że ​​język może wyrażać dowolne funkcje obliczeniowe od danych wejściowych do wyjściowych. Jest słabszy: musi istnieć jakiś sposób reprezentowania dziedziny i zakresu zestawu funkcji obliczalnych jako danych wejściowych i wyjściowych, tak aby każda z tych funkcji odwzorowała się na program, który przyjmuje reprezentację swoich danych wejściowych do odpowiednich wyników.

Weźmy na przykład język, który wyraża maszyny Turinga. Każdy program w języku jest maszyną Turinga.

Teraz rozważ podjęzyk wszystkich maszyn Turinga, które odczytują i zapisują tylko znaki a, b i puste. Jest zakończony Turinga, ale nie może wyrazić żadnych programów, które na przykład produkują c na wszystkich wejściach, ponieważ nie może napisać żadnego cs. Może wyrażać tylko wszystkie funkcje obliczalne na wejściach i wyjściach zakodowanych jako ciągi znaków as i bs.

Nie jest więc prawdą, że wszystkie języki kompletne Turinga mogą obliczać te same rzeczy, nawet jeśli ograniczymy te rzeczy do funkcji obliczeniowych od ich potencjalnych danych wejściowych do ich potencjalnych wyników. Język może wymagać kodowania danych wejściowych i wyjściowych w określony sposób.

reinierpost
źródło