We are currently working on new rules for what content should and shouldn't be allowed on this website, and are looking for feedback! See Esolang:2026 topicality proposal to view and give feedback on the current draft.
Talk:REFRACTRAN
Jump to navigation
Jump to search
Reversibility
I'm not sure this language is actually reversible. For example, what happens if the state integer is 8 and program execution encounters the fraction 2/3? 8 isn't divisible by 3, so this command should do nothing; but that isn't reversible, because executing in reverse, the 8 can be multiplied by 3/2 to produce 12 (which isn't where the program initially came from). --ais523 00:30, 12 September 2026 (UTC)
- This is addressed in the "Lack of Symmetry" section. Running a reverse search is not actually equivalent to "rewinding" the code. However, every program state does have a single unique predecessor state. There is no way for a reverse search to have matched 2/3 and produced an 8 as the resulting program state integer, since it would need to have a 3 in its factorization. So, if you are forward searching on the fraction after 2/3 with a program state integer of 8, you know that you just forward searched the 2/3 and it did nothing, rather than reverse-searching the 2/3 and getting turned around. If you want to simulate rewinding the program, you have to reciprocate every fraction in addition to reversing the search direction. ImOnlyHereForReversibleComputing (talk) 00:44, 12 September 2026 (UTC)
- I guess just to tackle the other side: if you are on the fraction after a 2/3 and the program state integer IS divisible by 3, then that definitively means that you just matched the 2/3 during a reverse search and got turned around. It's not possible that you arrived at the current fraction via a forward search, because if you had, you would have matched the 2/3 and turned around before reaching the current fraction. You can always look at the preceding fraction according to the current search direction, and check if you have all of the factors from its relative "denominator" in the program state integer to determine if you matched it or not on your way to arriving at your current fraction. If you have all the factors from its relative denominator, you must have matched it and turned around from an opposite direction search to get to where you are. And you can follow this repeatedly to step backwards through the entire execution history of the program. I can probably update the Lack of Symmetry section to be a little bit more clear about this, because this isn't spelled out super clearly in the article currently; it's more just something to infer from a number of different pieces of information. ImOnlyHereForReversibleComputing (talk) 00:58, 12 September 2026 (UTC)
- OK, I think I understand: when, e.g., going past 2/3, if you end up on the right hand side you must have come from the left hand side if the resulting number is not divisible by 3, but from the right hand side if the resulting number is divisible by 3 (likewise, if you end up on the left hand side, you must have come from the left hand side if the resulting number is divisible by 2, but from the right hand side if the resulting number is not divisible by 2). I'd missed that one direction multiplies by the fraction and the other direction divides. --ais523 01:25, 12 September 2026 (UTC)
- Yeah. I actually find it kind of helpful to almost think of this as a "2-dimensional" programming language with 2 columns: a numerator column and a denominator column, with the rule that the instruction pointer always moves downwards in the denominator column and always moves upward in the numerator column. This makes the execution rule uniform: at each cell, you check if its value divides your program state integer; if it does, divide the current cell's value out, swap columns, then multiply the current cell's value in. A lot of the "semantic operations on fraction lists" stuff that seems really abstract becomes a lot more obvious if you look at it this way, because both reciprocating and reversing a fraction list are just reflections in this 2D space. And it also becomes more obvious why you need to reciprocate the fraction list in addition to reversing the search direction to "rewind" the program: "reversing the search direction" actually just moves the instruction pointer to the other column, so you also have to swap the columns so that your "rewound" searches are traversing the correct columns. This is actually the reason why all of the code examples are written with one fraction per line, because it makes it easier to scan down the denominators and up the numerators. ImOnlyHereForReversibleComputing (talk) 02:36, 12 September 2026 (UTC)
- OK, I think I understand: when, e.g., going past 2/3, if you end up on the right hand side you must have come from the left hand side if the resulting number is not divisible by 3, but from the right hand side if the resulting number is divisible by 3 (likewise, if you end up on the left hand side, you must have come from the left hand side if the resulting number is divisible by 2, but from the right hand side if the resulting number is not divisible by 2). I'd missed that one direction multiplies by the fraction and the other direction divides. --ais523 01:25, 12 September 2026 (UTC)
- I guess just to tackle the other side: if you are on the fraction after a 2/3 and the program state integer IS divisible by 3, then that definitively means that you just matched the 2/3 during a reverse search and got turned around. It's not possible that you arrived at the current fraction via a forward search, because if you had, you would have matched the 2/3 and turned around before reaching the current fraction. You can always look at the preceding fraction according to the current search direction, and check if you have all of the factors from its relative "denominator" in the program state integer to determine if you matched it or not on your way to arriving at your current fraction. If you have all the factors from its relative denominator, you must have matched it and turned around from an opposite direction search to get to where you are. And you can follow this repeatedly to step backwards through the entire execution history of the program. I can probably update the Lack of Symmetry section to be a little bit more clear about this, because this isn't spelled out super clearly in the article currently; it's more just something to infer from a number of different pieces of information. ImOnlyHereForReversibleComputing (talk) 00:58, 12 September 2026 (UTC)