FRACTRAN
Welcome to FRACTRAN! FRACTRAN is an esoteric programming language developed by John Conway. This interactive will walk you through some programming exercises in FRACTRAN until you are an EXPERT FRACTRAN PROGRAMMER!
Submission for the 3Blue1Brown Summer of Math Exposition 3 #some3
Why FRACTRAN?
FRACRAN is a specific case of a natural generalization of the Collatz conjecture. Since FRACTRAN is Turing complete, this brings up the possibility that the Collatz conjecture might be undecidable as a halting problem. What's more, any solution to the Collatz conjecture must not fully generalize to all of FRACTRAN, since that would solve the halting problem.
The Collatz conjecture asks questions about the behavior of repeatedly applying a function that applies different linear/affine functions depending on the remainder of the input when divided by 2. Applying a FRACTRAN program for one step is also applying a linear function depending on the remainder of the input when divided by the LCM of the denominators, and so applying a FRACTRAN program for many steps is asking about the behavior of repeatedly applying a Collatz-like function.
Your Free Sample of FRACTRAN (Conway, 1987):
- Primegame: 17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/2, 1/7, 55/1 (input 2 and it will run forever. The powers of 2 that appear will be 2 to the power of the primes in order)
Shameless Plug:
Lately, I've been making Youtube videos. Some highlights:
- FRACTRAN playlist (walkthrough and discussion of the consequences of FRACTRAN being Turing complete coming soon)
- Last year's #SoME2 entry on model theory using my EF-Game interactive
- A lecture series on the intersection of Model Theory and Automata Theory
References (contains spoilers):
- http://www.cs.cmu.edu/~15455/resources/Conway87.pdf Conway, J.H. (1987). FRACTRAN: A Simple Universal Programming Language for Arithmetic. In: Cover, T.M., Gopinath, B. (eds) Open Problems in Communication and Computation. Springer, New York, NY. https://doi.org/10.1007/978-1-4612-4808-8_2
- See Conway give a talk on FRACTRAN here: https://www.uctv.tv/shows/Fractran-A-Ridiculous-Logical-Language-with-John-Conwa...
- Need inspiration for the last level? Computerphile has a video on Counter Machines that might be helpful: https://www.youtube.com/watch?v=PXN7jTNGQIw
Uses:
- jquery (for Mathquill) MIT License (https://jquery.org/license/)
-
Mathquill (modified) (http://mozilla.org/MPL/2.0/)
Latin Modern Mono Font (https://tug.org/fonts/licenses/GUST-FONT-LICENSE.txt)
Questrial Font (https://github.com/googlefonts/questrial/blob/main/OFL.txt)
Comments
Log in with itch.io to leave a comment.
Don't do 2*3/2
Nice game, two bug reports however:
(1) In level 17, it should be stated that you can suppose that prime 13 doesn't appear on the input (it is not apparent from the problem statement, and it is necessary to have a guaranteed prime which will not occur).
(2) (parsing bug?, I don't understand the details) When I enable nocancel, and input "5*7*3*11/2*3*11", it gets interpreted as:
A = as entered: [Empty], raw numbers: 1155/13
B = as entered: 5⋅7⋅3⋅11/2⋅3⋅11, raw numbers: 13/66
Factored Form: 3*5*7*11/13, 13/2*3*11
This is quite constraining me with proceeding in the game... I tried to reload the page, or try another level, and still shows the same weird bug.
(1) is a very good point that I completely overlooked! When programming in FRACTRAN, it's usually the case that you know in advance the small list of primes that will be relevant to the problem, so you can always find a "13" for any given program.
(2) One might imagine an extension of FRACTRAN allowing fractions with the following behavior: If the number is divisible by 66, then multiply by 1155/66 = 35/2, and if it's not, move on to the next fraction. Normally if you entered 1155/66 it would cancel down to 35/2 and so the fraction would activate on any number divisible by 2, not just those divisible by 66.
This extended version of FRACTRAN is expressively equivalent to ordinary FRACTRAN, where fractions always get canceled. What's happening is that nocancel mode is translating your code into an equivalent valid program, using the same technique as in my solution to level 17.
(2) I see, thanks for the explanation. I didn't expect nocancel to modify my input, I thought it was merely a running flag.
Really cool! (See my comments on YouTube)
A bug I noticed:
Having the page automatically factor any number in real-time as it's typed is cool in theory, but it makes it a little too easy to crash the page. All you have to do is mash the number keys until you've created an enormous prime number, or at least a number with at least one prime factor greater than what the page can check. (I used 1389537541)
One solution would be to calculate the prime factorization asynchronously, and maybe display the raw number in a different color to indicate that the computer is still working on factoring it in the background. (Actually implementing this in JavaScript may prove tricky.)
Great stuff! Would be nice if the “Next Level” button consistently scrolled to the “Level Goal” paragraph. Currently it sometimes scrolls all the way up and sometimes doesn’t at all, and I couldn’t find any regularity.
Edit: I’m almost done, and on the final two levels limit on the test simulation is not enough. I had to add redundant fractions for moving hundreds of exponents because moving 765 of them one by one (for the 2^567 reversal) exceeded step limit.
Edit2: It can’t be just the limit, as the 2^1234 case terminates within 1000 steps but the test case reports a loop:
My current reversing program (first rule to make 2^567 terminate in time):
A loop is also reported when I cheat and enter a rule
3^4321*13/2^1234*11, suggesting it may have something to do with number sizes. Is the source for this available?I second this, the 2^1234 test in the reversal level always reports loop, even when the only instruction is
3^4321*13/2^1234*11Thanks! Nearly everything is stored in terms of prime factorizations, except the loop detector uses their calculated values as javascript numbers. All of these large numbers 2^1234*11, 3^4321*13, 2^1134*31 evaluate to infinity, which we've seen before, so the loop detector thinks we're in a loop. And, yes, the maximum step limit is also too small. This should be an easy fix. The interactive is just an html file in an iframe, so you can just view its source directly. I didn't apply any compilation or obfuscation to the code.
I believe I have fixed the loop detector to correctly handle terms that evaluate to infinity. I've also added a "Max Iterations" input box so you can increase the number of iterations before the simulation gives up.