Czy zwykłe języki mogą być kompletne w Turing?

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?

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):

• Zestaw strun. „Język bezkontekstowy” oznacza „zestaw ciągów znaków, które można rozpoznać za pomocą gramatyki bezkontekstowej”.
• Sposób określania obliczeń. „Pełny język Turinga” oznacza „sposób określania programów, w których można określić maszynę Turinga”.

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”:

• C ++ jako zestaw ciągów, które są legalne zgodnie z gramatyką C ++
• C ++ jako sposób określania programów.

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:

• Wyrażenie „[az] + @ [az]. [Az]” opisuje zestaw ciągów znaków rozpoznawalnych przez automaty skończone, tj. Zwykły język. Jednak po prostu - zestaw ciągów: nie jest sposobem określania programów (chyba że podasz sposób interpretowania każdego takiego łańcucha jako programu), więc nie ma sensu mówić o tym, czy jest to Turing kompletny.
• Język schematów blokowych jest sposobem określania programów; w zależności od konkretnego smaku schematów blokowych może on być, ale nie musi, kompletny według Turinga. Jednak schematy blokowe nie są łańcuchami, więc nie ma sensu mówić o schematach blokowych w znaczeniu „język jako zestaw łańcuchów”.

Chociaż 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.

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.

1. 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.

2. 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.

Odpowiedź brzmi tak. Widzisz, zgodnie z przyjętą odpowiedzią, gramatyka jest niezależna od jej znaczenia. Słowami Chomsky'ego:

Myślę, że jesteśmy zmuszeni stwierdzić, że gramatyka jest autonomiczna i niezależna od znaczenia ...

Chomsky, Syntactic Structures (1956)

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 whitespacema regularną gramatykę, a może nawet x86 assembly languages(wymaga weryfikacji).