Gas is analogous to cycles of the EVM that the contracts uses when it executes. Someone suggested 'gas' should have been called 'cycles' to more clearly convey its meaning and avoid a lot of confusion. Anyway, gas/cycles must be limited given there are no access controls on use of the EVM. It's an effective DoS control. It's also orthogonal to Turing Completeness.