Czy są jakieś zbiory policzalne, których nie można wyliczyć?

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

Ustanowiona terminologia jest obliczalna . Wiele osób powie, że „policzalne” i „policzalne” są synonimami. Zredagowałem to pytanie odpowiednio.

— Andrej Bauer,

@AndrejBauer, obliczalne i rekurencyjne są synonimami, prawda?

— rus9384

@ rus9384 Tak. Jeśli chodzi o słownictwo, powinna panować jasność, jak pisze Robert Irving Soare w Relatywistycznych obliczeniach Turinga i interaktywnym (2011) : Do 1995 r. Zamieszanie stało się nie do zaakceptowania. Napisałem artykuł na temat obliczalności i rekurencji dla byka. z Sym. Logika (1996) dotycząca historii i naukowych powodów, dla których powinniśmy używać „obliczalnego”, a nie „rekurencyjnego”, aby oznaczać „obliczalny”. „Rekurencyjne” powinno oznaczać „indukcyjne”, tak jak miało to miejsce w przypadku Dedekinda i Hilberta. Początkowo niewielu było gotowych dokonać takiej zmiany ...

— David Tonhofer,

Odpowiedzi:

Czy są jakieś przykłady zbiorów policzalnych, których nie można wyliczyć?

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 , 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. $\mathbb{N}$ $\mathbb{N}$

— David Richerby
źródło

@JorgePerez Nie i nie .

— David Richerby,

Dowodzi to istnienia, ale nie podaje żadnego przykładu ..

— BlueRaja - Danny Pflughoeft,

@ BlueRaja-DannyPflughoeft, podając przykład jest taki sam jak wyliczenie jednego. „Czy możesz podać przykład czegoś, czego nie możesz podać przykładu? Nie? Dlatego nie ma nic, czego nie możesz podać przykładu.” To w skrócie konstruktywizm matematyczny.

— Wildcard

Czy obraz funkcji zajętego bobra

byłby takim zestawem? Ponieważ

ściśle rośnie, trywialnie tworzy bijection z

, ale nie ma maszyny Turinga, która mogłaby wyliczyć

Σ

$\Sigma$

Σ

$\Sigma$

N

$\mathbb{N}$

Σ

$\Sigma$

— lub

@Wildcard Nie, podanie przykładu jest takie samo jak zdefiniowanie jednego, prawda? Istnieją zestawy, które można zdefiniować, ale nie można ich wyliczyć za pomocą algorytmu, takie jak zestaw wszystkich maszyn Turinga, które się nie zatrzymują.

— Tanner Swett,

Tak, każdy nierozstrzygalny (nierozstrzygalny) język ma tę właściwość.

Weźmy na przykład zestaw . $L = \{(x,M) \mid M \text{ does not halt on input } 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$

Na przemian można uruchomić maszynę dla kroków na i wyliczyć ty element $M$ $n$ $x$ $n$ $L$ .

albo zatrzymuje się, albo nie zatrzymuje na . Jeśli się zatrzyma, w końcu znajdziemy którym osiągniemy stan zatrzymania. Jeśli się nie zatrzyma, w końcu osiągniemy 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$

— jmite
źródło

Czy nie ma języków o niezliczonej złożoności?

— rus9384

@ rus9384 Nie jestem pewien, co masz na myśli. „Niepoliczalny” jest miarą wielkości; „złożoność” jest miarą tego, jak trudno jest podjąć decyzję. Ale nie ma niepoliczalnych języków łańcuchów skończonych: jeśli chcesz, aby język był niepoliczalny, musisz zezwolić na łańcuchy nieskończone (lub niepoliczalny „alfabet” lub oba).

— David Richerby

@DavidRicherby, cóż, jmite twierdzi, że każdy nierozstrzygnięty problem działa ze skończonymi łańcuchami? Myślę, że dotyczy to tylko każdego nierozstrzygalnego problemu rozpoznawalnego przez Turinga .

— rus9384

@ rus9384 Każdy język nad skończonym alfabetem jest policzalny, a obliczalność zwykle ignoruje nieskończone alfabety. Zobacz także to pytanie .

— jmite

@ rus9384 tak, język jest zbiorem skończonych ciągów znaków nad skończonym alfabetem. Każda taka rzecz jest policzalna. Jeśli chcesz uzyskać język niepoliczalny, musisz usunąć jeden lub oba wystąpienia „skończonego” z tej definicji. Ale jeśli ktoś po prostu powie „język”, oznacza zestaw skończonych ciągów znaków nad pewnym skończonym alfabetem.

— David Richerby,

$\Sigma^*$ $\Sigma = \{0,1\}$ $L \subseteq \Sigma^*$ $\Sigma^*$

— fade2black
źródło

Niekoniecznie mamy do czynienia z ciągami binarnymi. Istnieje wiele przypadków, w których moglibyśmy być zainteresowani ciągami znaków nad innymi alfabetami, a ludzie, którzy nazywają obliczalność „teorią rekurencji”, zwykle mają do czynienia bezpośrednio z zestawami liczb naturalnych. (Oznacza to, że same liczby są postrzegane jako prymitywne i nie są kodowane np. Jako ciągi binarne.)

— David Richerby

@DavidRicherby kilka tygodni temu twierdziłeś, że jestem przeciwny w komentarzach do odpowiedzi Yuvalsa. I to nie pierwszy podobny przypadek.

— fade2black

Yuval publikuje wiele odpowiedzi, a ja dużo komentarzy, więc musisz być bardziej szczegółowy. Z pewnością podtrzymuję mój komentarz powyżej, więc jeśli w pewnym momencie powiedziałem coś przeciwnego, to albo się myliłem, albo byłem zdezorientowany, albo źle mnie zrozumiałeś, albo mówiłem o konkretnym scenariuszu lub czymś takim. Przepraszam, jeśli cię zdezorientowałem, zwłaszcza jeśli zrobiłem to, mówiąc coś niejasnego lub nieprawidłowego!

— David Richerby

@DavidRicherby, w rzeczywistości każdy skończony alfabet można zredukować do postaci binarnej, więc nie rozumiem, jak to ma znaczenie. Czy też mamy w tym przypadku niezliczoną ilość nieskończonego alfabetu (gdzie każda cyfra ma unikalny symbol)?

— rus9384

{0, 1}

$\{0,1\}$