Can a computationally unbounded adversary break any public-key encryption scheme? Assume there is a public-key encryption scheme $(KeyGen, Enc, Dec)$ with perfect correctness (i.e., for all messages M and valid key-pairs (PK,SK), we have $Dec_{SK}(Enc_{PK}(M))=M$).

Will there always be a function $A$ such that for all messages M and valid public-keys PK, $A_{PK}(Enc_{PK}(M))=M$?

In other words, can a computationally unbounded adversary decrypt the message, having only the public key?
Yes, a computationally unbounded attacker can break any public key system.

One easy way to see this is to consider the KeyGen algorithm, which takes takes as input a value R (which in normal use is the output of some random number generator), and outputs a public key PK and a private key SK.

Now, what a computationally unbounded adversary can do is consider all possible inputs R, and see which one produces the public key that he has been given.  We know that there is at least one such input R (the one that was used when the public key was created); we can then use the corresponding private key to decrypt the message.

The obvious objection to this is "what if there are multiple such R's which generate the same public key, but different private keys?".  Actually, it turns out that this is not a problem; because each such private key SK was generated correctly by the key generation function and corresponds to the public key under attack, it must still satisfy the formula:

$Dec_{SK}(Enc_{PK}(M)) = M$

Hence, it must correctly decrypt the message, even if it was not the exact private key that the legitimate user had.