Qual é o problema "mais próximo" da conjectura de Collatz que foi resolvido com sucesso?

Estou interessado no problema "mais próximo" (e "mais complexo") da conjectura de Collatz que foi resolvida com sucesso (que Erdos disse famosa "a matemática ainda não está propícia a tais problemas"). Está provado que uma classe de problemas "tipo Collatz" é indecidível. No entanto, problemas vagamente semelhantes, como o jogo MIU de Hofstadter (resolvido, mas reconhecidamente mais um problema de brinquedo) são realmente decidíveis ou foram resolvidos.

Perguntas relacionadas

Collatz Conjectura e gramáticas / Autômatos

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

Como este é HTML e não LaTeX, é mais fácil incluir as referências onde elas são pertinentes.

Suresh Venkat

TCS / ângulos empíricos em collatz / refs

vzn

Há pelo menos uma pessoa que afirma que "a conjectura de Collatz" é a resposta única para sua pergunta. Sou cético em relação à integridade da prova vinculada, mas ainda não passei tempo suficiente analisando-a.

Boyd Stephen Smith Jr.

fyi aqui é um novo papel por Michel que bem examina a área de ligação indecidibilidade para um quadro teórico número geral, problemas na teoria dos números de ocupado castor competição

vzn

Respostas:

Um comentário estendido:

Seqüências semelhantes a collatz podem ser calculadas por pequenas máquinas de Turing com poucos símbolos e estados. Em " Pequenas máquinas de Turing e competição generalizada de castores ocupados " de P. Michel (2004), há uma boa tabela que posiciona problemas semelhantes a Collatz entre TMs decidíveis (para as quais o problema de parada é decidível) e TMs universais.

insira a descrição da imagem aqui

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

Da conclusão do trabalho:

$TM(4,2)$

Veja também " A complexidade das pequenas máquinas universais de Turing: uma pesquisa " de D. Woods e T. Neary (2007).

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

Marzio De Biasi
fonte

para complementar a resposta: Conway mostrou que existem sequências semelhantes a Collatz que são indecidíveis ams.org/mathscinet-getitem?mr=392904 . isto é, uma sequência semelhante a uma coleira pode simular uma máquina de turing universal.

Sasho Nikolov

valeu! a pesquisa / resultados da mitchell são muito legais! Para sua clarificação na tabela, um "T" em uma célula indica que existe uma TM (k, l) que é equivalente à conjectura de collatz. a perspectiva também sugere que a conjectura de Collatz não é apenas uma curiosidade teórica isolada, mas possivelmente um fenômeno superficial de algo mais profundo na teoria da computabilidade. ps também está muito interessado se algum "problema semelhante a uma colatz" aberto já foi resolvido ...?

$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
fonte

Eu não acho que isso satisfaça a parte "mais complexa" da pergunta, pois um aluno motivado da escola pode identificar a idéia principal por trás da prova de sua afirmação com um pouco de reflexão.

Yonatan N

Mas se for mais complexo e ainda resolvido, não se parecerá mais com a Conjectura Collatz. Além disso, o título de sua pergunta indica que ele dá prioridade ao "mais próximo" do que ao "mais complexo".

22815 Craig Feinstein