K1 - rekurencyjny. Istnieje algorytm rozstrzygający, czy automat należy do zbioru, czy nie. Wystarczy sprawdzić, czy istnieje ścieżka ze stanu startowego do dowolnego ze stanów akceptujących (na przykład przeszukiwanie grafu w głąb).
K2 - rekurencyjny. Istnieje algorytm sprawdzający, czy język generowany przez gramatykę bezkontekstową jest pusty: Twierdzenie 2.4. z
Kod: Zaznacz cały
http://www.google.com/url?sa=t&source=web&cd=6&ved=0CEQQFjAF&url=http%3A%2F%2Fwww.logic.amu.edu.pl%2Fimages%2Fa%2Fa0%2FS2L.pdf&rct=j&q=gramatyka%20bezkontekstowa%20czy%20j%C4%99zyk%20jest%20niepusty&ei=NA3-TaDXJMqi-gba8qznAw&usg=AFQjCNFOK5nC4H0Tb_5QnqMk286mVQpCPQ&sig2=78XEoYFIVsL2yyXVyU8GFg&cad=rja
.
K3 - rekurencyjnie przeliczalny. Rozważmy program:
Kod: Zaznacz cały
wczytaj M
for(int j=0; ; j++)
for(int i=0; i< j; i++)
uruchom M(i) na j sekund
jeśli M(i) się zatrzymał return tak
Łatwo uzasadnić dlaczego program się zatrzymuje wtedy i tylko wtedy, jeśli istnieje liczba dla której M się zatrzymuje.
Chyba nie jest rekurencyjny, ale nie potrafię tego udowodnić w tej chwili.