Hercules versus the Hydra

Exploring fast-growing functions with a simple game

Hercules Versus the Hydra is a Greek legend about Hercules fighting a monster called the Hydra. According to Greek mythology, the Hydra - often known as the Lernean Hydra - was a monster with many heads who lived in a marsh near the region of Lerna. Every time Hercules chops off one of the Hydra's heads, multiple new heads grow back. Whether or not Hercules will win the battle and destroy all the heads of the Hydra will depend upon how many heads grow back each time one is removed.

Hercules and the Hydra

We start with a string of the letters 'a' and 'b'. The aim is to destroy the string, with three rules: each turn, the first letter is lopped off, an 'a' becomes 'ab' and 'b' stays the same.



a → ab
b → b

This work explored the range of possible outcomes under different rules, and starting strings. Examples of games under the simple case (two letters and three aforementioned rules) are shown below. The first is a short game, starting with the string 'abb' the second is still a fairly short starting string, 'abaaba', but with many more steps.

abb
bb
b
3 steps


abaaba
bababbab
abbabbbabb
bbabbbbabbb
babbbbbabbbb
abbbbbbabbbbb
bbbbbbabbbbbb
bbbbbabbbbbbb
bbbbabbbbbbbb
bbbabbbbbbbbb
bbabbbbbbbbbb
babbbbbbbbbbb
abbbbbbbbbbbb
bbbbbbbbbbbb
bbbbbbbbbbb
bbbbbbbbbb
bbbbbbbbb
bbbbbbbb
bbbbbbb
bbbbbb
bbbbb
bbbb
bbb
bb
b
25 steps

The initial observations of this simple game are listed below. The game gets more interesting when we introduce more letters and rules. Check out the report.

You can read the full report here.