Да, спасибо, я про неположительные числа как-то не подумал :)
Поэтому строгая формулировка задачи должна звучать так: 1. Берется некоторое натуральное число Х. 2. Если Х - нечетное, оно заменяется на 3Х+1; если же Х четное, оно заменяется на Х/2. 3. Если Х>1, то возвращаемся к пункту 2. Доказать либо опровергнуть, что, независимо от выбора начального значения Х, рано или поздно алгоритм завершится (разрядность Х считается неограниченной).
Задача не решена до сих пор, хотя прошли десятилетия. Компьютерные эксперименты показывают, что рано или поздно Х всегда достигает единицы. Доказательства нет. Некоторые математики на основе теоремы Гёделя всерьез подозревают, что задача может быть неразрешимой в принципе - то есть, для любого Х рано или поздно получится 1, однако это невозможно вывести логическими преобразованиями из аксиом арифметики...
Для неограниченной разрядности сложнее, да. Отрезание младших нулей в двоичной записи - операция простая и приятная, осталось только доказать, что операция 3х+1 с этим самым отрезанием приведёт в конце концов к степени двойки.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
timeasmymeasure
no subject
Date: 2015-09-21 01:15 pm (UTC)Потому что там / , а не >>>
:)
no subject
Date: 2015-09-21 06:17 pm (UTC)Поэтому строгая формулировка задачи должна звучать так:
1. Берется некоторое натуральное число Х.
2. Если Х - нечетное, оно заменяется на 3Х+1; если же Х четное, оно заменяется на Х/2.
3. Если Х>1, то возвращаемся к пункту 2.
Доказать либо опровергнуть, что, независимо от выбора начального значения Х, рано или поздно алгоритм завершится (разрядность Х считается неограниченной).
Задача не решена до сих пор, хотя прошли десятилетия. Компьютерные эксперименты показывают, что рано или поздно Х всегда достигает единицы. Доказательства нет.
Некоторые математики на основе теоремы Гёделя всерьез подозревают, что задача может быть неразрешимой в принципе - то есть, для любого Х рано или поздно получится 1, однако это невозможно вывести логическими преобразованиями из аксиом арифметики...
no subject
Date: 2015-09-22 06:33 am (UTC)