Język rekurencyjnie przeliczalny

Język rekurencyjnie przeliczalny (ang. recursively enumerable language) to język formalny określany jako język klasy 0 w hierarchii Chomsky'ego, który generowany jest przez gramatykę kombinatoryczną.

Definicje

Istnieje kilka równoważnych definicji języka rekurencyjnie przeliczalnego:

1. Rekurencyjnie przeliczalny podzbiór zbioru wszystkich słów nad danym alfabetem.
2. Język formalny, dla którego istnieje maszyna Turinga lub inna funkcja obliczalna, która jest w stanie ponumerować wszystkie słowa języka.
3. Język formalny L, dla którego problem czy słowo $x \in L$ jest nierozstrzygalny.

Własności

Języki rekurencyjnie przeliczalne są zamknięte ze względu na następujące operacje:

• Domknięcie Kleene'ego $L^*$ z L
• Konkatenację $L \circ P$ języków L oraz P
• Sumę $L \cup P$
• Przecięcie $L \cap P$

Zobacz też

• funkcja rekurencyjna
• teoria rekursji