Zbiór jest policzalny, jeśli ma bijectję z liczbami naturalnymi, i jest obliczalny (ce), jeśli istnieje algorytm, który wylicza jego elementy.
Każdy nieskończony obliczalny zestaw wyliczalny musi być policzalny, ponieważ możemy zbudować bijection z wyliczenia.
Czy są jakieś przykłady zbiorów policzalnych, których nie da się wyliczyć? Oznacza to, że istnieje bijection między tym zbiorem a liczbami naturalnymi, ale nie ma algorytmu, który mógłby obliczyć ten biject.
computability
semi-decidability
Peter Olson
źródło
źródło
Odpowiedzi:
Tak. Wszystkie podzbiory liczb naturalnych są policzalne, ale nie wszystkie z nich są policzalne. (Dowód: istnieje niepoliczalnie wiele różnych podzbiorów ale tylko licznie wiele maszyn Turinga, które mogłyby działać jako wyliczacze.) Tak więc każdy podzbiór N , o którym wiesz, że nie jest wyliczalny rekurencyjnie, jest przykładem - takim jak zbiór wszystkich liczb kodujących Turinga maszyny, które zatrzymują się przy każdym wejściu.N N
źródło
Tak, każdy nierozstrzygalny (nierozstrzygalny) język ma tę właściwość.
Weźmy na przykład zestaw .L = { ( x , M) ∣ M nie zatrzymuje się na wejściu x }
Załóżmy, że mamy algorytm, który może wyliczyć członków tego zestawu. Gdyby istniał taki algorytm, moglibyśmy go użyć do rozwiązania problemu zatrzymania przy wejściach , stosując następujący algorytm:x , M
albo zatrzymuje się, albo nie zatrzymuje na x . Jeśli się zatrzyma, w końcu znajdziemy n, w którym osiągniemy stan zatrzymania. Jeśli się nie zatrzyma, w końcu osiągniemy ( M , x ) w naszym wyliczeniu.M. x n ( M, x )
Mamy zatem redukcję i możemy stwierdzić, że takie wyliczenie nie istnieje.
Zauważ, że takie wyliczenia mogą istnieć w przypadku problemów częściowo rozstrzygalnych. Na przykład można wyliczyć zestaw wszystkich par wejściowych maszyny zatrzymującej, wyliczając wszystkie możliwe ślady wszystkich wykonań maszyny Turinga po krokach i odfiltrować te, które nie kończą się w stanie zatrzymania.n
źródło
źródło