Fractran.

EvolveList, the basic instruction  :

Clear[EvolveList];EvolveList[fracs_,init_]:=NestWhileList[First[Select[fracs #,IntegerQ,1]]&,init,Select[fracs #,IntegerQ,1]=!={}&]

parity={65/42,7/13,1/21,17/7,57/85,17/19,7/17,1/3};

The example of a parity checker : EvolveList applied to 63 (2^n) generates a list ending with 5 if n is odd and with 1 otherwise :

EvolveList[parity,63 (2^5)]

EvolveList[parity,63 (2^6)]

6 simple algorithms :

1) Addition in Fractran : (2^a)(3^b)⟶(3^(a+b)).

sum={3/2};

add[u_]:=((HoldForm[3])^(FactorInteger[Last[EvolveList[sum,u]]][[1,2]]))

add[(2^3)(3^4)]

2) Multiplication in Fractran : (2^a)(3^b)⟶(5^(a×b)).

product={455/33,11/13,1/11,3/7,11/2,1/3};

mult[u_]:=((HoldForm[5])^(FactorInteger[Last[EvolveList[product,u]]][[1,2]]))

mult[(2^3)(3^4)]

3) Integer division in Fractran : (2^a)(3^b)11⟶(5^(quotient(a/b)))(7^(remainder(a/b))).

quotient={91/66,11/13,1/33,85/11,57/119,17/19,11/17,1/3};

intdiv[u_]:=((HoldForm[5])^(FactorInteger[Last[EvolveList[quotient,u]]][[1,2]]))((HoldForm[7])^(FactorInteger[Last[EvolveList[quotient,u]]][[2,2]]))

intdiv[(2^13)(3^5)11]

4) Greatest common divisor : (2^a)(3^b)⟶(5^(GCD(a,b))).

gcd={22/19,21/23,51/55,11/17,26/35,7/13,1/11,1/7,5/6,23/3,19/2};

gcdiv[u_]:=((HoldForm[5])^(FactorInteger[Last[EvolveList[gcd,u]]][[1,2]]))

gcdiv[(2^24)(3^18)]

5) Least of two integers : (2^a)(3^b)⟶(5^(Min(a,b))).

least={5/6,1/2,1/3}

min[u_]:=((HoldForm[5])^(FactorInteger[Last[EvolveList[least,u]]][[1,2]]))

min[(2^2)(3^3)]

6) Swapping two registers :

swapping={55/14,7/11,13/7,34/39,13/17,1/13,3/5};

swap[u_]:=((HoldForm[2])^(FactorInteger[Last[EvolveList[swapping,u]]][[1,2]]))((HoldForm[3])^(FactorInteger[Last[EvolveList[swapping,u]]][[2,2]]))

swap[(2^5)(3^4)7]

Programming a function.

Fibonacci[n] : (2^n)⟶(3^(fib(n)))

fibo={13/11,133/85,17/19,23/17,1015/69,23/29,31/23,111/217,31/37,13/31,17/26,33/2,1/13,1/5};

fib[u_]:=((HoldForm[3])^(Log[3,Cases[EvolveList[fibo,u],x_/;IntegerQ[Log[3,x]]==True]][[1]]))

fib[(2^9)]

Factorial[n] : (2^n)⟶(3^(n!))

factorial={115/38,19/23,17/19,4147/51,17/29,31/17,259/155,41/31,129/481,37/43,17/37,47/533,41/47,53/41,177/583,53/59,61/53,67/427,1/61,355/469,67/71,17/67,57/2}

fact[u_]:=((HoldForm[3])^(Log[3,Cases[EvolveList[factorial,u],x_/;IntegerQ[Log[3,x]]==True]][[1]]))

fact[(2^5)]

Universal arithmetical program. (Subscript[f, k])[n]=m : k (2^(2^n))⟶(2^(2^m)) (if defined).

polygame={583/559,629/551,437/527,82/517,615/329,371/129,1/115,53/86,43/53,23/47,341/46,41/43,47/41,29/37,37/31,37/31,299/29,47/23,161/15,527/19,159/7,1/17,1/13,1/3};

Universality implies the undecidability of the halting problem. An arbitrary limit (say 10000 steps) prevents eventual looping :

Clear[EvolveList];EvolveList[fracs_,init_]:=NestWhileList[First[Select[fracs #,IntegerQ,1]]&,init,Select[fracs #,IntegerQ,1]=!={}&,1,100000]

Computable functions are indexed by the positive integer, k. Most low k-values correspond to uninteresting functions : (Subscript[f, 2268945])[n]=n+1 or (Subscript[f, 256])[3]=4 (undefined if n≠3).

compute[k_,u_]:=HoldForm[2]^HoldForm[2]^Log[2,Log[2,Cases[EvolveList[polygame,k u],x_/;IntegerQ[Log[2,Log[2,x]]]==True]]][[1]]

compute[2268945,(2^(2^6))]

compute[256,(2^(2^3))]

compute[256,(2^(2^4))]

Dropper algorithms.

Here Fractran enumerates the asked integers, n, one by one (Only powers of 2 are significant in the output).

Collatz sequence of an integer (Halting conjectured) :

collatz={1/11,136/15,5/17,4/5,26/21,7/13,1/7,33/4,5/2,7/1};

Clear[EvolveList];EvolveList[fracs_,init_]:=NestWhileList[First[Select[fracs #,IntegerQ,1]]&,init,Select[fracs #,IntegerQ,1]=!={}∧First[Select[fracs #,IntegerQ,1]]>2&,1,10000,1]

Log[2,Cases[EvolveList[collatz,(2^79)],x_/;IntegerQ[Log[2,x]]==True]]

Clear[EvolveList];EvolveList[fracs_,init_]:=NestWhileList[First[Select[fracs #,IntegerQ,1]]&,init,Select[fracs #,IntegerQ,1]=!={}&,1,10000]

Primes generator (No halting of course) :

primes={17/91,78/85,19/51,23/38,29/33,77/29,95/23,77/19,1/17,11/13,13/11,15/2,1/7,55/1};

((HoldForm[2])^(Log[2,Cases[EvolveList[primes,2],x_/;IntegerQ[Log[2,x]]==True]]))

A bug.

Decimals of π : This program does not work because of a well-known but never corrected bug (probably in the coding of the inputs and/or of the outputs)

pigame={365/46,29/161,79/575,679/451,3159/413,83/407,473/371,638/355,434/335,89/235,17/209,79/122,31/183,41/115,517/189,111/83,305/79,23/73,73/71,61/67,37/61,19/59,89/57,41/53,833/47,53/43,86/41,13/38,23/37,67/31,71/29,83/19,475/17,59/13,41/291,1/7,1/11,1/1024,1/97,89/1};

Clear[EvolveList];EvolveList[fracs_,init_]:=NestWhileList[First[Select[fracs #,IntegerQ,1]]&,init,Select[fracs #,IntegerQ,1]=!={}&,1,10000]

Log[2,Cases[EvolveList[pigame,89],x_/;IntegerQ[Log[2,x]]==True]]