You don't have to know how much gas it requires to /complete/, you can just run the program and check whether it runs out of gas before it exits. You do not need to solve the halting problem. Actually, it's pretty trivial to implement this and this model has scaled quite well considering the size of Ethereum today.