Jeżeli przyjmuje się, że język musi być kompletny Turinga, aby był dobry, to czy rzeczywiście można mieć „użyteczny” język programowania, który nie jest kompletny?
Powinienem wyjaśnić, że chodzi tu raczej o języki programowania w tradycyjnym znaczeniu, a nie o języki znaczników i zapytań.
Odpowiedzi:
Coq , Agda , HOL i ACL2 są bardzo przydatnymi i niezwykle potężnymi językami, chociaż nie są kompletne w Turingu .
Powszechną cechą, która czyni je niekompletnymi, jest fakt, że zawsze można udowodnić zakończenie. Wystarczy bardzo proste ograniczenie: połączenia rekurencyjne są dozwolone tylko na możliwych do udowodnienia strukturalnie mniejszych warunkach. Dlatego, gdy nie jest to możliwe do wykonania tłumacza języka Turinga uzupełniania lub nawet dla języka sama wiele innych przydatnych rzeczy są nadal możliwe, jak kwalifikowanego kompilatora C .
źródło
Sądzę, że termin „mini-język” Yegge odnosi się do faktu, że często użyteczne jest używanie języka do konkretnych problemów, w których język nie wymaga kompletności w celu wykonania zadania, a to dotyczy sedna tego, jak bardzo - użyteczne mogą być kompletne języki. https://sites.google.com/site/steveyegge2/language-grubbing
Wikipedia odpowiada na to bardzo dobrze, zgodnie z tym, co powiedział mój brzuch. Najpierw myślałem o czystej matematyce, a potem przypomniałem sobie o wyrażeniach regularnych, a Wikipedia wymienia Epigram, który moim zdaniem byłby w stylu „czystej matematyki”.
http://en.wikipedia.org/wiki/Turing_completeness#Non-Turing-complete_languages
Wspomina również, że reprezentacje struktury danych nie są językami, ale sądzę, że XSLT powinien liczyć się jako reprezentacja obliczeń, XPath może nie opierać się na tym, co powiedział Yannis o SQL jako języku zapytań, a nie języku obliczeń. Być może T-SQL lub PL / SQL liczą się jako języki obliczeniowe, ponieważ można wykonać wiele obliczeń przy użyciu ich agregatów, gdzie uogólniona forma SQL może nie określać agregatów.
źródło
Rozumiem, że SQL jest dość popularny wśród typów biznesowych
źródło
Kompletność Turinga jest niezbędna, aby język mógł być używany jako język ogólnego przeznaczenia. Ale to nie wystarcza , tj. Tylko dlatego, że jest kompletne Turinga, nie nadaje się do każdej problematycznej dziedziny:
I odwrotnie, DSL jest odpowiedni dla problematycznej dziedziny, dla której został zaprojektowany (zakładając, że został właściwie zaprojektowany), nawet bez kompletności Turinga:
* IIRC udowodniono, że HTML z animacjami CSS jest w pełni Turinga, wykorzystując je do implementacji Gry życia Conwaya na szeregu pól wyboru. Ale przydatność HTML-u utrzymuje się nawet w przeglądarkach, które nie obsługują animacji CSS.
źródło
W rzeczywistości istnieją języki programowania, w których można pisać tylko „wydajne” programy. Wydajny w tym sensie oznacza, że każdy program napisany w takim języku reprezentuje język
P
. Bellantoni, Niggl i Schwichtenberg opisują tutaj taki język .źródło
Preprocesor C nie jest Turing-complete (z założenia), ale wciąż może implementować interpreter dla języka, który jest Turinga kompletny (Zamówienie języka, jak opisano w dokumentacji, jest w zasadzie tylko zbiorem frezować czysto funkcjonalny program typu ML / Scheme i byłby stosunkowo mało znaczący - prawdopodobnie całkiem przyjemny w użyciu - gdyby nie nietypowa implementacja).
Trik za tym jest podobny do argumentów powyżej dotyczących implementacji dowolnej maszyny Turinga w skończonym fizycznym wszechświecie: preprocesor C nie może zapewnić nieskończonej liczby kroków lub komórek danych dla języka, ale może:
zapewnienie bezzasadnie dużą liczbę dynamicznego (2 ^ 64 lub tak domyślnie), wystarczająco duży dla rozwiązywania problemów przy użyciu najbardziej realistyczny gwałtowny proces ekspansji ( bełkot bełkot dożywotnią wszechświata Mumble ).
użyj dowolnego statycznego ograniczenia dla powyższej liczby, tzn. chociaż liczba kroków musi być pewną liczbą skończoną, możesz zmienić to, co jest określone ograniczenie w czasie „kompilacji”, zmieniając ustawienia statyczne silnika interpretera. Ponieważ nie ma (teoretycznego) ograniczenia rzeczywistej wartości tego ograniczenia, można (teoretycznie) rozszerzyć, aby pasował do miejsca wymaganego przez dowolny program kończący.
Nie twierdząc, że Order jest koniecznie sam w sobie „użyteczny”, lub że jakikolwiek silnik implementowany przez CPP byłby, ale jest to ciekawy dowód koncepcji. Jest również podobno dynamicznie wpisywany , co jest niezwykłe w tym obszarze.
źródło
Tak, w rzeczywistości możliwe jest posiadanie przydatnego języka, który nie jest kompletny w Turingu. Zobacz tutaj: http://tkatchev.bitbucket.org/tab/examples.html
Innym przykładem przydatnego niekompletnego języka Turinga jest SQL. (A jeszcze innym są arkusze kalkulacyjne, takie jak Gnumeric lub Excel, chociaż tak naprawdę nie są to języki programowania).
Co do tego, dlaczego chcesz mieć język, który nie jest kompletny w Turingu: ponieważ pozwala to na pewne mocne gwarancje dotyczące zachowania w czasie wykonywania.
Mówiąc wprost, kompletność Turinga oznacza zdolność do rekurencji. Posiadanie rekurencji oznacza posiadanie potencjalnie niezwiązanych struktur w pamięci. Ponieważ w prawdziwym świecie pamięć nie jest nieskończona, kompletność Turinga wymaga zarządzania pamięcią i / lub wyrzucania elementów bezużytecznych.
Zakaz rekurencji to świetny sposób na uniknięcie naprawdę trudnego problemu zarządzania zasobami.
Nota bene! Niekompletność Turinga niekoniecznie oznacza, że jakikolwiek program musi się zakończyć. Niekompletny język Turinga może umożliwić ocenę nieskończonej leniwej listy.
źródło
Do tej pory wspomniano o jednym interesującym „języku programowania sub-Turinga”, więc go dodam.
Nazywa się to „Crema” . Opisuje się jako:
To dość minimalistyczny i raczej niski poziom.
Powinien wyglądać znajomo dla programistów C.
Został początkowo sfinansowany przez Agencję Obrony Zaawansowanych Projektów Badawczych (DARPA), ale w chwili pisania tego tekstu wygląda na zupełnie nieokreślony. Ale może jednak ktoś jest zainteresowany.
źródło