Oh, one more thought.
Implementing a capcha in the core of the blockchain would make all bots just go away and crawl under their respective rocks for all time.

Of course, something like that would have be be thought through very, very carefully with a long period of public comment.