Какова «ближайшая» проблема к гипотезе Коллатца, которая была успешно решена?

Меня интересует «ближайшая» (и «самая сложная») проблема к гипотезе Коллатца , которая была успешно решена (на что Эрдос сказал, что «математика еще не созрела для таких задач»). Было доказано, что класс "коллатцовых" проблем неразрешим. Тем не менее, проблемы, которые в некоторой степени похожи, такие как MIU-игра Хофштадтера (решены, но, по общему признанию, скорее являются игрушечной проблемой), действительно разрешимы или были решены.

Смежные вопросы

Гипотеза Коллатца и Грамматика / Автоматы

reference-request open-problem nt.number-theory halting-problem computability ВЗН
источник

Поскольку это HTML, а не LaTeX, будет проще, если вы укажете ссылки там, где они уместны.

Суреш Венкат

TCS / эмпирические углы на collatz / refs

vzn

Есть по крайней мере один человек, который утверждает, что «гипотеза Коллатца» является уникальным ответом на ваш вопрос. Я скептически отношусь к полноте связанного доказательства, но пока не потратил достаточно времени на его анализ.

Бойд Стивен Смит младший

К вашему сведению, это новая статья Мишеля, в которой хорошо освещается область, связывающая неразрешимость с общей теоретико-числовой структурой, проблемы теории чисел из соревнования занятых бобров

vzn

Ответы:

Расширенный комментарий:

Коллатц-подобные последовательности могут быть вычислены с помощью небольших машин Тьюринга, имеющих мало символов и состояний. В « Маленьких машинах Тьюринга и обобщенном соревновании занятых бобров » П. Мишеля (2004 г.) есть хорошая таблица, в которой коллац-подобные проблемы позиционируются между разрешимыми ТМ (для которых решается проблема остановки) и универсальными ТМ.

введите описание изображения здесь

Существуют ТМ, которые вычисляют коллатц-подобные последовательности, для которых разрешимость все еще остается открытой проблемой: , и (где - множество машин Тьюринга с состояниями и символами). Я не знаю, были ли результаты подтверждены. $TM(5,2)$ $TM(3,3)$ $TM(2,4)$ $TM(k,l)$ $k$ $l$

Из заключения статьи:

... Нынешняя коллатцоподобная линия уже находится на самом низком из возможных уровней, с возможным исключением , но мы предполагаем, что все машины в этом наборе могут быть доказаны разрешимыми ... $TM(4,2)$

См. Также « Сложность небольших универсальных машин Тьюринга: обзор » Д. Вудса и Т. Нери (2007).

Другим примером коллатцоподобной проблемы, для которой разрешимость является открытой, является система тегов Поста: ; недавний анализ см. « О границах разрешимости и неразрешимости в системах меток. Теоретические и экспериментальные результаты » Л. Де Моля (2009). $\mu = 2, v=3,0\rightarrow 00, 1 \rightarrow 1101$

Марцио де Биаси
источник

в дополнение к ответу: Конвей показал, что существуют коллатц-подобные последовательности, которые неразрешимы. ams.org/mathscinet-getitem?mr=392904 . то есть коллатц-подобная последовательность сама может симулировать универсальную машину Тьюринга.

Сашо Николов

Спасибо! опрос Митчелла / результаты очень крутые! Для пояснения в таблице, «Т» в ячейке указывает на существование TM (k, l), что эквивалентно гипотезе Коллатца. перспектива также предполагает, что гипотеза Коллатца является не просто изолированным теоретическим любопытством, но, возможно, поверхностным явлением чего-то более глубокого в теории вычислимости. ps также очень интересно, были ли когда-нибудь решены когда-нибудь открытые "проблемы типа collatz" ...?

ВЗН

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

Крейг Файнштейн
источник

Я не думаю, что это удовлетворяет «самой сложной» части вопроса, поскольку мотивированный ученик начальной школы может немного подумать о ключевой идее доказательства вашего утверждения.

Йонатан N

Но если он будет более сложным и все еще решен, он больше не будет напоминать гипотезу Коллатца. Кроме того, заголовок его вопроса указывает на то, что он отдает приоритет «самым близким», а не «самым сложным».

Крейг Файнштейн