A Collatz function f is a function from integers to integers such that there is a modulus m and sequences of rational numbers ri and si, i=0..m-1, such that
f(x) = rix + si when x=i (mod m).
Equivalently we may use sequences of integers ai and bi, i=0..m-1 and require
f(mx+i) = aix + bi, i=0..m-1.
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 ai > 0, bi ≥ 0. This will always be satisfied by a Collatz function corresponding to a Fractran program with positive fractions.
The converter takes as input a Haskell list of 3-tuples, where the tuple elements are (ai, bi, ci) for i=0..m-1. The
ai and bi are as above, while ci 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
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 "
- Paper on the undecidability of the generalized Collatz conjecture for Collatz functions (Google books, some pages may not show properly).