this question is apparently closely related to Wolframs research program of determining whether "small" Cellular Automata [CAs][1] are Turing Complete. if the CA is proved Turing Complete then by mapping with Turings halting problem, there exists an input for which termination of the CA cannot be proven. but also determining whether the CA is Turing complete can be very difficult and there are several so-far-indeterminate cases. a case where it succeeded but with a very complex proof is [2], some further details of the dynamics in [4]. see also [5] for a writeup of an ambitious somewhat recent "major attack" on the busy beaver problem that superseded many prior results. and there is also a related long tradition of research for finding small state universal TMs[3,6] probably dating to the ~1960s including results by Marvin Minsky. re Collatz conjecture candidate & a boundary with "nearby" problems similar to Conway-type, see also [7]
[1] Elementary cellular automata, wikipedia
[3] tcs.se, whats the simplest noncontroversial 2 state universal TM
[4] tcs.se initial conditions for rule 110
[5] New-Millenium Attack on the Busy Beaver Problem by Ross et al
[6] The complexity of small universal Turing machines: a survey Woods & Neary
[7] tcs.se, whats the nearest problem to the Collatz conjecture thats been successfully resolved?
