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