Was ist das Problem, das der erfolgreich gelösten Collatz-Vermutung am nächsten kommt?

Ich interessiere mich für das "nächstgelegene" (und "komplexeste") Problem der Collatz-Vermutung , das erfolgreich gelöst wurde (was laut Erdos "Mathematik ist noch nicht reif für solche Probleme"). Es wurde bewiesen, dass eine Klasse von "Collatz-ähnlichen" Problemen unentscheidbar ist. Vage ähnliche Probleme wie das MIU-Spiel von Hofstadter (gelöst, aber zugegebenermaßen eher ein Spielzeugproblem) sind in der Tat entscheidbar oder wurden gelöst.

Antworten:

Ein erweiterter Kommentar:

Collatz-ähnliche Sequenzen können von kleinen Turing-Maschinen mit wenigen Symbolen und Zuständen berechnet werden . In " Small Turing Machines und Generalized Busy Beaver Competition " von P. Michel (2004) gibt es einen schönen Tisch, der Collatz-ähnliche Probleme zwischen entscheidbaren TMs (für die das Halteproblem entscheidbar ist) und Universal TMs positioniert.

Bildbeschreibung hier eingeben

Es gibt TMs dass compute Collatz-ähnliche Sequenzen , für die die decidability noch ein offenes Problem: , und (wobei ist der Satz von Turing Machine mit Zuständen und Symbolen). Ich weiß nicht, ob die Ergebnisse verbessert wurden. $TM(5,2)$ $TM(3,3)$ $TM(2,4)$ $TM(k,l)$ $k$ $l$

Aus dem Fazit der Arbeit:

... Die gegenwärtige Collatz-ähnliche Linie befindet sich bereits auf dem niedrigstmöglichen Niveau, mit der möglichen Ausnahme von , aber wir vermuten, dass alle Maschinen in diesem Satz als entscheidbar erwiesen werden können ... $TM(4,2)$

Siehe auch " Die Komplexität kleiner universeller Turingmaschinen: eine Umfrage " von D. Woods und T. Neary (2007).

Ein weiteres Beispiel für ein Collatz-ähnliches Problem, für das die Entscheidbarkeit ein offenes Problem darstellt, ist das Post-Tag-System: ; Für eine aktuelle Analyse siehe " Über die Grenzen der Lösbarkeit und Unlösbarkeit in Tag-Systemen. Theoretische und experimentelle Ergebnisse " von L. De Mol (2009). $\mu = 2, v=3,0\rightarrow 00, 1 \rightarrow 1101$

Marzio De Biasi
quelle

zur Ergänzung der Antwort: Conway hat gezeigt, dass es Collatz-ähnliche Sequenzen gibt, die nicht zu entscheiden sind ams.org/mathscinet-getitem?mr=392904 . dh eine collatzartige Sequenz kann selbst eine universelle Turingmaschine simulieren.

Sasho Nikolov

Danke! Die Mitchell Umfrage / Ergebnisse sind sehr cool! Zur Klarstellung in der Tabelle zeigt ein "T" in einer Zelle an, dass ein TM (k, l) existiert, das der Kollatz-Vermutung entspricht. Die Perspektive legt auch nahe, dass die Collatz-Vermutung nicht nur eine isolierte theoretische Neugierde ist, sondern möglicherweise ein Oberflächenphänomen von etwas, das tiefer in der Berechenbarkeitstheorie liegt. ps auch sehr interessiert, ob einmal offene "collatz like problems" jemals gelöst wurden ...?

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
quelle

Ich denke nicht, dass dies den "komplexesten" Teil der Frage befriedigt, da ein motivierter Grundschüler die Schlüsselidee hinter dem Beweis Ihrer Aussage mit ein wenig Nachdenken identifizieren kann.

Yonatan N

Wenn es jedoch komplexer und immer noch gelöst ist, ähnelt es nicht mehr der Collatz-Vermutung. Darüber hinaus weist der Titel seiner Frage darauf hin, dass er "am nächsten" vor "am komplexesten" steht.

Craig Feinstein

Was ist das Problem, das der erfolgreich gelösten Collatz-Vermutung am nächsten kommt?

Verwandte Fragen

Antworten: