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

14

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

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

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

ВЗН
источник
5
Поскольку это HTML, а не LaTeX, будет проще, если вы укажете ссылки там, где они уместны.
Суреш Венкат
Есть по крайней мере один человек, который утверждает, что «гипотеза Коллатца» является уникальным ответом на ваш вопрос. Я скептически отношусь к полноте связанного доказательства, но пока не потратил достаточно времени на его анализ.
Бойд Стивен Смит младший
К вашему сведению, это новая статья Мишеля, в которой хорошо освещается область, связывающая неразрешимость с общей теоретико-числовой структурой, проблемы теории чисел из соревнования занятых бобров
vzn

Ответы:

22

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

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

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

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

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

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

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

Другим примером коллатцоподобной проблемы, для которой разрешимость является открытой, является система тегов Поста: ; недавний анализ см. « О границах разрешимости и неразрешимости в системах меток. Теоретические и экспериментальные результаты » Л. Де Моля (2009).μзнак равно2,vзнак равно3,000,11101

Марцио де Биаси
источник
8
в дополнение к ответу: Конвей показал, что существуют коллатц-подобные последовательности, которые неразрешимы. ams.org/mathscinet-getitem?mr=392904 . то есть коллатц-подобная последовательность сама может симулировать универсальную машину Тьюринга.
Сашо Николов
Спасибо! опрос Митчелла / результаты очень крутые! Для пояснения в таблице, «Т» в ячейке указывает на существование TM (k, l), что эквивалентно гипотезе Коллатца. перспектива также предполагает, что гипотеза Коллатца является не просто изолированным теоретическим любопытством, но, возможно, поверхностным явлением чего-то более глубокого в теории вычислимости. ps также очень интересно, были ли когда-нибудь решены когда-нибудь открытые "проблемы типа collatz" ...?
ВЗН
5

T:NNT(N)знак равноN/2NT(N)знак равноN+1NNNКNT(К)(N)знак равно1

T(N)знак равноN+1NT(N)знак равно3N+1N

Крейг Файнштейн
источник
2
Я не думаю, что это удовлетворяет «самой сложной» части вопроса, поскольку мотивированный ученик начальной школы может немного подумать о ключевой идее доказательства вашего утверждения.
Йонатан N
1
Но если он будет более сложным и все еще решен, он больше не будет напоминать гипотезу Коллатца. Кроме того, заголовок его вопроса указывает на то, что он отдает приоритет «самым близким», а не «самым сложным».
Крейг Файнштейн