home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / CLIPPER / MISC / BIPL.ZIP / DATA.ZIP / ONES.TUR < prev    next >
Encoding:
Text File  |  1992-09-20  |  1.8 KB  |  39 lines
  1. #  From: heim@tub.UUCP (Heiner Marxen)
  2. #  Newsgroups: sci.math
  3. #  Subject: busy beaver Turing machine
  4. #  Date: 24 Aug 89 13:24:10 GMT
  5. #  Organization: Technical University of Berlin, Germany
  6. #  
  7. #  This is about ``busy beavers'' (is there a more appropriate newsgroup?).
  8. #  Unfortunately I did read this newsgroup only sporadically, and don't know
  9. #  whether this has been discussed already.  My other sources of information
  10. #  (mainly the German issue of `Scientific American') don't tell me more.
  11. #  
  12. #  As far as I know the 5-state busy beaver question is not yet settled.
  13. #  With the help of a program I have found a 5-state Turing machine which
  14. #  halts (after 11,798,826 steps) and produces 4098 ones on the tape, namely
  15. #      A0 -> B1L    A1 -> A1L             // `A' is the initial state
  16. #      B0 -> C1R    B1 -> B1R             // `R' is `move right'
  17. #      C0 -> A1L    C1 -> D1R             // `L' is `move left'
  18. #      D0 -> A1L    D1 -> E1R
  19. #      E0 -> H1R    E1 -> C0R             // `H' is the halting state
  20. #  The best machine I knew before produces 1915 ones (published in 1985
  21. #  by Scientific American, I believe).  My questions are
  22. #   Q1: Is there ongoing (or completed) research ?  Any (theoretic) results ?
  23. #   Q2: Are there any better 5-state machines known or published ?
  24. #   Q3: Who else studies the busy beaver problem with general purpose computers?
  25. #  
  26. #  Answers to the above, hints and pointers are welcome.
  27. #  Please answer by e-mail; if appropriate I will summarize to the net.
  28. #  = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
  29. #  Heiner Marxen,            from europe:    unido!tub!heim
  30. #                  from world:    pyramid!tub!heim
  31. #                  bitnet:        heim%tub.BITNET@mitvma.MIT.EDU
  32.  
  33. 1. 1l2 1l1
  34. 2. 1r3 1r2
  35. 3. 1l1 1r4
  36. 4. 1l1 1r5
  37. 5. 1h0 0r3
  38.  
  39.