My question is a bit generic, so I'm making up a nice story to justify it. Bear with me if it's not realistic ;-)
Mr. X, the head of the computer security department at a big company, is a bit paranoid: he requires that all employees change their passwords once a month, in order to minimise the risks of identity or information theft. Moreover, he does not trust the employees to be able to come up with secure passwords.
Therefore, every month, he generates new passwords using a piece of software he wrote, and gives them to the employees so that they can log in again. But besides being paranoid, Mr. X is also a bit lazy: the passwords he generates all follow some pattern, and the algorithm used to allow people to log in only checks that the password "looks okay" according to that rule, and that it is not in the "expired list".
Unfortunately, his pretentious behaviour made a lot of people bitter, and one of them, Mr. Y, decides to prove him that he can crack his passwords. So, one night, he collects a few of them, and starts trying to design a learning algorithm for generating valid passwords, using his personal computer to verify them.
The oracle used by Mr. Y is a bit strange, in that it tells him "the truth, but not the whole truth" (hence the "taciturn" adjective). More precisely: Mr. Y will know that a password is valid when his computer accepts it, but when a password is rejected, Mr. Y will not know whether or not it could have been valid: the password may be rejected because it does not correspond to some pattern, but it may also be rejected because it used to be valid but no longer is, according to Mr. X's "change once a month"-rule.
So, will Mr. Y ever be able to come up with anything in that setting? Or can we claim/prove that Mr. X's passwords are inherently unpredictable (as defined in the PAC learning setting, but maybe this concept exists in other frameworks)?