## FRACTRAN and factoring

Expand Messages
• I am just curious, as I have only just discovered FRACTRAN. Is is theoretically possible to write a program that factors a given number in FRACTRAN? I
Message 1 of 2 , Aug 7 5:18 AM
I am just curious, as I have only just discovered FRACTRAN.

Is is theoretically possible to write a program that factors a given
number in FRACTRAN? I appreciate that, if it is possible, this may not
be a very efficient method, but I am astounded that a FRACTRAN
algorithm can produce the primes in order (well it produces b^p for a
given initial input)

Regards

Robert
• ... If you believe the statement that FRACTRAN is Turing-complete (I haven t checked the proof myself) then the answer to your question is an unambiguous YES.
Message 2 of 2 , Aug 8 1:24 AM
On Thu, 2008-08-07 at 12:18 +0000, Robert wrote:
> I am just curious, as I have only just discovered FRACTRAN.
>
> Is is theoretically possible to write a program that factors a given
> number in FRACTRAN? I appreciate that, if it is possible, this may not
> be a very efficient method, but I am astounded that a FRACTRAN
> algorithm can produce the primes in order (well it produces b^p for a
> given initial input)

If you believe the statement that FRACTRAN is Turing-complete (I haven't
checked the proof myself) then the answer to your question is an
unambiguous YES.

Proof: all Turing-complete languages can simulate all other
Turing-complete languages. Find a language and a program that can
factor a given integer (this part is easy) and then write an interpreter
for that language in FRACTRAN and run its program on the interpreter.

Paul

[Non-text portions of this message have been removed]
Your message has been successfully submitted and would be delivered to recipients shortly.