Wikipedia

Język rekurencyjnie przeliczalny: Różnice pomiędzy wersjami

Przeglądaj historię interaktywnie
[wersja nieprzejrzana][wersja nieprzejrzana]
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
TXiKiBoT (dyskusja | edycje)
357 468 edycji
przepisanie hasła, dodanie przypisów, poprawienie błędnych informacji
Linia 1:
'''Język rekurencyjnie przeliczalny''' ([[język angielski|ang.]] ''recursively enumerable language'') to [[język formalny]], dlaokreślany któregojako istniejejęzyk [[algorytm]]'''klasy decydujący0''' czy danyw [[łańcuchHierarchia Chomsky'ego|hierarchii Chomsky'ego]] należy do tego języka, czyktóry nie;generowany przyjest tymprzez algorytm[[Gramatyka tenrekurencyjnie musiprzeliczalna|gramatyki zakończyćrekurencyjnie działanie z odpowiedzią pozytywną dla łańcuchów należących do języka, zaś dla łańcuchów spoza języka może dać odpowiedź negatywną lub w ogóle nie dać odpowiedziprzeliczalne]].
 
== Definicje ==
Jako przykład języka rekursywnie przeliczalnego można podać język przedstawiający wszystkie te [[Oprogramowanie|programy]], które się zatrzymują. Algorytm może po prostu uruchamiać kolejne programy i dawać odpowiedź pozytywną dla każdego, który się zatrzyma. Ponadto wszystkie [[język rekursywny|języki rekursywne]] są rekursywnie przeliczalne.
 
Istnieje kilka równoważnych definicji języka rekurencyjnie przeliczalnego:
Zamiennie używane są określenia: język częściowo rozstrzygalny oraz język częściowo obliczalny.
 
# [[Zbiór rekurencyjnie przeliczalny|Rekurencyjnie przeliczalny]] [[podzbiór]] [[Zbiór|zbioru]] wszystkich słów nad danym alfabetem.
# Język formalny, dla którego istnieje [[Maszyna Turinga|maszyna Turinga]] lub inna [[funkcja obliczalna]], która jest w stanie ponumerować wszystkie słowa języka.
# Język formalny ''L'', dla którego problem czy słowo <math>x \in L</math> jest [[Problem nierozstrzygalny|nierozstrzygalny]]<ref>{{cytuj stronę| url = http://home.agh.edu.pl/~tekomp/files/ta-wyklady/2-2-Gramatyki.pdf| tytuł = Gramatyki, wyprowadzenia, hierarchia Chomsky'ego| data dostępu = 15 września 2009| autor = dr inż. Janusz Majewski| opublikowany = 2009-03-25 | praca = [http://home.agh.edu.pl/~tekomp/ Materiały wykładowe dla studentów informatyki AGH - teoria automatów i języków formalnych]}}</ref>.
 
== Własności ==
 
Języki rekurencyjnie przeliczalne są [[Działanie wewnętrzne|zamknięte]] ze względu na następujące operacje:
 
* [[Domknięcie_Kleene'ego]] <math>L^*</math> z ''L''
* [[Konkatenacja|Konkatenację]] <math>L \circ P</math> języków ''L'' oraz ''P''
* [[Suma zbiorów|Sumę]] <math>L \cup P</math>
* [[Przekrój zbiorów|Przecięcie]] <math>L \cap P</math>
 
== Zobacz też ==
*[[przegląd zagadnień z zakresu matematyki]]
*[[funkcja rekurencyjna]]
*[[funkcja obliczalna]]
*[[teoria rekursji]]
 
== Przypisy ==
{{informatyka stub}}
 
{{stub}}
<references />
 
[[Kategoria:Języki formalne]]
Źródło: „https://pl.wikipedia.org/wiki/Język_rekurencyjnie_przeliczalny”