Jaki jest „najbliższy” problem hipotezy Collatza, który został pomyślnie rozwiązany?

Interesuje mnie „najbliższy” (i „najbardziej złożony”) problem hipotezy Collatza , który został pomyślnie rozwiązany (o czym słynie Erdos „matematyka nie jest jeszcze dojrzała na takie problemy”). Udowodniono, że klasa problemów typu „Collatz” jest nierozstrzygalna. Jednak problemy, które są nieco podobne, takie jak gra MIU Hofstadtera (rozwiązane, ale co prawda bardziej problem z zabawkami) są rzeczywiście rozstrzygalne lub zostały rozwiązane.

Powiązane pytania

Collatz Conjecture & Grammars / Automata

— vzn
źródło

Ponieważ jest to HTML, a nie LaTeX, łatwiej jest wstawić odniesienia tam, gdzie są one istotne.

— Suresh Venkat

TCS / empirical Angles on collatz / refs

— vzn

Jest co najmniej jedna osoba, która twierdzi, że „hipoteza Collatza” jest unikalną odpowiedzią na twoje pytanie. Jestem sceptyczny co do kompletności połączonego dowodu, ale jeszcze nie spędziłem wystarczająco dużo czasu na jego analizie.

— Boyd Stephen Smith Jr.

fyi tutaj jest nowy artykuł Michela, który ładnie analizuje obszar łączący nierozstrzygalność z ogólną teorią liczb, problemy w teorii liczb z zajętej konkurencji bobrów

— dniu

Odpowiedzi:

Rozszerzony komentarz:

Sekwencje podobne do Collatza mogą być obliczane przez małe maszyny Turinga mające niewiele symboli i stanów. W „ Małych maszynach Turinga i uogólnionym konkursie zajętych bobrów ” P. Michela (2004) znajduje się ładny stół, który umieszcza problemy podobne do Collatza między rozstrzygającymi TM (dla których rozstrzygalny jest problem zatrzymania) a Universal TM.

wprowadź opis zdjęcia tutaj

$TM(5,2)$ $TM(3,3)$ $TM(2,4)$ $TM(k,l)$ $k$ $l$

Z podsumowania pracy:

$TM(4,2)$

Zobacz także „ Złożoność małych uniwersalnych maszyn Turinga: ankieta ” D. Woodsa i T. Neary'ego (2007).

$\mu = 2, v=3,0\rightarrow 00, 1 \rightarrow 1101$

— Marzio De Biasi
źródło

w celu uzupełnienia odpowiedzi: Conway wykazał, że istnieją sekwencje podobne do Collatza, które są nierozstrzygalne ams.org/mathscinet-getitem?mr=392904 . tzn. sekwencja przypominająca kolizję może sama symulować uniwersalną maszynę Turinga.

— Sasho Nikolov

dzięki! ankieta / wyniki mitchell są bardzo fajne! wyjaśnienie fyi w tabeli, „T” w komórce wskazuje, że istnieje TM (k, l), która jest równoważna hipotezie Collatza. perspektywa sugeruje również, że hipoteza Collatza jest nie tylko odosobnioną ciekawostką teoretyczną, ale być może zjawiskiem powierzchniowym czegoś głębszego w teorii obliczeń. ps jest również bardzo zainteresowany tym, czy któreś z otwartych kiedyś problemów typu „collatz like problems” zostały kiedykolwiek rozwiązane…?

— vzn

$T: \mathbb N \rightarrow \mathbb N$ $T(n)=n/2$ $n$ $T(n)=n+1$ $n$ $n \in \mathbb N$ $k \in \mathbb N$ $T^{(k)}(n)=1$

$T(n)=n+1$ $n$ $T(n)=3n+1$ $n$

— Craig Feinstein
źródło

Nie wydaje mi się, żeby spełniało to „najbardziej złożoną” część pytania, ponieważ zmotywowany uczeń szkoły podstawowej może trochę zastanowić się nad kluczową ideą dowodu twojego oświadczenia.

— Yonatan N

Ale jeśli jest bardziej złożony i nadal rozwiązany, nie będzie już przypominał hipotezy Collatza. Co więcej, tytuł jego pytania wskazuje, że daje pierwszeństwo „najbliższemu” przed „najbardziej złożonym”.

— Craig Feinstein