A Universal FRACTRAN Interpreter in FRACTRAN

A Universal FRACTRAN Interpreter in FRACTRAN

Chris Lomont, May 1, 2017

Introduction

FRACTRAN is a Turing-complete esoteric programming language invented by the prolific mathematician John Conway in 1972 [Con72, Con87].

From Wikipedia (with slight edits):

A FRACTRAN program is an ordered list of positive (reduced) fractions together with an initial positive integer input s. The program is run by updating the integer s (which I call the state of the program) as follows:

  1. for the first fraction f in the list for which sf is an integer, replace s by sf.