Bill Gosper

Home * People * Bill Gosper

Bill Gosper 2006

Ralph William (Bill) Gosper, Jr., an American mathematician and computer scientist, along with Richard Greenblatt considered the co-founder of the hacker community . In the 60s, affiliated with MIT, he worked for Project MAC (Machine-Aided Cognition), where his contributions to computational mathematics and Bit-Twiddling include HAKMEM and Maclisp. He helped Greenblatt with his chess program Mac Hack VI, and operated the PDP-6 when Robert Q played its first tournament game versus Carl Wagner.

In the 70s, Bill Gosper moved to Stanford University for some years, where he lectured and helped Donald Knuth to write volume II of The Art of Computer Programming. He has worked at or consulted for Xerox PARC, Symbolics, Wolfram Research, the Lawrence Livermore National Laboratory, and Macsyma . Bill Gosper created numerous packing problem puzzles such as the Twubblesome Twelve , and was interested in the Conway's Game of Life, where he found the Gun and originated the Hashlife algorithm to speed up the computation of Life patterns.

Robert Q

First tournament game by a computer, Carl Wagner (2190) - Mac Hack VI aka "Robert Q", January 21, 1967 . "Robert Q", a computer programmed to play chess, was beaten in its first competition with a human, Carl Wagner. The computer, at MIT in Cambridge, Mass., was operated by Allen Moulton, and R. William Gosper, while Wagner made his moves several miles away in the YMCU in Boston. The moves were relayed into the computer by teletype operated by Alan Baisley. "Robert Q" was entered as an experiment, in the monthly Boylston Chess Club Tournament at the Young Mens Christian Union.

Allen Moulton and R. William Gosper (rear right) operating "Robert Q" on a PDP-6

HAKMEM

HAKMEM, alternatively known as AI Memo 239, is a February 1972 "memo" (technical report) of the MIT AI Lab by Gosper et al. that describes a wide variety of hacks, primarily useful and clever algorithms , and even a chess position . A few samples, referred elsewhere:

HAKMEM 70

HAKMEM 70 , A neat chess problem, swiped from Chess for Fun and Chess for Blood, by Edward Lasker . White mates in three moves :

                                                                                                             ♗         ♙   ♟                 ♘       ♚♙         ♔

5B2/6P1/1p6/8/1N6/kP6/2K5/8 w - -

HAKMEM 169

HAKMEM 169, to count the ones in a PDP-6/PDP-10 36-bit word, written in Assembly :

   LDB   B,[014300,,A]     ;or MOVE B,A then LSH B,-1
   AND   B,[333333,,333333]
   SUB   A,B
   LSH   B,-1
   AND   B,[333333,,333333]
   SUBB  A,B               ;each octal digit is replaced by number of 1's in it
   LSH   B,-3
   ADD   A,B
   AND   A,[070707,,070707]
   IDIVI A,77              ;casting out 63.'s

HAKMEM 175

HAKMEM 175 - next higher number with the same number of one bits (Snoob), by Bill Gosper, PDP-6 Assembly :

   MOVE  B,A
   MOVN  C,B
   AND   C,B
   ADD   A,C
   MOVE  D,A
   XOR   D,B
   LSH   D,-2
   IDIVM D,C
   IOR   A,C

Gosper's Glider Gun

Gosper's Glider Gun in action — a variation of Conway's Game of Life

See also

• Bit-Twiddling
• Mac Hack VI
• PDP-6
• Traversing Subsets of a Set

Selected Publications

• Michael Beeler, Bill Gosper, Rich Schroeppel (1972). HAKMEM, Memo 239. CSAIL, MIT
• Bill Gosper (1974). Acceleration of Series, Memo 304. CSAIL, MIT
• Bill Gosper (1977). Decision procedure for indefinite hypergeometric summation. PNAS USA, Vol. 75, No. 1, pdf

External Links

• Bill Gosper from Wikipedia
• Twubblesome Twelve - a difficult puzzle

R. William Gosper

Rep-tiles

• HAKMEM from Wikipedia, HAKMEMC -- HAKMEM Programming hacks in C by Alan Mycroft
• Gosper's algorithm from Wikipedia
• Gosper curve from Wikipedia
• Hashlife from Wikipedia

References

Up one level