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

Re: {Spam?} [PrimeNumbers] FRACTRAN and factoring

Expand Messages
  • 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 1 of 2 , Aug 8, 2008
      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.