Collatz function

From Esolang
Jump to: navigation, search

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 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.

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 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).