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]