Why is FRACTRAN turing complete

turing-completeness

I've tried to google for explanation but most links only say things like "FRACTRAN is turing complete. As an example, let's look at multiplication."

I remember seeing an xkcd forum post say that FRACTRAN helped the poster understand Turing Completeness. I am looking for an intuitive explanation as to why this esolang is Turing complete, as it's not very obvious looking at the language mechanics.

Best Answer

For an imperative language to be Turing complete it must have:

  1. Conditional loop
  2. Arbitrary number of variables

FRACTRAN is a language that is made up of a series of fractions that stores its data in the exponents of primes.

Lets say you want to add two numbers: 2a3b becomes 5ab

455   11    1   3   11   1
--- , -- , -- , - , -- , -
 33   13   11   7    2   3

That's a FRACTRAN program for doing that above change.

You start off with a number like 72 (2332). The program goes 'forward' until it finds a number that when multiplied by the instruction is another integer (no remainders allowed).

72 will run forward until it gets to 11/2. It then will divide the number by 2 and multiply it by 11 (the power in 11 is a variable). This gives 396. 396 is divisible by 33 (reducing the 3 power and the 11) and multiply by 455 (incrementing 5, 7 and 13 variables). And so on. The full description of this program and its state table can be read at FRACTRAN wikipedia page, including a really nice animated gif of the above program.

Other FRACTRAN material on Stack Exchange that touches on the Turing completeness can be found at: Convert Fractran into Brainfuck (ok, that's a really productive use of one's time)

The reason that Fractran is Turing-complete is because it simulates a register machine. The number's prime factorization stores the contents of the registers, while the division and multiplication is a way to conditionally add and subtract from the registers.

Part of the trick here (and this starts straying into theory) is that behind the scenes, this is a Minsky register machine for which it was proved that certain tapes (programs) are Turing machines IF the tape is represented as a Gödel number which is exactly what the FRACTRAN number is (from the linked wikipedia page):

Gödel used a system based on prime factorization. He first assigned a unique natural number to each basic symbol in the formal language of arithmetic with which he was dealing.

So, we've got conditional loops, arbitrary variables stored as Gödel numbers, we've got a Turing machine.

Some other fun reading that touches on the Collatz like nature of FRACTRAN can be read at Can’t Decide? Undecide! that relate the Collatz conjecture to FRACTRAN and the halting problem.

FRACTRAN is a bit difficult to get one's head around.

Consider the program something like:

LABEL: start
    block1
    block2
    block3
    ...
END

In this, each block is of the form:

IF(registers X >= a, Y >= b)  # or any combination of registers
THEN
    X -= a
    Y -= b

    I += n
    J += m

    goto start

The first statement from the multiplication program above:

455
---
 33

Would be written in this form as:

IF(register `3` >= 1 && `11` >= 1)
THEN
     `3` -= 1
    `11` -= 1

     `5` += 1
     `7` += 1
    `13` += 1

    goto start

And thus you can clearly see the data storage and the looping constructs necessary for Turing completeness. Its very rudimentary, but it exists and runs as a simple register machine - but then thats all that you really need to be able to do.

Still not convinced?

This largely borrows from a lecture by Dimitri Hendricks on Models of Computation

This takes the very simple program (2/3) which is an adder (2a3b --> 3a+b) But it is destructive - the value in 2 is cleared as part of the process.

Lets write a higher level FRACTRAN that makes it easy to not do such destruction.

The original program could be thought of as:

   2
α: - → α
   3

In F2, one can specify 'functions' of a sort.

   10       1
α: -- → α , - → β
    3       1

   3
β: - → β
   5

To convert an F2 program (P) into a standard FRACTRAN program, one does:

  1. Clear P of loops of length 1
  2. Replace greek letters (functions) with fresh prime numbers
  3. Replace the transitions:
   a      c      e
p: - → q, - → r, - -> s, ...
   b      d      f

becomes:

aq   cr   es
-- , -- , -- , ...
bp   dp   fp

What this has done is used the primes p, q, r, and s to store the state of the program.

And then we've got the register machine... it has a finite number of registers that store arbitrary large numbers and two instructions:

  • inc(xi, m) - increment register i and go to line m
  • jzdec(xi, m1, m2) - if register i is 0 go to line m, else decrement i, and go to line m2.

This register machine has been shown to be Turing complete.

It then goes to show the process over several slides of compiling a register machine program into a FRACTRAN program as part of a mechanical process.

Basically:

                       p(i)
inc(x(i), m)        =  ---- → m
                        1

                        1          1
jzdec(x(i), m1, m2) =  ---- → m2,  - → m1
                       p(i)        1

And thus because of the equivalence between these two models of computing, FRACTRAN is Turing complete.

Btw, if you really want to have your mind blown, read Code Golf: Fractran in which some people wrote a FRACTRAN program to run another FRACTRAN program.

Related Topic