4 ms·
My favorite Turing tarpit is FRACTRAN, devised by John Conway. It's flabbergasting that it is actually Turing complete, but it is. A FRACTRAN program is a list
by bqe 11y ago
My favorite Turing tarpit is FRACTRAN, devised by John Conway. It's flabbergasting that it is actually Turing complete, but it is.
A FRACTRAN program is a list of fractions, rational numbers. You input an integer and then you find the first fraction that gives you an integer when multiplied by your input. That process is repeated with the new, multiplied number until there is no fraction that produces an integer when multiplied.
Conway wrote a program that generates primes, there's others that mathematical sequences, but my favorite is just the addition program:
3/2
Given an input 2^x * 3^y, it will stop at 3^(x+y), which adds x and y together.
- stingraycharles 11y agoFor the lazy: https://en.m.wikipedia.org/wiki/FRACTRAN https://en.m.wikipedia.org/wiki/FRACTRAN
- pavlov 11y agoFor some reason this makes me imagine an alternate history sci-fi universe where Pythagoras (famous for his love of fractions) invents FRACTRAN. Then Archimedes builds a mechanical computer to execute those programs, and one of the successors of Alexander The Great puts the computer to use in warfare and conquers the world. Science is accelerated so that nuclear physics are invented by the time Jesus is born... Surely there's some kind of plot waiting there :)
- saulrh 11y ago"My words are backed with NUCLEAR WEAPONS!"