Remembering John Conway's FRACTRAN, a ridiculous, yet surprisingly deep language

Fractran, invented by John Conway, is an esoteric programming language that showcases Conway's unique approach to mathematics and computer science. Despite its simplicity and unconventional syntax, Fractran is a Turing-complete language, capable of computing any computable function. 1. **Understanding Fractran Programs**: - Fractran programs consist of a list of positive fractions and an initial positive integer. The program updates the integer by multiplying it with the first fraction in the list that results in an integer product. This process repeats until no fraction in the list produces an integer product, at which point the program halts. - For instance, the PRIMEGAME program, which finds successive prime numbers, starts with the fraction 17/91 and the initial integer 2. The sequence generated includes prime powers, demonstrating the language's ability to handle complex computations. 2. **Computational Power and Encoding**: - Fractran programs can be seen as a type of register machine where the registers are stored in prime exponents within the argument \(n\). Using Gödel numbering, a positive integer \(n\) can encode an arbitrary number of arbitrarily large positive integer variables. - The value of each variable is encoded as the exponent of a prime number in the prime factorization of the integer. This encoding method allows for an efficient and compact representation of complex data structures. 3. **Conway's Contributions and Legacy**: - John Conway's work on Fractran reflects his innovative approach to making complex mathematical concepts accessible and engaging. Despite his passing in 2020, Conway's contributions to mathematics and computer science continue to inspire and influence researchers and enthusiasts alike. - Fractran serves as a testament to Conway's ability to simplify and elucidate intricate ideas, making them appealing to a broad audience. The language's unique properties and the problems that can be solved with it have captivated the computational community. 4. **Practical Applications and Inspiration**: - While Fractran is primarily an academic curiosity, its principles and the problems it can solve might inspire new approaches to algorithm design and computational problem-solving techniques. - The language's simplicity and elegance in solving complex problems can serve as a model for future programming language design, emphasizing the importance of clear and concise syntax alongside computational power. In conclusion, Fractran is not just a ridiculous language for solving prime games; it is a profound demonstration of Conway's genius, showcasing the power of simplicity, creativity, and the beauty of mathematical encoding in computer science.