Tuesday, September 12, 2006

Busy Beaver hunter up and running!

A hastily-written python program hums quietly away on four different machines, patiently guessing solutions to the 5-node busy beaver problem. Hooray!! If I'd been thinking properly, I'd have written it in scheme and used gambit to compile it... the algorithm I'm using uses constant memory, but is quite greedy in terms of computation time, so every little bit of speed counts.

After about half an hour of running, one of the processes has found a machine that produces 12 marks after 61 cycles!

It would help prune down the search space enormously if I could prove there were equivalent turing machines out there that had non-isomorphic state graphs; especially if the result allowed us to prune down the possible labels for the edges of the state graph! That's where the really terrible performance comes from...


Post a Comment

<< Home