Quel est le problème «le plus proche» de la conjecture de Collatz qui a été résolu avec succès?

Je m'intéresse au problème "le plus proche" (et "le plus complexe") de la conjecture de Collatz qui a été résolue avec succès (ce que Erdos a dit fameusement "les mathématiques ne sont pas encore mûres pour de tels problèmes"). Il a été prouvé qu'une classe de problèmes "de type Collatz" est indécidable. Cependant, des problèmes qui sont vaguement similaires, comme le jeu MIU de Hofstadter (résolu, mais certes plus d'un problème de jouet) sont en effet décidables ou ont été résolus.

Questions connexes

Collatz de conjectures et grammaires / automates

reference-request open-problem nt.number-theory halting-problem computability vzn
la source

Comme il s'agit de HTML et non de LaTeX, c'est plus facile si vous insérez les références là où elles sont pertinentes.

Suresh Venkat

TCS / angles empiriques sur collatz /

refs

Il y a au moins une personne qui prétend que "la conjecture de Collatz" est la réponse unique à votre question. Je suis sceptique quant à l'exhaustivité de la preuve liée, mais je n'ai pas encore passé assez de temps à l'analyser.

Boyd Stephen Smith Jr.,

fyi voici un nouvel article de Michel qui étudie joliment la zone reliant l'indécidabilité à un cadre général de théorie des nombres, les problèmes de théorie des nombres de la concurrence

active des

Réponses:

Un commentaire étendu:

Les séquences de type Collatz peuvent être calculées par de petites machines de Turing ayant peu de symboles et d'états. Dans " Petites machines de Turing et concurrence généralisée des castors occupés " de P. Michel (2004), il y a un joli tableau qui positionne les problèmes de type Collatz entre les MT décidables (pour lesquelles le problème d'arrêt est décidable) et les MT universelles.

entrez la description de l'image ici

Il existe des MT qui calculent des séquences de type Collatz pour lesquelles la décidabilité est toujours un problème ouvert: , et (où est l'ensemble de Turing Machine avec états et symboles). Je ne sais pas si les résultats ont été améliorés. $TM(5,2)$ $TM(3,3)$ $TM(2,4)$ $TM(k,l)$ $k$ $l$

De la conclusion du document:

... La ligne actuelle de Collatz est déjà à son niveau le plus bas possible, à l'exception peut-être de , mais nous supposons que toutes les machines de cet ensemble peuvent se révéler décidables ... $TM(4,2)$

Voir aussi " La complexité des petites machines universelles de Turing: une enquête " par D. Woods et T. Neary (2007).

Un autre exemple de problème de type Collatz pour lequel la décidabilité est un problème ouvert est le système de balises de Post: ; pour une analyse récente, voir « Sur les limites de la solvabilité et de l'insolvabilité dans les systèmes d'étiquettes. Résultats théoriques et expérimentaux » de L. De Mol (2009). $\mu = 2, v=3,0\rightarrow 00, 1 \rightarrow 1101$

Marzio De Biasi
la source

pour compléter la réponse: Conway a montré qu'il existe des séquences de type Collatz indécidables ams.org/mathscinet-getitem?mr=392904 . c'est-à-dire qu'une séquence de type collatz peut elle-même simuler une machine de turing universelle.

Sasho Nikolov

THX! le sondage mitchell / les résultats sont très cool! Pour plus de clarté dans le tableau, un "T" dans une cellule indique qu'il existe une MT (k, l) équivalente à la conjecture collatz. la perspective suggère également que la conjecture collatz n'est pas simplement une curiosité théorique isolée mais peut-être un phénomène de surface de quelque chose de plus profond dans la théorie de la calculabilité. ps aussi très intéressé si des "problèmes de type collatz" une fois ouverts ont déjà été résolus ...?

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
la source

Je ne pense pas que cela satisfasse la partie "la plus complexe" de la question, car un élève de niveau primaire motivé peut identifier l'idée clé derrière la preuve de votre déclaration avec un peu de réflexion.

Yonatan N

Mais si elle est plus complexe et toujours résolue, elle ne ressemblera plus à la conjecture de Collatz. En outre, le titre de sa question indique qu'il donne la priorité au "plus proche" sur le "plus complexe".

Craig Feinstein