Kryteria aby ustalić, czy jest to język programowania

Question

Jakie są critera lub podstawowe cechy wymagane, aby powiedzieć, że X lub Yjest (lub nie) język programowania?

Zrobiłem trochę czytania (Is HTML considered a programming language?, Turing complete i others), i doszedł do wniosku, że język lub składnia musi być Turinga kompletne powinna być traktowana jako język programowania. Czy to jest poprawne? Wystarczy?

A jak ustalić, czy coś jest Turing kompletny? Czy są jakieś konkretne kryteria?

Czy struktura sterowania przepływem (instrukcje warunkowe i pętle) jest wystarczająca, aby można ją było uznać za Turing complete?

Answer 1

Termin "język programowania" jest nieco niewyraźny. Czy wyrażenia regularne stanowią język programowania? Większość programistów powiedziałaby "tak", nawet jeśli wyrażenia regularne nie są kompletne.

Jeśli chodzi o kompletność Turinga, nie jestem ekspertem, ale myślę, że wystarczy mieć gałąź warunkową i nieskończony stos (dlatego prawdziwa maszyna tylko przybliża całkowitą turingowść).

EDYCJA: Po kilku badaniach odkryłem, że to nie wystarcza. Potrzebujesz co najmniej dwóch stosów i minimalnej liczby stanów (oraz tabeli przejściowej stanu).

Być może bardziej przyziemnym miernikiem jest to, że jeśli zapamięta się dowolne ilości stanów i pętli, to prawdopodobnie jest kompletny.

Answer 2

Istnieją języki programowania, które nie są kompletne. W przypadku niektórych przykładów języków innych niż Turinga należy sprawdzić: Practical non-Turing-complete languages? Zaletą posiadania języka, który nie jest Turingiem, może być na przykład wykonanie wystarczających zadań, a jednocześnie wystarczająco proste, aby umożliwić ci udowodnienie właściwości swoich programów, czego nie można udowodnić w inny sposób. Może to na przykład być przydatne w przypadkach, w których ważne jest, aby wiedzieć, że program będzie działał bezbłędnie.

Co dokładnie stanowi język programowania jest nieco niejasne, ale można powiedzieć, że jest to język, w którym można wyrazić obliczenia. Jeśli spojrzymy na HTML, nie można utworzyć dokumentu, który cokolwiek wylicza; to jedynie informuje przeglądarkę, w jaki sposób strona ma wyglądać. Ważną rzeczą do zapamiętania jest to, że nie oblicza niczego nowego.

Jest to, jak mówi Marcelo, dość niewyraźne.

chodzi o ustalenie, czy język jest Turinga kompletne, odniosę się do tej kwestii: What are practical guidelines for evaluating a language's "Turing Completeness"?

Answer 3

Jakie są critera lub podstawowe cechy wymagane, aby powiedzieć, że X lub Y jest (lub nie jest) język programowania?

Jak Marcelo Cantos już powiedziano nam, że jest nieco zamazany, zwłaszcza, że ​​istnieją konkretne domeny języki (DSL; http://en.wikipedia.org/wiki/Domain-specific_language), które nie są kompletne Turinga, ale także często uważane języków programowania.

Jak ustalić, czy coś jest ukończone? Czy są jakieś konkretne kryteria?

Jednym ze sposobów określenia, czy język programowania jest Turing complete jest napisanie w nim maszyny Turinga (lub wdrożenie rachunku lambda).

Innym sposobem jest udowodnienie, że wszystkie funkcje rekurencyjne mu mogą być obliczane przez język programowania.

Ponieważ można udowodnić, że imperatywny język programowania jest kompletny Turinga, jeśli istnieje zmienna przyporządkowanie, sposób reprezentowania liczby 0, następcza funkcja, poprzednia funkcja i możliwość reprezentowania while-loops to jest inna droga.

Czasami używany sposób (który z oczywistych powodów nie zawsze działa), aby udowodnić, że językiem programowania nie jest Turing-complete jest sprawdzenie, czy wszystkie programy kończą się; jeśli tak, to nie może być.

Answer 4

Warto więc pomyśleć o konsekwencjach tych konkretnych definicji:

Turing-complete język jest językiem programowania: CSS becomes a programming language.

Język programowania musi być kompletny: być może, ale programs can be written otherwise.

Teraz znacznie lepsza definicja: Język programowania to taki, który może być używany do pisania programów.