Collatz function
A Collatz function is a generalization of Collatz sequences invented by John Horton Conway, who proved iteration of them Turingcomplete by reduction from Fractran.
A Collatz function f is a function from integers to integers such that there is a modulus m and sequences of rational numbers r_{i} and s_{i}, i=0..m1, such that
f(x) = r_{i}x + s_{i} when x=i (mod m).
Equivalently we may use sequences of integers a_{i} and b_{i}, i=0..m1 and require
f(mx+i) = a_{i}x + b_{i}, i=0..m1.
Contents
Computational class
Iterated Collatz functions are Turing complete as a single iteration of Fractran is a Collatz function.
The below Haskell program and function convert from a Fractran program represented as a list of Rational
s to an iterated Collatz function represented
as a list of 3tuples, where the tuple elements are (a_{i}, b_{i}, c_{i}) for i=0..m1. The
a_{i} and b_{i} are as above, while c_{i} is 0 if we wish to halt and 1 if we wish to continue with another iteration. This allows us to use Fractran's normal halting condition.
The resulting format is used in the converters in the following sections.
import Data.List (find, foldl') import Data.Ratio (denominator) fractranToCollatz :: [Rational] > [(Integer,Integer,Integer)] fractranToCollatz fractions = [ case find (\f > i `mod` denominator f == 0) fractions of Nothing > (m, i, 0) Just f > (floor (f*fromIntegral m), floor (f*fromIntegral i), 1)  i < [0..m1] ] where m = foldl' lcm 1 $ map denominator fractions main=interact $ show . fractranToCollatz . read
Reduction to 3cell brainfuck
The following Haskell program converts an iterated Collatz function to a brainfuck subprogram using a tape of just 3 unbounded nonnegative cells, proving brainfuck Turing complete even with this restriction.
It is a requirement that a_{i} > 0, b_{i} ≥ 0. This will always be satisfied by a Collatz function corresponding to a Fractran program with positive fractions.
rep n l = [1..n] >> l collatzToBF :: [(Integer,Integer,Integer)] > String collatzToBF l = ">>+[" ++ foldr branch "++<<[>+<]" l ++ ">[<+>]>]" branch (a,b,c) s = concat [ "[<", rep a "+", ">]", rep c "+", '<' : rep b "+", "<[>", rep b "", '[' : rep a "", ">+<]>", rep c "", s, "]" ] main = interact $ collatzToBF . read
Here is a reformatted example generated from the Fractran program 5/4:
>>+[[<+++++>]+<< [>[>+<]>[<++++>]<+< [>[>+<]>[<++++>]<++< [>[>+<]>[<++++>]<+++< [>[>+<]>++<< [>+<]]]]] >[<+>]>]
The automatic conversion is not optimal, e.g. line 3 and 4 could both simply be "[>+<
".
Reduction to cyclic tag systems
We can relatively simply simulate Collatz function iteration with a cyclic tag system, giving an alternative proof for the Turingcompleteness of the latter.
Each iteration of the function is done in two complete passes over the binary datastring.
The data bits form consecutive groups of 5, with set bits classified according to their position within their group:
Offset  0  1  2  3  4 

Bit class  pass 1 digit  pass 2 digit  pass 1 control bit  pass 2 control bit  halting digit 
Example walkthrough
We'll show the simulation of the Fractran program 5/4 starting with the number 4. For this we have m=4, and the CTS program has 4*5 = 20 productions.
1000010000100001000000100000000000000000 . . . * @
At the beginning of the first pass, the number 4 is encoded in unary as 4 copies of the string 10000
. Then follows a control section 00100000000000000000
.
During this pass, the program deletes most of the unary digits (.
), but every fourth (*
, at program offset 15) gets to produce the string 01000000000000000000
for the next pass, essentially dividing the number by 4. If the division has a remainder, this will not produce anything, but will change the program offset for everything coming later.
The set bit (@
) in the control section also produces a string 000100000000000000000
. The amount of 0 padding in the latter can vary dependent on the program offset (representing the remainder), and has the purpose of resynchronizing the string at the beginning of the next iteration.
0100000000000000000000010000000000000000 * @
At the beginning of the second pass, the quotient from the division is encoded in unary as copies of the string 01000000000000000000
, again followed by a control section and padding. The remainder is encoded in the program offset, ensuring that the set bits can branch depending on it.
In this case the remainder was 0, and the sole unary digit (*
) produces 5 copies of the phase 1 digit for the next iteration. The control bit (@
) could also produce some phase 1 digits, but doesn't in this case, generating only a new control section.
100001000010000100001000000100000000000000000 . . . * . @
In the second iteration, representing the number 5, we get a nonzero remainder 1. This means the Fractran program should halt. This is achieved by leaving off a single bit in the final zero padding for the second pass.
000000100000000000000000000010000000000 * @
In the second pass of the second iteration, set bits are shifted 5 places compared to the first iteration, corresponding to the remainder now being 1. The unary digit (*
) multiplies itself by 4 again, and the control bit (@
) adds the remainder back, ensuring that the represented number has not changed in this iteration. Since the program should halt, no new control section is generated.
(1)000010000100001000010000 x x x x x
Finally, we have again a unary representation of the number 5 – but this time the program offset has been shifted by one bit. Instead of division the bits just get deleted, and the cyclic tag system halts.
Production table
We summarize the program offsets with their corresponding data bits and productions in the following table.
Offset  Production  Explanation 

5i, 0≤i≤m2  Pass 1 unary digit to be deleted.  
5i, i=m1 
01000(00000)^{m1} 
Pass 1 unary digit terminating group of m. 
5i+1 
(10000)^{ai} 
Pass 2 unary digit when remainder is i. 
5i+2 
00010(00000)^{m1i} 
Pass 1 control bit when remainder is i. The last 0 of the production is dropped when halting – the only case where the offset (mod 5) is not preserved. 
5i+3 
(10000)^{bi}00100(00000)^{m1} 
Pass 2 control bit when remainder is i. The 00100(00000)^{m1} is dropped when halting.

5i+4  Halting phase unary digit to be deleted. 
If no halting remainders exist, then the last 0
in each group of 5 bits can be dropped, together with the final row in the table, and all 5s are reduced to 4s.
Conversion program
The following Haskell program calculates the initial state of the cyclic tag system corresponding to an iterated Collatz function.
The first input line should contain the starting number. Then follows the list representing the function. The output program is displayed in BCT syntax.
For REPL use, an interpreter function runCTS
is included; the result of the collatzToCTS
function can be fed directly into it.
import Data.List (foldl') rep n l = [1..n] >> l collatzToCTS :: Integer > [(Integer,Integer,Integer)] > (String,[String]) collatzToCTS initValue rules = (initData, initProgram) where m = length rules anyHalting = any (\(_,_,cont) > cont==0) rules smallPeriod = if anyHalting then 5 else 4 bitAt n = rep n "0" ++ '1' : rep (smallPeriod*mn1) "0" digit1 = '1' : rep (smallPeriod1) "0" [digit2, check1] = map bitAt [1,2] initData = rep initValue digit1 ++ check1 initProgram = do ((a,b,cont),i) < zip rules [0..] [if i == m1 then digit2 else "", rep a digit1, "0001" ++ rep (smallPeriod*(m1i)) "0" ++ rep cont ['0'  anyHalting], rep b digit1 ++ rep cont check1] ++ [""  anyHalting] ctsToBCT program = do prod < program concat [ ['1',bit]  bit < prod ] ++ "0" main = do initValue < readLn [(rules,_)] < reads <$> getContents let (initData, initProgram) = collatzToCTS initValue rules mapM_ putStrLn [ initData `seq` "Data: ", initData, "Program: ", ctsToBCT initProgram ]  First argument is number of program cycles before prompting.  A negative number will run indefinitely. runCTS _ ("",_) = return () runCTS 0 s = flip runCTS s =<< readLn runCTS n (d,p) = do print d let d' = foldl' step d p runCTS (n1) (d',p) step (d:ds) prod = ds ++ if d == '0' then "" else prod step "" _ = ""
See also
External resources
 Paper on the undecidability of the generalized Collatz conjecture for Collatz functions (Google books, some pages may not show properly).