Czy pamięć RAM może obliczyć własną liczbę Gödla?

Możesz uzyskać numer Gödela pamięci RAM, ustawiając go jako listę poleceń i czyniąc tę listę liczbą całkowitą.

Tak więc, pomyślałem, że jest coś w rodzaju „RAM, który zwróci swój własny numer Gödela (powiedzmy ), będzie musiał zawierać informację , więc liczba całkowita będzie większa niż , więc nie zwróci własnego Gödela numer." $x$ $x$ $x$

Ale potem zauważyłem, że dla określonych liczb można wykonać kompresję, na przykład obliczenie zamiast wpisywania 100000 ... 000 w kodzie pamięci RAM. Prawdopodobnie liczba Gödla nie byłaby równa , ale przynajmniej może być. $10^{9999}$ $10^{9999}$

Pytanie: Czy istnieje pamięć RAM, która oblicza własny numer Gödela? Czy może być taki?

computability

— porażenie dziecięce
źródło

Nawiasem mówiąc, palsch, oto fajny film Numberphile o twojej ikonie użytkownika. :-)

— David Richerby,

@DavidRicherb Są to nie tylko piksele, ale spirala Ulama. Zaprogramowałem to jakiś czas temu dla mojego nauczyciela matematyki. Fioletowe piksele to pierwsze bliźniaki, czerwone to inne liczby pierwsze, a pomarańczowy piksel w środku to 1. :-)

— palsch

Ładny! Oto film Numberphile, który dosłownie dotyczy Twojej ikony użytkownika! :-D

— David Richerby,

Rozważmy obliczalną funkcję podaną przez . Według drugiego twierdzenia o rekurencji Kleene'a istnieje takie , że program o liczbie Gödela oblicza funkcję , tj. Program, który wypisuje dla każdego wejścia. To jest dokładnie ten program, którego szukasz: dla każdego wejścia wypisuje swój własny numer Gödela. $Q\colon \mathbb{N}\times\mathbb{N}\to\mathbb{N}$ $Q(x,y) = x$ $p$ $p$ $f(y) = Q(p,y)=p$ $p$

Taki program jest znany jako quine i istnieje on w każdym modelu obliczeniowym o dużej mocy Turinga.

— David Richerby
źródło

Czy możesz na pewno uruchomić ten program w ograniczonej pamięci pamięci RAM? Przypuszczam, że tutaj RAM oznacza pamięć o dostępie swobodnym ...

— Per Alexandersson,

@PerAlexandersson Nie, odnosi się do maszyny o dostępie swobodnym , modelu obliczeniowego o dużej mocy Turinga.

— David Richerby