podzbiory nieskończonych zbiorów rekurencyjnych

Ostatnie pytanie egzaminacyjne brzmiało następująco:

jest nieskończonym zestawem rekurencyjnie wyliczalnym. Wykazać, że ma nieskończony rekurencyjny podzbiór. $A$ $A$

Niech jest nieskończony rekurencyjne podzbiór . Czy musi mieć podzbiór, którego nie można wyliczyć rekurencyjnie? $C$ $A$ $C$

Odpowiedziałem już 1.. W odniesieniu do 2. odpowiedziałem twierdząco i twierdziłem, co następuje.

Załóżmy, że wszystkie podzbiory były rekurencyjnie policzalne. Ponieważ jest nieskończony, zestaw mocy jest niepoliczalny, więc z założenia byłoby niepoliczalnie wiele zbiorów rekurencyjnie policzalnych. Ale rekurencyjnie policzalne zestawy są w bezpośredniej korespondencji z maszynami Turinga, które je rozpoznają, a maszyny Turinga są policzalne. Sprzeczność. Zatem musi mieć podzbiór, który nie jest wymienny rekurencyjnie. $C$ $C$ $C$ $C$

Czy to jest poprawne?

computability check-my-proof użytkownik1435
źródło

Na koniec nie jest całkiem poprawny, ponieważ każdy zestaw jest wyliczany przez nieskończenie wiele maszyn Turinga, a nie tylko jedną. Możesz jednak obejść ten problem.

Carl Mummert

@Carl: Ach, racja, dzięki - głupi błąd. Ale wszystko, czego potrzebuję, to zastrzyk do TM, a nie wstrzyknięcie, prawda? Zgodnie z definicją Turinga, z którą pracowała moja klasa, każda TM jest powiązana z jedną i tylko jedną funkcją. Różne zestawy -> różne funkcje rozpoznawania -> różne TM, które je obliczają.

user1435

! user1435: cofasz rzeczy w ostatnim zdaniu. Każda maszyna Turinga oblicza pojedynczą funkcję, ale każda funkcja obliczeniowa jest uzyskiwana z nieskończenie wielu maszyn Turinga.

Carl Mummert

Ale jeśli moja funkcja f odwzorowuje {funkcje rozpoznawania r} na {TM} poprzez f (r) = dowolną z nieskończenie wielu TM, które ją obliczają, mam zastrzyk, prawda? Albo przypuszczam, że mógłbym po prostu podzielić {TM} według relacji równoważności ~, która identyfikuje nieskończoność TM obliczających tę samą funkcję, a następnie odwzorować r na odpowiednią klasę równoważności.

1435

Carl ma rację, nie są w korespondencji jeden do jednego, każdy zestaw ce odpowiada nieskończenie wielu bazom TM. Biorąc pod uwagę inne zestawy obiektów, tak jak robisz to w komentarzu, nic nie zmienia, nie są one zbiorem baz TM.

Kaveh

Odpowiedzi:

Jest poprawna.

Każdy zestaw nieskończony ma niezdecydowany podzbiór, możesz użyć argumentu liczności: . W rzeczywistości większość jego podzbiorów jest nierozstrzygalna (i można zastąpić niezdecydowaną dowolną policzalną klasą języków, np.Arytmetyczną,analityczną, ...). $\aleph_0\leq C \implies \aleph_0 < 2^C$

Złe w tym argumencie jest to, że nie podaje on żadnych informacji o tym, jak trudny jest ten podzbiór. Zwykle chcemy podzestawu, który jest tak łatwy, jak to możliwe. Jednym ze sposobów na uzyskanie tego jest użycie diagonalizacji podobnej do argumentu liczności przy użyciu faktu, że jest rozstrzygalne: $C$

Określić , gdzie jest ty zestaw CE. Oczywiście . Ponadto można rozwiązać za pomocą wyroczni dla i . Jeśli więc jest rozstrzygalne, jest językiem biura. $D = \{ i \in C \mid i \notin W_i \}$ $W_i$ $i$ $D \subseteq C$ $D$ $C$ $K = \{ i \mid i\notin W_i\}$ $C$ $D$

Kaveh
źródło

„Każdy nieskończony zestaw ma niezdecydowany podzbiór”. Jest to słabsze niż twierdzenie, które próbowałem udowodnić. Próbowałem udowodnić, że C musi mieć podzbiór inny niż RE, a nie niepodlegający rozstrzygnięciu podzbiór. Czy moje roszczenie jest nadal prawidłowe?

user1435

Tak. Termin „nierozstrzygalny” jest nieco przeciążony (Wikipedia ma dobrą dyskusję ). Ta odpowiedź prawdopodobnie oznacza to, co próbujesz udowodnić.

David Lewis

@ user1435, tak, ten sam argument działa dla dowolnej policzalnej klasy języków, zaktualizowałem pytanie, aby było jasne.

Kaveh