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. 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.
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 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
We can relatively simply simulate Collatz function iteration with a cyclic tag system, giving an alternative proof for the Turing-completeness of the latter.
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:
| 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≤m-2 | Pass 1 unary digit to be deleted. | |
| 5i, i=m-1 |
01000(00000)m-1 |
Pass 1 unary digit terminating group of m. |
| 5i+1 |
(10000)ai |
Pass 2 unary digit when remainder is i. |
| 5i+2 |
00010(00000)m-1-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. |
| 5i+3 |
(10000)bi00100(00000)m-1 |
Pass 2 control bit when remainder is i. The 00100(00000)m-1 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*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 "" _ = ""
See also
External resources
- Paper on the undecidability of the generalized Collatz conjecture for Collatz functions (Google books, some pages may not show properly).