For sure, here are the registers used for each fraction:
comp h^2 > comp H^2
comp h c > done H
comp > done c^2
done H^2 > done h^3
done H > comp
done > comp
Accumulator: comp h^8
The first two does the comparison for odd/even, the h register is moved to the H register during the comparison, then done does H += H>>2, and then keep trying.
Do you happen to know what the smallest/first (by some measure) Fractran program is of which it is unknown whether it halts or not? Or even undecidable?
I don't, sorry. I have played with rewriting systems a lot, but not within the lens of computability. One thing that I've noticed where that some rules can be inferred to be exhaustive(an exhaustive rule can be applied without searching for another rule for as long as the rule can be applied), and that a program where all the rules have less tokens on the right side than on the left side are not turing complete.
Conway's Fractran traditionally compares the accumulator against reduced fractions, but computationally-speaking, getting to the gcd of a fraction does little more than getting rid of otherwise valuable information used during comparison to match against a restricted set of fractions. The support for catalysts, symbols found on both sides of a rewrite rule, makes for a simpler and faster implementation.
15/6 red [green] > blue [green]
5/2 red > blue
red green
These two fractions are not equal and reducing the first into the second, eliminates the capability to match against it only when the catalyst green is present in the accumulator.
I see, so you are using a different model for computation that does not use rational numbers, but instead pairs of integers. From a computational point of view, that makes a lot of sense, disallowing catalysts is quite annoying, but I would not call this Fractran, instead I would call it something like a prioritized chemical reaction network or something like this. The wikipedia article explicitly states:
> The same variable cannot be both decremented and incremented in a single instruction (otherwise the fraction representing that instruction would not be in its lowest terms). Therefore each FRACTRAN instruction consumes variables as it tests them.
I've seen this variance used a lot in the code golfing challenges I participate in, I feel like if I called it something other than Fractran, it wouldn't be long before someone points out that this is quite like fractran and I ough to call that
This is cool, could you please explain your implementation?
For sure, here are the registers used for each fraction:
The first two does the comparison for odd/even, the h register is moved to the H register during the comparison, then done does H += H>>2, and then keep trying.https://wiki.xxiivv.com/site/fractran.html
Do you happen to know what the smallest/first (by some measure) Fractran program is of which it is unknown whether it halts or not? Or even undecidable?
I don't, sorry. I have played with rewriting systems a lot, but not within the lens of computability. One thing that I've noticed where that some rules can be inferred to be exhaustive(an exhaustive rule can be applied without searching for another rule for as long as the rule can be applied), and that a program where all the rules have less tokens on the right side than on the left side are not turing complete.
https://wiki.xxiivv.com/site/pocket_rewriting
Thank you very much - great link too!
50/18 reduces to 25/9 right?
Conway's Fractran traditionally compares the accumulator against reduced fractions, but computationally-speaking, getting to the gcd of a fraction does little more than getting rid of otherwise valuable information used during comparison to match against a restricted set of fractions. The support for catalysts, symbols found on both sides of a rewrite rule, makes for a simpler and faster implementation.
These two fractions are not equal and reducing the first into the second, eliminates the capability to match against it only when the catalyst green is present in the accumulator.I see, so you are using a different model for computation that does not use rational numbers, but instead pairs of integers. From a computational point of view, that makes a lot of sense, disallowing catalysts is quite annoying, but I would not call this Fractran, instead I would call it something like a prioritized chemical reaction network or something like this. The wikipedia article explicitly states:
> The same variable cannot be both decremented and incremented in a single instruction (otherwise the fraction representing that instruction would not be in its lowest terms). Therefore each FRACTRAN instruction consumes variables as it tests them.
I've seen this variance used a lot in the code golfing challenges I participate in, I feel like if I called it something other than Fractran, it wouldn't be long before someone points out that this is quite like fractran and I ough to call that
And 297/275 to 27/25?