Cryptosystems whose hardness depends on solving the halting problem?
For any reasonable public key cryptosystem that I can think of, no, this is not possible. You cannot base a practical public key cryptosystem on any complexity class larger than EXPTIME.
If the private key is linear in the size of the public key (i.e. if the public key is $b$ bits in size, then the private key is no larger than $\alpha b + \beta$ bits for some constants), then you can test all possible private keys (in exponential time) and see which one decrypts a message.