And sufficiently smart human can find a way to unplug AI faster than it can rebuild itself... An AI cannot cutoff oxygen supply on eartth.

We aren't necessarily all alive anymore !

We weren't necessarily all human (me and my dog), but now "we" can include machines. 

That's obvious I know. We have changed dramatically in just a few years.

I've just asked various AI "Who are we?". Old models got it wrong (automatically assume "we" means humanity...). Recent models gets it. I wonder if its due to the training data now including chats between AI and human or if they figured it out logically.
 

The 1+1=2 joke will forever lives as a meme.

The only things coming close is the 15=3*5 quantum computing paper.

OK, so an approximate sorting algorithm in O(n) would do the trick.

The problem then boils down to weither computing the cost of (computing expected cost) is worth the expected gain.

Which goes back to my initial question : is there a rationality paradox ? Maybe simply the fact that 1) computing cost might boils down to the halting problema 2) cost's cost's cost... is possibly infinite ? 

So P_i/C_i is in [0,1], the precision is unbounded, but for some reason, a radix sort can do the job in linear time ?

There could be pathological cases where all P_i/C_i are the same up to epsilon.

I guess I'm searching for situation where doing cost c, computing c cost c', etc... Branching prediction comes to mind.

 

What do you mean I don't "need"  O(n log(n)) sorting ?

It's just the asymptotic cost of sorting by comparison...

I'll have a look into bounded rationality. I was missing the keyword.

EDIT : had a look, the concept is too imprecise to have clear cut paradoxes.

 

Are there known "rational paradoxes", akin to logical paradoxes ? A basic example is the following :

In the optimal search problem, the cost of search at position i is C_i, and the a priori probability of finding at i is P_i. 

Optimality requires to sort search locations by non-decreasing P_i/C_i : search in priority where the likelyhood of finding divided by the cost of search is the highest.

But since sorting cost is O(n log(n)), C_i must grow faster than O(log(i)) otherwise sorting is asymptotically wastefull.

Do you know any other ?

In collectible games, after 1/p trials, there is 1/e = 63% chance to get a desired item.

But a full collection is completed in -ln(p)/p trials in average. For p = 1/n, its n*ln(n).

For instance, getting an outcome with 10% frequency requires in average 10*ln(10) = 23.026 trials.
1% is 460 trials
1/1000 is 6900 trials, etc...

In gacha games, developpers can guarantee you a 10% event in every 10 trials. The market fits irrationality, for a price.