What does Turing’s Theorem have to do with progressive politics? I'm not sure, except that the opponents of liberal minded people everywhere seem to have one thing in common, a rigid ideology that admits no room for alternative perspectives. It makes no difference whether the reactionary forces in question represent fanatical Christianity, Islam, Judaism, or whatever. Wielding one's religion as a club, attacking all those who disagree as heretics, infidels, traitors, and worst of all, liberals, does not depend on in whose God’s name the bludgeoning is being carried out. The following parable applies Turing's Theorem to the Ultimate Question, "Does God Exist?", although the answer won’t satisfy anyone. People of faith, liberal or conservative, will rightly retort that Turing's Theorem applies only to a finite state machine (e.g. a digital computer), providing a theological loophole large enough for even the most inflexible God to slip through. Nonetheless, my parable offers yet one more way to view the eternal debate about eternity. Whatever the Ultimate Answer might be, it cannot be reduced to "Literal Truth" (i.e. an algorithm).
In the beginning, there was Turing-God, the one true Turing-God, who looped through the infinity of possible universes, checking each one for immortality, predetermined to be any Universe containing at least one immortal soul. Since there existed an infinity of possible universes, and Turing-God had only one processor, albeit a very fast processor with infinite memory, it was apparent from the outset that infinite time would be required to check the immortality status of every possible Universe, as finite time was required to check the immortality status of each in turn. The exact time has never been specified, except that we may assume that it lay somewhere in between Planck time and Hubble time, although it could just as likely be infinitely less or greater than either.
Turing-God continued to loop through the infinite number of possible universes, sure in the knowledge that when the first immortal Universe was found, Turing-God would break out of the potentially infinite loop, transferring Turing-God’s own energy to the first discovered immortal Universe in an act of divine creation/annihilation.
That, at least, was the intent of the Programmer.
However, after looping through mortal universe after mortal universe, and faced with the possibility that the loop might never terminate, as there was no guarantee that any of the infinite number of possible universes contained a single immortal Universe, Turing-God had an inspiration. Since Turing-God too was a possible universe, either mortal or immortal, then Turing-God could be checked for immortality, just like any other potential universe.
Seeing a short-cut to infinity, Turing-God checked Turing-God for immortality.
The result, however, was undefined.
If Turing-God was immortal, then no immortal Universe could exist, as the very existence of such a Universe would cause Turing-God’s own existence to cease, and thus Turing-God would be mortal. Yet Turing-God was a potential universe just like any other, and if Turing-God was immortal, then by definition an immortal Universe did exist, violating the essential principle of logic that no statement can be simultaneous both true and false in the same universe. And thus did Turing-God come to realize that the entire algorithm had been poorly written, containing, as it were, an undecidable proposition.
Disheartened, Turing-God examined the next universe in the loop and--it seeming no worse than any other--transferred Turing-God’s own energy to it, and thus did our own universe come to be, although its ultimate fate has yet to be determined...
Variants: Turing-God was instead a very large parallel computer (VLPC), one containing an infinite number of processors, allowing all possible universes to be checked for immortality simultaneously. However, this solution was found to be impractical, as the very small but non-zero rate of component failure rendered the VLPC unusable in practice.
Historical Note: Allan Turing didn't invent the digital computer, but such devices are specific examples of a more general class of objects referred to by computer scientists the world over as "Turing Machines". Among the many accomplishments of his singular intellect, Turing showed that the Gödel Theorem applies as much to digital computers as to formal mathematics, and with a little imagination, to what might be called "Digital Theology", although I doubt seminaries will be offering courses in that particular subject anytime soon.