Marvin Minsky zadał mi następujące pytanie podczas mojego egzaminu ustnego:Najkrótszy łańcuch bitów którego nieskończone powtarzanie jest inna po odwróceniu
jak mrówka idzie drukuje liczbę binarną (na przykład 101) za każdym razem robi krok. Jaka jest minimalna długość, w cyfrach, liczba binarna może być, aby można było określić, w którym kierunku mrówka podróżuje, nie patrząc na początek lub na koniec sznurka? Mrówka mówi ci liczbę binarną.
Przykład: liczba binarna mrówka jest 101, a więc mrówka pozostawia ślad, który wygląda tak: 101101101101101101101. pamiętać, że nie ma sposobu, aby powiedzieć, w jaki sposób mrówka porusza. W związku z tym ten konkretny numer nie działa (ale może istnieć trzy cyfrowy numer binarny, który robi).
Przykład: Liczba binarna mrówki wynosi 011, a zatem mrówka pozostawia ślad, który wygląda następująco: 011011011011011011. Ponownie, nie ma sposobu, aby powiedzieć, w którą stronę wędruje mrówka, nie patrząc na końce struny .
Jaka jest odpowiedź na to pytanie? Zauważ, że odpowiedź nie może być po prostu przykładem działającego numeru binarnego. Odpowiedź musi zawierać dowód, że żadna liczba binarna o długości mniejszej niż n-1 nie zadziała, gdzie n jest długością przykładowej liczby binarnej, która działa. Dowód z wyczerpującego wyliczenia jest w porządku, ale nieprzyjemny. :)
Czy pytasz o rygorystyczny dowód matematyczny, czy po prostu upuszczasz imię? – gbn
Dlaczego pierwszy ślad nie przechodzi "101101101101101"? –
Głosowano, aby zamknąć jako "niezwiązane z programowaniem". Możesz wypróbować forum matematyczne na takie pytania: –