Talk:Collatz sequence

From Esolang
Jump to navigation Jump to search


Does a Collatz sequence program prove Turing-completeness? --User:Hanzlu 18:04, 3 August 2019 (UTC)

Only if your construction handles generalizations of the Collatz sequence in addition to the sequence itself, i.e. looking at the number modulo n (not just 2) and then deciding what to multiply it by and add to it as a result. (In fact, you don't actually need the additions to prove Turing-completeness; "look at the number modulo n and multiply by one of n different numbers accordingly" is sufficient to implement Tip, which is Turing-complete.) --ais523 17:14, 3 August 2019 (UTC)