I agree. All the best economists recommend a carbon tax.
Such laws are difficult to pass, though. A tax on proof-of-work contests would politically be easier and encourage switching to better algorithms.
Best would be to do both. It's good to have incentives both to switch away from fossil fuels and to switch away from proof of work.