This forum is closed to new posts due to low activity and a deluge of spam. It is kept online as a static historical record. If you want to read about or discuss esoteric programming languages, the Esolang wiki is the place to go. An archive of the forum is available.
For any fractran program, let p be any prime not used in the program. If your starting value is divisible by p,
then the program has no way of removing it. So it cannot be done, alas.
Well, there still is no such program, because of the faulty i/o convention that I was imposing ...
There is no FRACTRAN program that halts with a value other than 2^0 when started with the value 2^0.
(Only an integral fraction can alter the value 1, and any program containing such a fraction will never halt.)
So, the i/o convention of starting with 2^x and stopping with 2^f(x) (or p^f(x) for a given prime p)
is not generally adequate to compute functions f: N -> N.
The simplest remedy may be to start with 2^(x+1) and stop with 3^(f(x)+1). Using this i/o encoding,
here are programs for all the constant functions:
ZERO = [7/10, 11/5, 5/14, 11/7, 5/2, 3/11]
ONE = [7/10, 11/5, 5/14, 11/7, 39/11, 5/2, 3/13]
TWO = [7/10, 11/5, 5/14, 11/7, 39/11, 51/13, 5/2, 3/17]
THREE = [7/10, 11/5, 5/14, 11/7, 39/11, 51/13, 57/17, 5/2, 3/19]etc. Each successive program is obtained from its predecessor by increasing the denominator prime p
in the final fraction to the next larger prime, say q, and inserting 3q/p before the 5/2.
Are there "smaller" versions of these programs? (I'm supposing that whatever i/o encoding scheme
is used, the same one is used for all the functions.)
Absolutely. For a start, remember you can have exponents larger than 1 in the program itself. So, if I've thought correctly:
CONST N = [2/25, 5/2, 3^(N+1)/5]
For large enough N, I suspect you could compress that further textually (since 3^(N+1) is pretty big, plus there is that whole Kolmogorov complexity thing that should apply.) For example powers of 2:
CONST 2^N = [2/25, 5/2, 49/5, 121/7, ..., 9/last prime]
Those are nice little programs. (BTW, I didn't actually write mine in FRACTRAN, but wrote them first as counter machine
programs, then translated them instruction-by-instruction into FRACTRAN -- clearly not a way to get "optimized" code!)
Borrowing your basic idea, here's a version, I hope, of the successor function (x -> x+1):
SUCC = [55/2, 3/5, 11/49, 7/11, 3/7].In an obvious symbolic notation, with i, o, a, b, c denoting any five distinct prime numbers, this is
SUCC = [ab/i, o/b, a/cc, c/a, o/c],which should halt with final value o^(x+2) if started with initial value i^(x+1) (x >= 0).
That can be shortened too:
SUCC = [6/5 , 5/4, 9/2]
I notice that in a variant of FRACTRAN that tests whether state/denom is integral, instead of whether state*numer/denom
is integral, your program can be shortened even further to SUCC = [6/4, 9/2] (symbolically, [io/ii, oo/i]). Your Bag language
(http://home.nvg.org/~oerjan/esoteric/bag/) appears to be equivalent to a variant of this kind.