"Given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input."
(Wikipedia entry for the Halting problem)
The undecidability of the halting problem is a well-known result in the Theory of computation. There is no Turing machine that can both solve the halting problem for all possible program-input pairs AND be garanteed to always achieve the answer in finite time. Turing Machines tasked with solving the halting problem may themselves never stop!
Now, imagine that the functionalist conception of the mind is the correct one. That means some Turing machines, when run, can have (produce?) minds, and qualia. Obviously, not all of them do. I don't think a machine that continuously writes in a tape an alternating sequence of ones and zeroes -or my computer for that matter- is as conscious as me. (Though my computer is certanly evil.)
So we need a way to decide which computations produce minds and qualia, and which don't. This could be a pressing issue in a post-singularity scenario, where computation is pervasive and a bewildering menagerie of vastly different minds and bodies have come into existence. In that scenario, the problem of other minds would be no mere solipsistic daydream, but a very real issue and a matter of utmost concern. Why?
Contingent facts, like that every human brain has been shaped by the same evolutionary processes, ensure that we all have roughly similar bodies and minds, and that we experience roughly similar mental states and qualia. If I pinch somebody, I can be pretty sure that he feels pain. For one, I feel pain when pinched, and his body and nervous system are structurally similar to mine. Also, he might complain in a language I can understand, or simply start wailing.
After the singularity, we would have no such anchors. Every sufficiently complex algorithm being executed in the universe could turn out to be a mind. Perhaps a completely alien one with which communication would be impossible (like Stanislaw Lem's Solaris). Or perhaps a mind very much like ours living in a simulated environment, only the algorithm is such that we can't easily realise that (imagine for example a mind running on obfuscated code). Unknowingly stopping the execution of such an algorithm would be tantamount to involuntary mindslaughter.
So, should we refrain in the future from ever closing our screensavers? That doesn't seem practical. What we need then is a Turing machine which, given the description of another Turing machine, can predict if the execution of that machine will produce a mind. We could test our screensavers with it, to check if we are morally allowed to close them.
But, what if the "is-there-a-mind" problem turns out to be, in a way, analogous to the halting problem? If any possible Turing machine for solving the "is-there-a-mind" problem may itself develop a mind? If a machine cannot "detect" pain without feeling pain, or "detect" love without falling in love? That would bring with it a host of difficult issues.
I think this is a nifty premise for a science fiction story. (If such a story already exists, I'll be pissed off. One would like to have an original idea once in a while.)