Loading ...
Sorry, an error occurred while loading the content.
 

FRACTRAN and factoring

Expand Messages
  • Robert
    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
    • Paul Leyland
      ... 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.