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.
From finance point of view, the purpose is to incentivize miners to execute transaction and smart contract by using their own time and resource. Many complex operations need more computation resource; that is to say, they need to pay more GAS. If a user wishes to have their transaction prioritized, he can submit transaction with higher GAS price. In this way, transaction could be processed sooner by miner incentivized by higher transaction fee. As compensation for computation resource which miner invests in, GAS becomes more crucial after consensus migrates to Proof of Stake (POS). In POS era, miner no longer get rewarded by mining blocks and packing transactions, it is more important for miner to process transaction and get paid for expending resources on the blockchain.
The theoretical purpose is to align the incentives of participants on the network. Much of blockchain theory discusses how to mitigate harmful or malicious actors in a trustless environment. GAS partially addresses this issue: Miners are incentivized to work on the network and users are de-incentivized from acting poorly or writing malicious code as they are putting their own ether (in the form of gas) at risk.
From computational point of view, the computational reason behind GAS goes back to an old, foundational aspect of computing theory—the Halting Problem. The Halting Problem is the issue of determining whether an arbitrary program will stop running or if it will run forever just from looking at the description and the input values. In 1936, Alan Turing determined that it is impossible for any machine to solve the Halting Problem. In the EVM, this means a miner is never able to begin processing a transaction and know 100% that the transaction will not go on forever. With GAS—specifically, GAS limit—a finite amount of gas is always attached to a transaction. Even if a miner began processing a transaction that was coded to continue indefinitely—either from a bug or an attack on the network—the gas would eventually run out, the transaction would end, and the miner would still be compensated.