Czytałem o Jocie i Jocie i uznałem tę sekcję za mylącą:
W przeciwieństwie do Iota, gdzie drzewo syntaktyczne łańcucha może rozgałęzić się po lewej lub po prawej stronie, składnia Jot jest równomiernie rozgałęziona w lewo. W rezultacie Iota jest całkowicie pozbawiona kontekstu, ale Jot jest zwykłym językiem.
Rozumiem, że zarówno Iota, jak i Jot są w Turingu kompletni. Ale najwyraźniej jedno jest pozbawione kontekstu, a drugie jest regularne! Z pewnością zwykłe języki nie mogą być kompletne w Turingu?
regular-languages
programming-languages
turing-completeness
sdleihssirhc
źródło
źródło
1*0
jest to zwykły język ;-) Chociaż niezbyt przyjazny język programowania dla programisty lub kompilatora.Odpowiedzi:
Krótko mówiąc, odpowiedź brzmi tak.
Ale łączysz dwa całkowicie niezwiązane ze sobą znaczenia terminu „język” (tak, to jest mylące):
Zauważ, że możesz mówić o „języku C ++” z dwóch zupełnie niepowiązanych punktów widzenia, używając dwóch niepowiązanych znaczeń słowa „język”:
Cechy „języka C ++” z tych dwóch punktów widzenia nie są ze sobą powiązane.
Więcej przykładów, które pomogą ci rozdzielić te pojęcia:
źródło
(([a-z][0-9]*)*[A-Z][0-9]*([a-z][0-9]*)*->([a-zA-Z][0-9]*)*)*
jest to zwykły język, który jest w stanie opisać gramatykę dowolnego języka klasy 0Chociaż zestaw legalnych programów w Jot jest regularny, sam Jot jest kompletny w Turingu. Oznacza to, że każdą funkcję obliczalną można wyrazić w Jot. Możemy nawet wymyślić język, w którym wszystkie łańcuchy binarne są legalne, ale sam język jest kompletny (ćwiczenie). Mylicie składnię i semantykę.
Nawiasem mówiąc, języki bezkontekstowe również (prawdopodobnie) nie są NP-pełne, ponieważ mają algorytm analizy wielomianowej.
źródło
Sama składnia (zgodnie z kodowaniem w drzewach składniowych) współczesnych języków programowania jest daleka od wszystkiego, co robią. W rzeczywistości języki formalne zdefiniowane przez zestaw wszystkich programów w danym języku, które kompilują się bez błędów, rzadko są pozbawione kontekstu .
Współczynnik semantyki statycznej i dynamicznej w równaniu. Są niewidoczne w drzewie składni, ale określają, czy fragment kodu jest rzeczywiście programem i co oblicza. Podsumowując, w kontekście bez kontekstu. zwykły język formalny, który jest zdefiniowany przez „składnię”, zapewnia zbyt duże przybliżenie języka programowania.
Teraz, aby odpowiedzieć na twoje pytanie: tak, jest to możliwe. Rozważmy na przykład dowolną numerację Gödla w maszynach Turinga; otrzymujesz „język programowania” wszystkich liczb naturalnych, z których każda reprezentuje TM. To prawda, że nie jest to przyjemny język do programowania, ale z pewnością jest to kompletny język Turinga, który jest regularny - nawet banalny.
źródło
Język programowania jest kompletny dla Turinga, jeśli jest wystarczająco wyrazisty, aby określić każdą funkcję obliczalną przez maszyny Turinga. Tutaj omawiamy moc języków określonych w językach programowania . Na przykład napisanie interpretera dla maszyn Turinga w Pythonie nie jest trudne, więc Python jest kompletnym językiem programowania Turinga.
Składnia języka programowania , tj. Zestawu ciągów odpowiadających prawidłowym programom w języku programowania, sama jest językiem. Np. Rozważ zestaw wszystkich możliwych programów w języku Python. Składnia języka programowania może być kontekstowa , bezkontekstowa , regularna itp. Interesuje nas trudność sprawdzenia, czy dany ciąg znaków jest poprawnym programem w języku programowania (robią to kompilatory / tłumacze). Kiedy mówimy, że składnia języka programowania jest pozbawiona kontekstu, oznacza to, że dla jego składni istnieje gramatyka bezkontekstowa, i sugeruje, że istnieją automatyczne mechanizmy do sprawdzania poprawności programów,
Zauważ, że prostota składni języka programowania nie implikuje ograniczenia mocy obliczeniowej programów określonych w tych językach programowania.
źródło
Odpowiedź brzmi tak. Widzisz, zgodnie z przyjętą odpowiedzią, gramatyka jest niezależna od jej znaczenia. Słowami Chomsky'ego:
Jeśli gramatyka potrafi wytworzyć wystarczającą liczbę zdań do opisania wszystkich rzeczy, które mogą być obliczone, wówczas możemy dowolnie przypisać do nich znaczenie obliczeniowe - po jednym dla każdej rzeczy, którą można obliczyć.
Jeśli chodzi o konkretny przykład, popularny język
whitespace
ma regularną gramatykę, a może nawetx86 assembly languages
(wymaga weryfikacji).źródło