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

[wersja nieprzejrzana][wersja nieprzejrzana]
Usunięta treść Dodana treść
zmiana nazwy / blad w nazwie
m angielska wersja z "recurency" nie występuje
Linia 1:
'''Język rekurencyjnie przeliczalny''' ([[język angielski|ang.]] ''recurencyrecursively enumerable language'') to [[język formalny]], dla którego istnieje [[algorytm]] decydujący czy dany [[łańcuch]] należy do tego języka, czy nie; przy tym algorytm ten musi zakończyć 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ć odpowiedzi.
 
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.