1

In many sources there are notes that Conway proved that a natural generalization of the Collatz problem is algorithmically undecidable. Let's look at Wikipedia:

Specifically, he considered functions of the form:

$g(n) = a_{i}n+b_{i}$, where $n \equiv i \pmod{P} $

and $a_{0},b_{0},a_{P-1},b_{P-1}$ are rational numbers which are so chosen that $g(n)$ is always an integer.

https://en.wikipedia.org/wiki/Collatz_conjecture#Undecidable_generalizations

Conway used turing-complete esoteric programming language FRACTRAN, to prove that generalization of the Collatz problem is algorithmically undecidable. But FRACTRAN games as defined here:

https://raganwald.com/2020/05/03/fractran.html

are not what function $g(n)$ is. FRACTRAN games are:

$h(n) = a_{i}n$, where $n \equiv i \pmod{P} $

and $a_{0},a_{P-1}$ are rational numbers which are so chosen that $g(n)$ is always an integer.

So $b_{i}$ is always zero. There are no single FRACTRAN program with any addition, there are only fractions like here (PRIMEGAME):

${\displaystyle \left({\frac {17}{91}},{\frac {78}{85}},{\frac {19}{51}},{\frac {23}{38}},{\frac {29}{33}},{\frac {77}{29}},{\frac {95}{23}},{\frac {77}{19}},{\frac {1}{17}},{\frac {11}{13}},{\frac {13}{11}},{\frac {15}{2}},{\frac {1}{7}},{\frac {55}{1}}\right)}$

Of course we can say that that $h(n)$ is special case of $g(n)$, but let's be honest - these are completely different functions and every one who was dealing with Collatz-like functions knows that. So why people are writing and talking about $g(n)$, not procisely about $h(n)$? This is relally big difference. This is like manipulation in the context of how these functions differ. Conway's results are brilliant, but combination of addition and multiplication is the source of the greatest difficulty in the Collatz problem and the dynamics of Collatz-type functions. Conway considered something significantly different in my understanding. We are not even close to build a FRACTRAN-like programs if we put there non-zero numbers $b_{i}$.

Or am I wrong and Conway proved something about functions $g(n)$ with $b_{i}$ not equal to zero?

Tom
  • 159
  • I never made a closer look to the proof, but usually the idea is to reduce the given problem to the halting problem , for this we can use any turing-complete language , and FRACTRAN is turing-complete. So , I do not understand where exactly the problem is. The famous special case (the "usual" Collatz conjecture) is claimed to be solvable in principle , but I keep sceptical. – Peter Nov 28 '22 at 08:18

0 Answers0