Rozważalne języki i nieograniczone gramatyki?

Maszyny Turinga i nieograniczona gramatyka to dwa różne formalizacje, które definiują języki RE. Niektóre języki RE są rozstrzygalne, ale nie wszystkie są.

Możemy zdefiniować rozstrzygalne języki za pomocą maszyn Turinga, mówiąc, że dany język jest rozstrzygalny, jeśli istnieje TM dla języka, który zatrzymuje i akceptuje wszystkie ciągi w języku oraz zatrzymuje i odrzuca wszystkie ciągi poza tym językiem. Moje pytanie brzmi: czy istnieje analogiczna definicja rozstrzygalnych języków opartych na gramatyce bez ograniczeń, a nie na maszynach Turinga?

computability turing-machines formal-grammars templatetypedef
źródło

Odpowiedzi:

Język jest rozstrzygalny, jeśli jest częściowo rozstrzygalny, a jego dopełnienie jest częściowo rozstrzygalne. Co więcej, język jest wymienny rekurencyjnie, jeśli jest częściowo rozstrzygalny, dzięki czemu można znaleźć nieograniczoną gramatykę. W związku z tym:

Język jest rozstrzygalne IFF jest zarówno nieograniczony gramatyki z i nieograniczony gramatyki z . $L$ $G$ $L(G) = L$ $\bar G$ $L(\bar G) = \bar L$

Simon S.
źródło

Ponadto, czy synonimy „półdecydowalne” i „rekurencyjnie wyliczalne” są synonimami?

templatetypedef

1. IIRC nie ma znanej klasy gramatyki formalnej odpowiadającej rozstrzygającym językom, więc nie sądzę, że jest to możliwe przy pojedynczej gramatyce bez ograniczeń. 2. Tak, zdarza się, że oznaczają to samo.

Simon S

Mylisz się co do definicji rozstrzygalności. Rozstrzygalne oznacza „istnieje maszyna Turinga, która oblicza odpowiedź”. Relacja, którą zacytowałeś jako definicję, jest w rzeczywistości twierdzeniem, które słyszałem o Emile Post.

Andrej Bauer,

Następnie, zdolność do półdecydowania i wyliczalność rekurencyjna nie są synonimami, ale są równoważnymi pojęciami. Zestaw jest półdecydowalny, jeśli jest to zestaw zatrzymujący maszyny Turinga, podczas gdy jest rekurencyjnie wyliczalny, jeśli jest wyliczany przez maszynę Turinga.

Andrej Bauer,

1. Masz rację, rozstrzygalność niekoniecznie jest zdefiniowana w ten sposób (ale może być), dlatego zredagowałem odpowiedź. 2. Właśnie dlatego napisałem „oni mają na myśli to samo”, być może „synonim” jest niewłaściwym słowem.

Simon S

Od tego czasu nie może być przydatnej klasy gramatyki dla języka (zestawu języków rekurencyjnych) $\mathrm{R}$

każda przydatna klasa gramatyki jest wymienna, i
$\mathrm{R}$

Pierwszy oczywiście nie jest rygorystycznym twierdzeniem (i nie może być), to tylko domniemanie sądowe. Zbiór wszystkich gramatyk jest policzalny, a wszelkie ograniczenia, których nie można rozstrzygnąć, prawdopodobnie same w sobie nie są zbyt użyteczne¹; w szczególności nie będzie to ograniczenie składniowe (jak Chomsky'ego).

Druga jest formalnie prawdziwa, patrz również tutaj .

Oczywiście ludzie zdefiniowali takie ograniczenia , a klasy te mają swoje zastosowania, ale ciężko jest nawet stwierdzić, czy dana gramatyka należy do prostszych podklas.

Raphael
źródło

Dlaczego ten argument nie dotyczy również maszyn Turinga? Istnieje przydatna klasa baz TM dla R (decydentów), nawet jeśli nie są one policzalne.

templatetypedef

@templatetypedef: Ta myśl przyszła mi do głowy. 1) Zestaw maszyn Turinga dla R jest nieco „niematerialny”. Prawdopodobnie nie jest „użyteczny” w żadnym, ale najbardziej teoretycznym sensie. 2) TM jest modelem operatywnym, podczas gdy gramatyki są bardziej modelem deklaratywnym (jeśli generatywnym). Dlatego jest mało prawdopodobne, aby istniała nawet właściwość tak „bezużyteczna” jak R-TM. (Znowu wszystko to bełkot oparty na intuicji).

Raphael

Pytanie to zostało poruszone w artykule Henninga Fernau z 1994 roku. Henning stwierdza:

Jako przykład rozważamy rodzinę języków rekurencyjnych. Pozostaje otwarte pytanie, czy istnieje „naturalna” charakterystyka gramatyczna tej klasy językowej. Jak pokażemy poniżej, każda rodzina gramatyki charakteryzująca języki rekurencyjne musi mieć dziwne właściwości.

Kierujemy czytelnika, który jest ciekawy do poznania tych dziwnych właściwości, na papierze.

Yuval Filmus
źródło