If someone gets cremated or buried long enough for eir brain to fully decompose into dirt, it becomes extremely difficult to revive em. Nothing short of a vastly superhuman intelligence would have a chance of doing it. I suspect that it would be possible for a superintelligence to do it, but unless there's a more efficient way to do it, it would require recomputing the Earth's history from the time the AGI is activated back to the death of the last person it intends to save. Not only does this require immense computational resources that could be used to the benefit of people who are still alive, it also requires simulating people experiencing pain (backwards). On the other hand, this saves people's lives. Does anyone have any compelling arguments on why an FAI would or would not recreate me if I die, decompose, and then the singularity occurs a long time after my death?
Why do I want to know? Well, aside from the question being interesting in its own right, it is an important factor in deciding whether or not cryonics is worth-while.
OK, let's make a few assumptions. Assume, for a start, that all the information in your brain is necessary to resurrect you, down to the quantum level. And that this is incompressible - that even computronium requires as much mass/energy as is contained in your brain in order to perfectly simulate it. But assume also that an FAI can convert matter/energy into computronium.
By the Bekenstein Bound, the absolute maximum number of brain states that could be possible is 10^(7.79640 10^41) , which we can approximate as 10^10^41. Note this is a SERIOUSLY HIGH estimate. That would be the number of possible states of any* roughly-spherical lump of matter of the right radius and mass. The mass of a brain is between one and two kilograms, so very roughly, we'd need 10^10^41 kg of computronium to simulate every possible brain state.
The mass of the galaxy is 10^42 kg, so the mass of the galaxy is exponentially smaller than the mass that would be needed to simulate every possible brain state.
So that's an upper limit - but that limit rests on wanting simulations of every possible brain state to exist simultaneously, where 'brain state' means everything from the state my brain is in now, to the state it was in one nanosecond ago, to the state that a 1.5kg bag of sugar was in half an hour ago, to...
If we wish to limit ourselves to brains that have existed, then the figure could be much lower. By definition, every human brain thus far has been made from the mass on the earth's crust and atmosphere, and there have been roughly a hundred billion people ever - they could easily be computed if we had precise data about their states, using considerably less mass than that of the Earth.
So the question becomes, is there any way of winnowing down the 'possible brain states' to the 'have-existed brain states'? I would expect so, to quite a large extent. Firstly, you'd only want to use those brain states that correspond to actual states of human brains - the state that corresponds to being a chunk of my armchair could be thrown away. That in itself would get rid of the vast bulk of possible states of matter.
Secondly, most of the resulting states would be duplicates. There would be my brain now, my brain a second ago, my brain as it would be in a universe where I'd chosen a different pair of socks this morning but otherwise nothing was different... I don't think anyone in the world would have any actual problem (as opposed to philosophical problems) identifying those people as one individual.
Thirdly, we can limit by known history. Obviously as one goes further back, what 'known history' is is foggier, but we can, for example, not simulate any brains whose memories would require them to have been born on Alpha Centauri in the year 5BC and to be 12 in the year 2032 - getting rid of brains with logically inconsistent or physically impossible pasts would winnow it down some more.
And finally, if all else fails, you can brute force the problem over multiple universes. Of the brains that are left to be simulated, select a subset of them to simulate using a quantum experiment, and leave the others to other aspects of the multiverse (this is assuming the multiversal interpretation of quantum physics to be correct, but I would imagine that a greater-than-human intelligence would have some way of confirming this beyond all doubt).
So my own thought is it's physically possible (assuming a situation where a FAI exists, which is a whole other problem in itself), but extraordinarily difficult. I would not expect it to happen unless and until a good proportion of the galaxy was converted to computronium. But should that happen, and should a FAI exist, then it would pretty much be the definition of 'friendliness' that it would resurrect people, starting with those easiest to bring back.
My own guesstimate is that, conditional on FAI being achieved in the next 100 years (so enough information is preserved to make them relatively easy to resurrect), and conditional on it being able to use mass utterly efficiently for computation, then there is probably as great as a 40% chance that those alive today but dead before FAI is created would eventually be resurrected with enough fidelity that they couldn't themselves tell the difference. How high you put the probability of FAI and computronium is, of course, up to you.