Dlaczego liczby obliczalne (w sensie Turinga) są policzalne?

Dlaczego liczby obliczalne (w sensie Turinga) są policzalne? To musi być bardzo oczywiste, ale obecnie po prostu tego nie widzę.

Zakładam, że twoja definicja liczby obliczalnej jest następująca: istnieje maszyna Turinga, która na wejściu zatrzymuje się z tym bitem liczby.$n$$n$

Załóżmy, że istnieje rekurencyjne wyliczenie maszyn Turinga, które wytwarzają liczby obliczalne. Możesz użyć diagonalizacji, aby wymyślić nową liczbę obliczalną, która nie jest częścią tego rekurencyjnego wyliczenia.

Kuszące jest wyliczanie liczb obliczalnych przez wyliczenie maszyn Turinga, ale nie każda maszyna Turinga odpowiada liczbie obliczalnej i ogólnie decyzja, czy maszyna Turinga zatrzymuje się na wszystkie dane wejściowe (nie mówiąc już o wyjściu 0 lub 1), nie jest obliczalna. Możliwe jest jednak wyliczenie wszystkich skutecznych liczb obliczeniowych, na przykład tych, których czas działania jest wielomianowy, za pomocą taktowanych maszyn Turinga.

Jeśli przez wyliczenie, masz na myśli, że istnieje bijection z liczbami naturalnymi (tj. Policzalnymi), to nie, liczby obliczalne nie są policzalne.

Dokładniej zdefiniujmy problem: „Maszyna Turinga z nadrukiem liczbowym (NPTM)” to maszyna Turinga, która dla każdego przejścia stanu nie może nic drukować lub może drukować dowolną cyfrę dziesiętną, znak minus lub kropkę. To wystarczy, aby wydrukować dziesiętne reprezentacje liczb rzeczywistych.

Pozwala zdefiniować obliczalną liczbę rzeczywistą jako dowolną liczbę rzeczywistą, którą można wydrukować z dowolnie długą reprezentacją, przy wystarczającym czasie, przez NPTM, zaczynając od pustej taśmy. Powiedzmy również, że liczba jest obliczana przez dane NPTM, jeśli zatrzymuje się po wydrukowaniu dobrze uformowanej liczby rzeczywistej (w którym to przypadku liczba ma skończoną reprezentację dziesiętną) lub w skończonym czasie wydrukuje dobrze uformowaną liczbę z kropką dziesiętną i zawsze zwiększy precyzję liczby, drukując więcej cyfr, biorąc pod uwagę coraz więcej czasu.

Ten późniejszy warunek jest konieczny, ponieważ jeśli mamy maszynę, która na przykład drukuje nieskończoną sekwencję jakiejś cyfry, powiedzmy 1111111111111111111..., nie można powiedzieć, że oblicza dowolną liczbę rzeczywistą, ponieważ liczby rzeczywiste mają nieskończoną reprezentację po prawej stronie strona okresu dziesiętnego. Z drugiej strony, jeśli urządzenie drukuje, 3.14a następnie przestaje drukować, ale nigdy się nie zatrzymuje, nie można powiedzieć, że oblicza dowolną liczbę rzeczywistą tylko dlatego, że precyzja liczby nie rośnie, a zatem ta konkretna maszyna nie będzie go konstruowała dalej.

Są to przykłady NPTM, które obliczają pewną liczbę. NPTM, który:

• drukuje 1, a następnie zatrzymuje się. Oblicza numer 1.
• drukuje 1.0, a następnie zatrzymuje się. Oblicza również numer 1.
• drukuje 1.0000000i drukuje zera na zawsze. Ten również oblicza numer 1.
• drukuje 3.14, a następnie zatrzymuje się. Oblicza liczbę 3.14.
• drukuje 3.14159i drukuje bez końca cyfry$\pi$. Ten oblicza liczbę$\pi$.
• drukuje -42., a następnie zatrzymuje się. Oblicza liczbę -42.

A są to przykłady NPTM, które nie obliczają żadnej liczby. NPTM, który:

• drukuje, 123123123a następnie drukuje sekwencję na 123zawsze. Nie oblicza liczby, ponieważ ta nieskończona sekwencja nie reprezentuje żadnej liczby rzeczywistej.
• drukuje, 1.0.0a następnie zatrzymuje się. Nie dlatego, że ta skończona sekwencja nie jest dobrze uformowana.
• drukuje, ....-..---a następnie zatrzymuje się. Nie dlatego, że nie jest to również dobrze uformowana liczba rzeczywista.
• nigdy niczego nie drukuje, ale też nigdy się nie zatrzymuje. Nie buduje się żadnej liczby.
• nigdy niczego nie drukuje i natychmiast zatrzymuje się. Nie zbudowano żadnej liczby.
• drukuje 3.14, nie zatrzymuje się, ale też nigdy nie drukuje niczego innego. Nie oblicza liczby, ponieważ jej precyzja nie rośnie z czasem.

Masz pomysł. Następnie mamy dwie klasy NPTM: te, które obliczają pewną liczbę rzeczywistą, i te, które nie.

Problem ze znalezieniem pewnej liczby dla liczb obliczalnych polega na tym, że nawet jeśli same NPTM są policzalne, nie możemy mieć procedury, która oddziela jeden rodzaj NPTM od drugiego.

Rozważ definicję zestawu policzalnego: dla zestawu $S$ aby być policzalnym, musi istnieć jakaś funkcja bijectywna $F: \mathbb{N} \rightarrow S$.

Aby „udowodnić”, że liczby obliczalne są policzalne, można pokusić się o zdefiniowanie takiej funkcji na podstawie zliczania NPTM (i tak często robili ludzie, gdy wierzą, że liczby obliczalne są policzalne). Coś takiego:

NPTM są policzalne, więc istnieje funkcja bijective $E_\text{NPTM}: \mathbb{N} -> \text{NPTM}$, dlatego możemy na zawsze wyliczyć wszystkie NPTM, które istnieją. Tak więc, aby wyliczyć wszystkie liczby obliczalne i precyzyjnie zdefiniować funkcję bijective$E_\text{Computabe}: \mathbb{N} \rightarrow \text{Computable}$, należy po prostu wyliczyć wszystkie NPTM, ale policzyć tylko te, które obliczają pewną liczbę rzeczywistą. Ale skąd wiemy, że oblicza pewną liczbę rzeczywistą?

Cóż, my nie. Zastanów się nad urządzeniem, które natychmiast drukuje 1.0, a następnie przestaje drukować i kontynuuje próbę rozwiązania problemu z korespondencją pocztową . Jeśli rozwiązuje problem, zatrzymuje się, a następnie maszyna właśnie obliczyła numer jeden. Ale ten problem jest nierozstrzygalny, więc nigdy się nie zatrzyma, a jeśli nigdy się nie zatrzyma, nigdy nie wyliczy prawdziwej liczby. Ale nie wiemy, czy się kiedykolwiek zatrzyma, ponieważ problem zatrzymania jest również nierozstrzygalny! Ponieważ nie ma możliwości sprawdzenia, czy ta konkretna maszyna i nieskończenie wiele innych maszyn albo oblicza, czy nie liczbę rzeczywistą, nie możemy w ten sposób zbudować / zdefiniować naszej funkcji bijectywnej.

Naiwny sposób definiowania bijectionu zawodzi i nietrudno jest udowodnić, że nie ma takiej możliwości. Jak sugerował Yuval Filmus, można zastosować diagonalizację.