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.

A simple FRACTRAN program? (8)

1 Name: r.e.s. : 2009-12-24 03:44 ID:2qQD1nmu

Does anyone know of a reasonably simple FRACTRAN program that,
for every positive integer starting value of n, always eventually halts with n = 2?

(Either I'm missing something obvious, or this is more complicated than it sounds.)

2 Name: Ørjan : 2009-12-24 07:18 ID:l+2d4UoE

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.

3 Name: r.e.s. : 2009-12-24 13:36 ID:2qQD1nmu

Oops ... I misstated the question.

For any starting value n = 2x, where x is a nonnegative integer, the program must eventually halt with n = 21.
(Alternatively, a different output convention could be used, such that, starting with any n = 2x, the program
eventually halts with n = p1 for some prime number p.)

I.e., the program is to compute the constant function C1 such that C1(x) = 1 for every nonnegative integer x.
A similar question applies to any positive constant function. (For the constant 0, the program (1/2) will do.)

4 Name: r.e.s. : 2009-12-26 06:17 ID:2qQD1nmu

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

5 Name: Ørjan : 2009-12-26 21:37 ID:l+2d4UoE

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]

6 Name: r.e.s. : 2009-12-28 03:13 ID:2qQD1nmu

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

7 Name: Ørjan : 2009-12-28 23:34 ID:l+2d4UoE

That can be shortened too:

SUCC = [6/5 , 5/4, 9/2]

8 Name: r.e.s. : 2009-12-29 06:10 ID:2qQD1nmu

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
( appears to be equivalent to a variant of this kind.

Name: Link:
Leave these fields empty (spam trap):
More options...