Odstęp między

$HT(n)$ $n$ $BB(n) = \max HT(n)$

Co możemy powiedzieć o drugiej największej liczbie w ? Nazwij to . $HT(n)$ $BB_2(n)$

$BB_2(n)$ jest banalnie nieobliczalny, ponieważ pozwala obliczyć : wystarczy poczekać, aż zatrzyma się jeszcze jedna maszyna. Naiwnie oczekiwałbym, że przerwa będzie „zajęta jak bóbr”, rosnąc szybciej niż jakakolwiek funkcja obliczalna. Czy to da się udowodnić? $BB(n)$ $BB(n) - BB_2(n)$

computability

— Geoffrey Irving
źródło

Załóżmy, że jeden z n stanów jest nieosiągalny.

— mic

@mic: Nie sądzę, żeby to miało znaczenie. wydaje się wysoce nieprawdopodobne.

B B (n - 1) = B B_{2} (n)

$BB(n-1) = BB_2(n)$

— Geoffrey Irving

Będzie to zależeć od kodowania. Jeśli zmienisz stan akceptacji / odrzucenia, liczba stanów pozostanie taka sama, podobnie jak czas do zatrzymania, co spowoduje, że .

B B (n) = B B_{2} (n)

$BB(n)=BB_2(n)$

— Lance Fortnow

Dlatego pozwalam być zbiorem czasów zatrzymania, aby przerwa była niezerowa przez konstrukcję.

H T (n)

$HT(n)$

— Geoffrey Irving

Czy w ogóle można udowodnić, że różnica nie jest ostatecznie równa 1?

— Geoffrey Irving

-1

Liczba stanów jest tylko pojęciem złożoności opisu funkcji obliczeniowych w modelu, możesz wybrać dowolny model obliczeń i dowolne ich kodowanie jako ciągi binarne, a następnie przyjąć długość jako n i zdefiniować BB (n) na podstawie że i wszystkie interesujące wyniki dotyczące BB (n) byłyby nadal prawdziwe, nudna jest szczególna cecha modelu TM i liczby stanów.
Nic nie stoi na przeszkodzie, aby wybrały zmodyfikowany model baz TM. Zasadniczo pytania, które nie są niezmienne w przypadku takich zmian reprezentacji baz TM nie dotyczą obliczalności ani baz TM, ale konkretnej reprezentacji (jak BB (n) mod 2 itd.) I jeśli nie istnieje jakiś szczególny powód, dla którego są interesujące, nie dają warto ścigać Imho. Są fajnymi łamigłówkami, ale nie mają dużej wartości. l Należy zauważyć, że „BB (n) nie jest obliczalny” jest niezmienny przy zmianie reprezentacji baz TM.
Czy to pytanie jest niezmienne przy zmianie reprezentacji funkcji obliczalnych? Myślę, że odpowiedź brzmi „nie”.

ja. Rozważmy reprezentację, w której mamy dwa specjalne stany 0 i 1, a albo 0 jest początkowe i po prostu można przejść do 1 lub 0 jest nieosiągalne, a 1 jest początkowe. W tym kodowaniu różnica wynosi 1.

ii. Rozważ inną reprezentację, w której mamy UTM plus część, która zapisuje n bitów na taśmie przed przejściem do UTM. Tak więc pytanie staje się maksymalne f (x) - 2ndmax f (x), gdzie maksima są ponad n bitami i gdzie f jest dowolną funkcją obliczalną. Musimy tylko znaleźć funkcję obliczalną, jeśli nie jest to obliczalna. Nie myślałem o tym zbyt wiele, ale moje wnętrzności mówią, że istnieje taka funkcja obliczalna.

— Kaveh
źródło

Nic z tego nie ma znaczenia, ponieważ jako pojęcie obliczeniowe wybrałem standardowe maszyny Turinga. Zgadzam się, że istnieje kilka różnych wspólnych definicji (taśma jedno- lub dwustronna, niezależnie od tego, czy taśma zaczyna się od zera, czy jakiś specjalny pusty symbol), ale nic podobnego do wspomnianych wcześniej zakodowanych UTM.

— Geoffrey Irving

Użycie do zliczenia zupełnie innego kodowania byłoby innym i znacznie mniej interesującym pytaniem, ponieważ, jak mówisz, kodowanie może zostać wybrane do złamania pytania.

n

$n$

— Geoffrey Irving

Powiem inaczej: dlaczego jesteś zainteresowany odpowiedzią? To miłe łamigłówki, jak wiele innych na temat BB, do konkretnej reprezentacji baz TM, ale nie ujawniają niczego na temat obliczalności i obliczeń. Wybór standardu reprezentacji TM był arbitralnym działaniem, można było wybrać moją pierwszą reprezentację powyżej, a odpowiedź na twoje pytanie brzmiałaby 1. Tylko dlatego, że nazywa się standardem, nie wyróżnia go wśród reprezentacji.

— Kaveh

Nie różni się to od pytania, czy dowolne dowolnie wybrane równanie E Diofantienne ma rozwiązanie liczb całkowitych. Istnieje nieskończenie wiele takich równań, bez powodu, dla którego interesuje się E, nie jest to bardzo interesujące pytanie. Kiedy ludzie zadają pytania takie jak „obliczalność BB (n) mod 2”, myślą, że zadają głębokie pytania dotyczące obliczalności, podczas gdy w rzeczywistości bardziej przypomina pytanie o rozpuszczalność dowolnego dowolnie wybranego równania Diofantienne, tylko niektóre z nich wyglądają ładniej Oko.

— Kaveh

Interesuje mnie, ponieważ uważam, że odpowiedź jest taka sama dla wszystkich kodowań niedegerowanych: jest nie do udowodnienia, nie jest do udowodnienia, że jest nie do udowodnienia itp. Ale nie wiem, jak to sformułować, więc wybrałem jedno. Fakt, że jest trywialny w przypadku specjalnie wybranych kodowań, jest podobny do problemu zatrzymania, który można rozwiązać w przypadku maszyn zatrzymujących się przy budowie.

— Geoffrey Irving