Wiadomo, że z policzalnym zestawem algorytmów (charakteryzujących się liczbą Gödla) nie możemy obliczyć (zbudować algorytmu binarnego, który sprawdza przynależność) wszystkich podzbiorów N.
Dowód można podsumować w następujący sposób: jeśli moglibyśmy, to zestaw wszystkich podzbiorów N byłby policzalny (moglibyśmy powiązać z każdym podzbiorem liczbę Gödla algorytmu, który go oblicza). Ponieważ jest to fałsz, potwierdza to wynik.
Jest to dowód, który mi się podoba, ponieważ pokazuje, że problem jest równoważny podzbiorom N, których nie można policzyć.
Teraz chciałbym udowodnić, że problemu zatrzymania nie da się rozwiązać przy użyciu tylko tego samego wyniku (niepoliczalność N podzbiorów), ponieważ myślę, że są to bardzo bliski problem. Czy można to udowodnić w ten sposób?
Odpowiedzi:
Twierdzenie o zatrzymaniu, twierdzenie Cantora (nieizomorfizm zbioru i jego zestawu sił) oraz twierdzenie o niekompletności Goedela to wszystkie przypadki twierdzenia Lawpowa o stałym punkcie, który mówi, że dla dowolnej zamkniętej kartezjańskiej kategorii, jeśli istnieje mapa epimorficzna a następnie każdy ma ustalony punkt.e : A → ( A ⇒ B ) fa: B → B
Miłe wprowadzenie do tych pomysłów można znaleźć w tym poście na blogu Andreja Bauera .
źródło