FRACTRAN is an esoteric, Turing-complete programming language invented by the mathematician John Horton Conway, in which a program is simply an ordered list of fractions, and execution consists of repeatedly multiplying a single starting integer by the first fraction in the list that yields another integer, halting when no fraction in the list can be applied. Despite this extremely minimal mechanism, FRACTRAN programs can compute any computable function, including a seventeen-fraction FRACTRAN program written by Conway that generates successive prime numbers.
Facts
SignificanceFRACTRAN's significance is that it shows a Turing complete model of computation can be built from nothing more than an ordered list of fractions applied to a single integer, a mechanism its inventor famously used to generate prime numbers. 1 Sources
1. FRACTRAN, Wikipedia
Lead sectionQuote, Lead section
FRACTRAN is a Turing-complete esoteric programming language invented by the mathematician John Conway.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.