Rekurzivně vyčíslitelný jazyk - Recursively enumerable language - Wikipedia

Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale její zdroje zůstávají nejasné, protože jí chybí vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Leden 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v matematika, logika a počítačová věda, a formální jazyk je nazýván rekurzivně spočetné (taky rozpoznatelné, částečně rozhodnutelné, semidecidable, Turing přijatelné nebo Turing rozpoznatelný) pokud se jedná o rekurzivně vyčíslitelná podmnožina v soubor všech možných slov přes abeceda jazyka, tj. pokud existuje a Turingův stroj který vyjmenuje všechny platné řetězce jazyka.

Rekurzivně vyčíslitelné jazyky jsou známé jako typ-0 jazyky v Chomského hierarchie formálních jazyků. Všechno pravidelný, bez kontextu, kontextové a rekurzivní jazyky lze rekurzivně spočítat.

Volá se třída všech rekurzivně vyčíslitelných jazyků RE.

Definice

Existují tři ekvivalentní definice rekurzivně vyčíslitelného jazyka:

1. Rekurzivně vyčíslitelný jazyk je a rekurzivně spočetné podmnožina v soubor všech možných slov přes abeceda z Jazyk.
2. Rekurzivně vyčíslitelný jazyk je formální jazyk, pro který existuje a Turingův stroj (nebo jiný vypočítatelná funkce ), který vyjmenuje všechny platné řetězce jazyka. Pokud je jazykem nekonečný, uvedený výčtový algoritmus lze zvolit tak, aby se vyhnul opakování, protože můžeme otestovat, zda řetězec vytvořený pro číslo n je "již" vyrobeno pro číslo, které je menší než n. Pokud je již vytvořen, použijte výstup pro vstup n + 1 místo toho (rekurzivně), ale znovu otestujte, zda je „nový“.
3. Rekurzivně vyčíslitelný jazyk je formální jazyk, pro který existuje Turingův stroj (nebo jiná vypočítatelná funkce), který se zastaví a přijme, když se zobrazí s jakýmkoli tětiva v jazyce jako vstup, ale může se buď zastavit a odmítnout, nebo smyčku navždy, když se zobrazí s řetězcem, který není v jazyce. Porovnejte to s rekurzivní jazyky, které vyžadují, aby se Turingův stroj ve všech případech zastavil.

Všechno pravidelný, bez kontextu, kontextové a rekurzivní jazyky lze rekurzivně spočítat.

Postova věta ukázat to RE, spolu s jeho doplněk jádro, odpovídají první úrovni aritmetická hierarchie.

Příklad

Sada zastavovací turingové stroje je rekurzivně vyčíslitelný, ale ne rekurzivní. Ve skutečnosti lze spustit Turingův stroj a přijmout, pokud se stroj zastaví, a proto je rekurzivně vyčíslitelný. Na druhou stranu je problém nerozhodnutelný.

Některé další rekurzivně vyčíslitelné jazyky, které nejsou rekurzivní, zahrnují:

• Problém s korespondencí
• Úmrtnost (teorie vypočítatelnosti)
• Entscheidungsproblem

Vlastnosti uzavření

Rekurzivně vyčíslitelné jazyky (REL) jsou Zavřeno v rámci následujících operací. To je, pokud L a P jsou dva rekurzivně vyčíslitelné jazyky, pak jsou následující jazyky také rekurzivně vyčíslitelné:

• the Kleene hvězda ${ displaystyle L ^ {*}}$ z L
• the zřetězení ${ Displaystyle L Circ P}$ z L a P
• the svaz ${ displaystyle L cup P}$
• the průsečík ${ displaystyle L cap P}$.

Rekurzivně nesčetné jazyky nejsou uzavřeny pod nastavený rozdíl nebo doplnění. Nastavený rozdíl ${ displaystyle L}$ − ${ displaystyle P}$ je rekurzivně vyčíslitelný, pokud ${ displaystyle P}$ je rekurzivní. Li ${ displaystyle L}$ je rekurzivně vyčíslitelný, pak doplněk ${ displaystyle L}$ je rekurzivně vyčíslitelný právě tehdy ${ displaystyle L}$ je také rekurzivní.

Reference

• Sipser, M. (1996), Úvod do teorie výpočtu, PWS Publishing Co..
• Kozen, D.C. (1997), Automaty a vypočítatelnost, Springer.

externí odkazy

• Složitost Zoo: Třída RE
• Přednáška diapozitivy