Jak udowodnić istnienie liczby, której żaden algorytm nie może zapisać?

Mam problem:

Pokaż, że istnieje liczba rzeczywista, dla której nie istnieje żaden program działający nieskończenie długo i zapisujący cyfry dziesiętne tej liczby.

Przypuszczam, że można to rozwiązać, redukując go do problemu Halting, ale nie mam pojęcia, jak to zrobić.

Byłbym wdzięczny za linki do podobnych problemów w celu dalszej praktyki.

Jak wskazuje Sebastian, istnieje tylko (nieskończenie, ale) niezliczona ilość programów. Wyświetl je, aby utworzyć listę programów. Lista jest (nieskończenie, ale) niezliczona długa. Każdy program generuje jedną liczbę w R. Na tej podstawie możemy stworzyć (nieskończoną, ale) policzalną listę liczb w R. Teraz możemy zastosować argument przekątnej Cantora bezpośrednio, aby udowodnić, że nadal muszą istnieć inne liczby.

Nawiasem mówiąc, jeśli algorytm ma (skończone) argumenty, możesz po prostu przepisać to jako „dłuższą” listę programów, w których każdy program nie ma żadnych argumentów.

W odniesieniu do komentarza „Co, jeśli liczby rzeczywiste są dozwolone jako argument”, wówczas przesłanka pytania jest błędna: można wówczas wygenerować wszystkie liczby w R. Jeśli ktoś znajdzie liczbę, powiedz 皮 i twierdzi, że nie można jej obliczyć, mamy następujący „algorytm”:

func(number):
    return number

i zadzwoń do func (皮)

To jest o wiele prostsze. Istnieje tylko policzalna liczba algorytmów. Istnieje jednak niezliczona liczba liczb rzeczywistych. Więc jeśli spróbujesz je sparować, niektóre prawdziwe liczby pozostaną zawieszone.

$k$$1$$k$$0$

Liczba jest nieskończenie długą liczbą, która po przecinku dziesiętnym koduje wszystkie maszyny Turinga, które się nie zatrzymują. Z tym numerem można rozwiązać problem zatrzymania.

Możesz „przeszukać” bazę TM pod numerem i uruchomić ją równolegle. Jeśli TM się zatrzyma, to się zatrzyma. Jeśli nie, „znajdziesz jego kod w numerze”.

Istnieje wiele modyfikacji dowodu i powinieneś być w stanie je odtworzyć po pierwszej lekcji złożoności :-)

Punkt porusza się po ścieżce przez funcion y = 2x. Kiedy odcięta jest liczbą nieobliczalną, Punkt nie może obliczyć swojej ścieżki, ale wiemy, że trwa. Tak więc liczby w ogóle nieobliczalne mogą istnieć.