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. Wikipedia has a simple definition of them.
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.
The below Haskell program and function convert from a Fractran program represented as a list of
Rationals to an iterated Collatz function represented
as a 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 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..m-1] ] where m = foldl' lcm 1 $ map denominator fractions main=interact $ show . fractranToCollatz . read
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.
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
Each iteration of the function is done in two complete passes over the binary data-string.
The data bits form consecutive groups of 5, with set bits classified according to their position within their group:
|Bit class||pass 1 digit||pass 2 digit||pass 1 control bit||pass 2 control bit||halting digit|
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
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.
We summarize the program offsets with their corresponding data bits and productions in the following table.
|5i, 0≤i≤m-2||Pass 1 unary digit to be deleted.|
|Pass 1 unary digit terminating group of m.|
|Pass 2 unary digit when remainder is i.|
|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.|
|Pass 2 control bit when remainder is i. The |
|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.
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*m-n-1) "0" digit1 = '1' : rep (smallPeriod-1) "0" [digit2, check1] = map bitAt [1,2] initData = rep initValue digit1 ++ check1 initProgram = do ((a,b,cont),i) <- zip rules [0..] [if i == m-1 then digit2 else "", rep a digit1, "0001" ++ rep (smallPeriod*(m-1-i)) "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 (n-1) (d',p) step (d:ds) prod = ds ++ if d == '0' then "" else prod step "" _ = ""
- Paper on the undecidability of the generalized Collatz conjecture for Collatz functions (Google books, some pages may not show properly).