Natknąłem się na wiele definicji języków rekurencyjnych i rekurencyjnie wyliczalnych. Ale nie mogłem do końca zrozumieć, co to jest.
Czy ktoś może mi powiedzieć, czym są proste słowa?
Nie całkiem. Powinieneś przeczytać kilka książek. Być może możemy polecić niektóre.
To powiedziawszy, język jest rekurencyjny, jeśli istnieje maszyna Turinga, niż zawsze może odpowiedzieć „tak” lub „nie”, jeśli dany ciąg znaków jest częścią tego języka. Jeśli zniesiemy ten wymóg, aby po prostu powiedzieć „tak” dla ciągów języka (może działać wiecznie, jeśli nie jest), wówczas otrzymamy rekurencyjnie wymienny język. Nietrudno zauważyć, że o języku rekurencyjnym decyduje maszyna Turinga, podczas gdy w języku rekurencyjnie wyliczalnym może być wyświetlana lista ciągów znaków (na przykład równoległe uruchamianie nieskończonej liczby maszyn Turinga - tak, jest to możliwe, patrz dove-tailing - na wszystkich ciągach alfabetu i wysyłanie łańcucha, jeśli odpowiednia TM go akceptuje). Istnieje wiele, wiele równoważnych definicji.
Problem ma charakter rekurencyjny lub rozstrzygalny, jeśli komputer potrafi obliczyć odpowiedź.
Problem można rekurencyjnie wyliczyć lub częściowo rozstrzygnąć, jeśli można przekonać maszynę, że odpowiedź jest pozytywna.
Język jest tylko zbiorem ciągów. Prawdopodobnie o nieskończonej liczności.
Język można wyliczyć rekurencyjnie, jeśli istnieje baza TM, która utrzymuje ciągi wyjściowe należące do języka (i tylko takie ciągi), tak że ostatecznie każdy ciąg w języku będzie w wyniku.
Język jest rekurencyjny, jeśli powyższa TM nie tylko wyświetla wszystkie ciągi w języku, ale także robi to w porządku! (powiedzmy leksykograficznie).
Jestem pewien, że z łatwością możesz wymyślić języki rekurencyjne (i zbudować bazę danych, która wypisze je na zamówienie). Trudno jest wymyślić rekurencyjne wyliczalne języki (które nie są rekurencyjne), chyba że przeczytasz więcej o nierozstrzygalności i diagonalizacji. Ale takie języki istnieją.
Języki rekurencyjne są rozstrzygalne przez jakąś maszynę Turinga, tzn. Istnieje baza TM, która może, biorąc pod uwagę dowolny ciąg wejściowy (nad odpowiednim alfabetem) poprawnie odpowiedzieć tak, jeśli ciąg jest w języku, lub nie, jeśli nie jest.
Rozpoznawane rekurencyjnie języki są rozpoznawane tylko, tzn. Istnieje Maszyna Turinga, która akceptuje, gdy łańcuch jest w danym języku, ale może zapętlać się na zawsze, jeśli łańcuch nie jest w tym języku.
źródło
Wydaje mi się, że główna różnica między językami rekurencyjnymi i wymiennymi polega na tym, że maszyna Turinga rekurencyjnego zatrzymuje się w nieokreślonym stanie, jeśli nie akceptuje ciągu znaków
Rekurencyjnie wyliczalna maszyna Turinga, jeśli nie zaakceptuje ciągu, może zatrzymać się w stanie nieskończonym lub pętli na zawsze, co nie ma miejsca w przypadku języków rekurencyjnych
źródło
==> Język jest rekurencyjny, jeśli istnieje maszyna Turinga, która akceptuje każdy ciąg w tym języku i odrzuca, jeśli nie jest w tym języku. na przykład weźmy maszynę Turinga M i Ciąg w: jeśli ciąg w jest członkiem maszyny Turinga M, wówczas M zatrzymuje się w swoim stanie końcowym, w przeciwnym razie odrzuca obliczenia. ==> ==> Język jest wyliczalny rekurencyjny, jeśli istnieje maszyna Turinga, która akceptuje każdy ciąg w tym języku i odrzuca, jeśli nie jest w tym języku, może być zapętlona na zawsze. na przykład weźmy maszynę Turinga M i String w: jeśli string w jest w języku, wówczas M zatrzymuje się w swoim stanie końcowym. W przeciwnym razie odrzuca obliczenia lub może być uruchamiany na zawsze.
źródło