Because some problems we lack the ability to solve any other way. There are at least three problems which are famous, as described in the article I linked.

see if you follow this one one, for a real computer:

Suppose I pick a n bit key, and encrypt a phrase with it. I will provide you the plain text phrase and either a real or fake cipher text. You have to determine if a program which loops through all the keys will decrypt the ciphertext into a the phrase.

Either you know weaknesses in the crypto system, or you have no choice but to iterate though each key to see if the output matches the phrase.

There is a relationship with proof of work crypto as well. Even all the Bitcoin mining has trouble finding hashes with a certain number of leading zeroes, add a few more zeros and no one will ever find a working seed again. There is no way to speed up the process beyond iterating over the seeds.

You can tie this to the halting problem by just saying to go back the key 0 once the key space is exhausted.