# Collatz function

A **Collatz function** is a generalization of Collatz sequences invented by John Horton Conway, who proved iteration of them Turing-complete 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..

*m*-1, such that

f(x) =r+_{i}xswhen_{i}x=i(modm).

Equivalently we may use sequences of integers *a _{i}* and

*b*,

_{i}*i*=0..

*m*-1 and require

f(mx+i) =a+_{i}xb,_{i}i=0..m-1.

## Computational class

Iterated Collatz functions are Turing complete as a single iteration of Fractran is a Collatz function.

## Reduction to 3-cell brainfuck

The following Haskell program converts an iterated Collatz function to a brainfuck subprogram using a tape of just 3 unbounded non-negative cells, proving brainfuck Turing complete even with this restriction.

It is a requirement that *a _{i}* > 0,

*b*≥ 0. This will always be satisfied by a Collatz function corresponding to a Fractran program with positive fractions.

_{i}The converter takes as input a Haskell list of 3-tuples, where the tuple elements are (*a _{i}*,

*b*,

_{i}*c*) for

_{i}*i*=0..

*m*-1. The

*a*and

_{i}*b*are as above, while

_{i}*c*is 0 if we wish the brainfuck program to halt and 1 if we want it to continue with another iteration. This allows us to select the usual Fractran halting condition, as implemented in the

_{i}`fractranToCollatz`

function.
import Data.List (find, foldl', genericReplicate) import Data.Ratio (denominator) rep n l = genericReplicate 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 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..m-1] ] where m = foldl' lcm 1 $ map denominator fractions

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 "`[->+<`

".

## External resources

- Paper on the undecidability of the generalized Collatz conjecture for Collatz functions (Google books, some pages may not show properly).