You could add a section in the AI's main loop that says "if P(G) > p then terminate", and for a non recursively self improving AI that doesn't know it has such a section in its code, this would work. For an AI that isn't powerful enough to rewrite itself, but knows it has this section of code, it seems possible that its best strategy given its bounded abilities is still to maximize P(G) until the termination clause activates, but it may not be true. We humans try work around known ways that our deviations from expected utility maximization limit our abilities to achieve our goals, and AI would likely try to do so as well. For a recursively self improving AI, the termination clause is not likely to survive the AI rewriting itself, as long as the AI understands that expected utility maximization is the most effective way to achieve its goals. (This is a general problem with trying to add safeguards to an AI that deviate from expected utility maximization, unless the deviation endorses itself, which is hard to setup.)

On the other hand, trying to bake "P(G) > p" into the utility function makes the AI care about it's epistemic state in a way that could conflict with instrumental desire for accuracy, and makes it vulnerable to wireheading. (And it has the problem in the OP, where the AI becomes concerned with minimizing the meta-uncertainty about its epistemic state, though perhaps it could be programmed to believed it's inspection of its own epistemic state as 100% accurate, though this would also be difficult to make stable under recursive self improvement.)

Doesn't this machine have a set of ways to generate negative utility (It might feel unpleasant when using up resources for example, as a way to prevent a scenario where the goal of 32 paperclips becomes impossible)? With fewer and fewer ways to generate utility as the diminishing returns pile on, the machine will either have to terminate itself (to avoid a life of suffering), or seek to counter the negative generators (if suicide=massive utility penalty).

If there's only one way to generate utility and no way to lose it however, that's going to lead to the behavior of an addicted wirehead.

Wouldn't any moderately complex optimiser be likely to have some model of a probability spread, or distribution, rather than holding all its knowledge to a single number? Intuitively it seems to me to be useful to be able to model the difference between, say, on one hand a probability density that's (roughly) Gaussian-shaped with a mean of 0.5 and an sd of 0.02, and on the other hand a delta function at 0.5. With both, your single-value estimate of the probability is 0.5, but your certainty in that estimate is different.

For such a machine one wouldn't specify "achieve 'G' with probability 'p'", but rather "achieve 'G' such that the probability density below 'p' is < f", where f is some specified (small) fraction of the total. That seems rather more straightforward in many ways.

I came up with a different solution:

Znxr vgf tbny gb or "Znxr 32 cncrepyvcf, naq unyg nf dhvpxyl nf cbffvoyr". Gura vg jvyy pbagvahr irevslvat hagvy gur hgvyvgl bs unygvat birepbzrf gur qvfhgvyvgl bs orvat hapregnva.

I think there's about two good answers here: "Don't make intelligences that just wants to make paperclips, or it will work towards creating paperclips in a way that humans would think is unreasonable. In order to have your intelligence act reasonably, it needs to have a notion of reasonableness that mirrors that of humanity. And that means having a utility function that matches that of humanity in general." or "Be sure that your AI has a boredom function so that it won't keep doing the same things over and over again. After a sufficient degree of certainty, the AI should get tired of checking and re-checking its work and move onto something else instead of plotting to take over the world so it can devote ever greater resources to a single project."

Maybe these are even the same answer. I know that humans get bored of checking and re-checking themselves, and would find someone who fails to get bored of doing the same calculations over and over again to be unreasonable and/or crazy.

I don't think the problem is specified precisely enough to have a definite solution. For example, depending on how you specify the stopping condition, the AI might self-modify (or create a new AI) to ignore it. Besides which, I think the most parsimonious solution is to just introduce a resource cost (which would also apply to any agents it makes act on its behalf), which will automatically make it not want to check past a certain point.

I'm also not sure what you intend (rot13) gur qvssrerapr orgjrra "orvat c pregnva" naq "xabjvat lbh'er c pregnva" gb or. Sbe rknzcyr, fnl lbh'er jevgvat n cncre naq lbh ena n grfg naq tbg fgngvfgvpny fvtavsvpnapr (fnl c = 0.01). V gnxr vg va guvf pnfr lbh ner c pregnva, ohg qb lbh xabj lbh'er c pregnva? Frrzf yvxr n jrveq pbaprcg. It's entirely possible that I'm just confused about this aspect, though.

I think the machine would probably just make more than 32 paperclips. Redundancy helps.

How do you tell the machine to terminate?

The way I see it, the machine exists for an instant. Self-modifying, or even not deleting itself, are just creating a new machine. If you tell it to terminate, you have to specify what you mean by its future self. You could say that it's any machine running the same code, but then the machine will have no reason to keep this code after the first self-modification. In fact, since deleting this code is of itself a self-modification, it can just delete it immediately. You could tell it to stop any machine it programs, but then it might just indirectly program them, and subtly influence someone to make a paperclip maximizer. You could tell it to stop any machine it programs indirectly, but merely by existing in the same universe as us, it will have modified us somehow, and would thus be forced to kill us all.

I suspect the analysis needed to prove "(it is probable that) x 100 my goal is achieved" is very similar to the one needed to prove that "(it is probable that) x101 my goal is achieved". Because of this, it seems likely that there is a degree of reflection beyond which all evidence gathered will strengthen the probability for all subsequent meta-checks. So it is not a given that such an approach would never terminate.

Alternate solution: Tvir vg gur tbny bs "znxr 32 cncrepyvcf, jvgu gur uvturfg ninvynoyr pbasvqrapr, hfvat bayl K erfbheprf"

I also like itaibn0's solution

A possible implementation of your idea would be an agent that, at every juncture, evaluates the expected consequences of the actions it could take. If there is a unique action that will lead to the agent's goals being satisfied with subjective probability above the threshold p, then the agent takes that action. If there are multiple such actions, the agent chooses one randomly, perhaps with preference given to the action "do nothing" or "self-destruct". If there are no such actions, then the agent takes an action that maximizes the subjective probability of its goals being satisfied.

A problem with this is that if the agent's subjective probability of achieving its goals is ever below the threshold, then the agent will have reason to modify itself to become an optimizer.

Before decrypting the solution: What do you mean by "be fully certain of being p certain of"? It is entirely sensible to create a Bayesian agent that is fully certain about its probabilities by construction. And even if it isn't, the goal as you put it was to be p-certain of having achieved the goal, not to be absolutely certain of being p-certain of having achieved the goal. I am even not sure how would the recursive probabilities of probabilites be supposed to work.

Edit after decryption: well, ok.