Why does Ethereum have gas? What other approaches could Ethereum have used to work around the Halting Problem?
The halting problem is not the only reason to have a gas fee system. It would have been possible to limit functionality by a small margin, thereby making it non Turing complete but still (almost) as useful for smart contracts.
The other reason is that miners should be rewarded proportionally to their running costs, otherwise the incentive structure would not scale. And it will push users to use instructions that are cheap for them, but expensive for miners/validators.
From the docs page:
In order to prevent deliberate attacks and abuse, the Ethereum protocol charges a fee per computational step.