Верна ли гипотеза Коллатца?

Вопрос

Возьмите любое натуральное число. Если оно чётное, разделите его пополам. Если нечётное — умножьте на 3 и прибавьте 1. Повторяйте.

Начав с 6, получим 3, 10, 5, 16, 8, 4, 2, 1. Начав с 27, числа поднимутся до 9232 и будут блуждать 111 шагов, прежде чем тоже упадут до 1. Дойдя до 1, вы застреваете в цикле 1, 4, 2, 1.

Гипотеза Коллатца утверждает, что любое начальное число в конце концов приходит к 1. Говорят, что немецкий математик Лотар Коллатц размышлял над этой задачей в 1930-х годах; её также называли задачей 3n + 1, сиракузской задачей и задачей Улама. Ребёнок может проверить её карандашом на бумаге. Ни один математик не сумел её доказать.

Что известно

Компьютеры проверили её для всех начальных чисел до 2⁷¹, то есть примерно до 2,4 × 10²¹. Все они приходят к 1.
Если бы гипотеза была неверна, существовало бы либо число, последовательность которого растёт бесконечно, либо другой цикл. Доказано, что любой такой цикл должен быть колоссально длинным — как минимум сотни миллиардов шагов.
В 1976 году Рихо Террас показал, что для почти всех начальных чисел последовательность в конце концов опускается ниже исходного значения. Это необходимый первый шаг, но «почти все» оставляет место для исключений, а опуститься ниже начала — не то же самое, что дойти до 1.
В 2019 году Теренс Тао доказал гораздо более сильное утверждение: для почти всех начальных чисел последовательность в конце концов становится меньше любой медленно растущей функции от начального числа — например, меньше логарифма от его логарифма. Его статья вышла в 2022 году. Это сильнейший известный результат, и сам Тао отмечал, что он и близко не решает гипотезу.
Про очень похожие задачи известно, что они неразрешимы. В 1972 году Джон Конвей показал, что некоторые обобщения правил Коллатца могут моделировать любую компьютерную программу, поэтому никакой алгоритм не может определить, чем закончатся их последовательности.

Основные гипотезы

Гипотеза верна

Почти все ожидают, что гипотеза верна. Её поддерживает простое вероятностное рассуждение: после каждого нечётного шага число умножается примерно на 3, но затем в среднем делится пополам примерно два раза, так что в долгосрочной перспективе оно уменьшается примерно в 3/4 раза за каждый нечётный шаг. Поэтому последовательности должны дрейфовать вниз и в конце концов попадать в 1.

Верна, но недоказуема

Поскольку обобщённые версии неразрешимы, некоторые математики подозревают, что и сама гипотеза Коллатца может быть верной, но недоказуемой в рамках стандартных аксиом. Кроме этой аналогии, свидетельств нет.

Контрпример существует, но он невообразимо велик

Меньшинство допускает, что огромное исключение существует далеко за пределами того, до чего могут дойти компьютеры. Ничто этого не подтверждает, но ничто и не исключает.

Где заканчивается понимание

Вероятностное рассуждение работает только в среднем. Трудность в том, что последовательность конкретного числа полностью определена, а не случайна, и никто не знает, как показать, что детерминированная последовательность действительно ведёт себя как среднее. Инструменты, дающие результаты «для почти всех чисел», не дотягиваются до «каждого числа».

В задаче смешаны два вида арифметики, которые обычно не взаимодействуют: умножение на 3 и деление на 2. Их взаимодействие перемешивает цифры числа так, что это выглядит случайным, и у современной математики нет общего метода, чтобы это контролировать. Поэтому Пол Эрдёш, по свидетельствам, сказал, что математика ещё не готова к таким задачам.

Есть и связь с вычислениями. Поскольку близкие правила могут кодировать любую программу, задача Коллатца находится у самой границы того, что вообще можно решить, — и эта тема связывает её с вопросами вроде P и NP.

Что могло бы дать ответ

Доказательство — скорее всего, через новый способ показывать, что детерминированный процесс ведёт себя как случайный; это имело бы значение далеко за пределами одной задачи.
Контрпример — число, которое никогда не приходит к 1, найденное вычислением или построенное теоретически.
Доказательство того, что гипотеза не зависит от стандартных аксиом, что само по себе было бы крупным результатом.