Język rekurencyjnie przeliczalny: Różnice pomiędzy wersjami
[wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
m angielskie tłumaczenie hasła |
m poprawka edycyjna... |
||
Linia 1:
'''Język rekursywnie przeliczalny''' ([[język angielski|ang.]] ''recursively 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.
|