They are transcendent reality warpers, there is nothing that can kill them in the Halo universe (or any physical universe), not even the Halos themselves. Actually the Flood is The results of the remains of 1000 precursors who turned their bodies to dust to be restored at a later date being corrupted (supposedly it was the passing of 10 million years that corrupted the dust, but it may have also been the Primordial).