home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / pyth_os2.zip / python-1.0.2 / Demo / turing / bench.tm < prev    next >
Text File  |  1994-03-02  |  2KB  |  53 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, ' '> --> <2, 'a'>
  34. <1, 'a'> --> <1, L>
  35. <2, 'a'> --> <3, L>
  36.  
  37. <3, ' '> --> <4, 'a'>
  38. <3, 'a'> --> <3, R>
  39. <4, 'a'> --> <5, R>
  40.  
  41. <5, ' '> --> <6, 'a'>
  42. <5, 'a'> --> <7, R>
  43. <6, 'a'> --> <1, L>
  44.  
  45. <7, ' '> --> <8, 'a'>
  46. <7, 'a'> --> <9, R>
  47. <8, 'a'> --> <1, L>
  48.  
  49. <9, ' '> --> <10, 'a'>
  50. <9, 'a'> --> <11, ' '>
  51. <10, 'a'> --> <0, R>
  52. <11, ' '> --> <5, R>
  53.