Skip to main content

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.  

Originally posted to rapture on Sat Nov 10, 2007 at 11:22 AM PST.

Your Email has been sent.
You must add at least one tag to this diary before publishing it.

Add keywords that describe this diary. Separate multiple keywords with commas.
Tagging tips - Search For Tags - Browse For Tags


More Tagging tips:

A tag is a way to search for this diary. If someone is searching for "Barack Obama," is this a diary they'd be trying to find?

Use a person's full name, without any title. Senator Obama may become President Obama, and Michelle Obama might run for office.

If your diary covers an election or elected official, use election tags, which are generally the state abbreviation followed by the office. CA-01 is the first district House seat. CA-Sen covers both senate races. NY-GOV covers the New York governor's race.

Tags do not compound: that is, "education reform" is a completely different tag from "education". A tag like "reform" alone is probably not meaningful.

Consider if one or more of these tags fits your diary: Civil Rights, Community, Congress, Culture, Economy, Education, Elections, Energy, Environment, Health Care, International, Labor, Law, Media, Meta, National Security, Science, Transportation, or White House. If your diary is specific to a state, consider adding the state (California, Texas, etc). Keep in mind, though, that there are many wonderful and important diaries that don't fit in any of these tags. Don't worry if yours doesn't.

You can add a private note to this diary when hotlisting it:
Are you sure you want to remove this diary from your hotlist?
Are you sure you want to remove your recommendation? You can only recommend a diary once, so you will not be able to re-recommend it afterwards.
Rescue this diary, and add a note:
Are you sure you want to remove this diary from Rescue?
Choose where to republish this diary. The diary will be added to the queue for that group. Publish it from the queue to make it appear.

You must be a member of a group to use this feature.

Add a quick update to your diary without changing the diary itself:
Are you sure you want to remove this diary?
(The diary will be removed from the site and returned to your drafts for further editing.)
(The diary will be removed.)
Are you sure you want to save these changes to the published diary?

Comment Preferences

  •  Heady discourse (7+ / 0-)

    Alan Turing is a great hero of mine.

  •  Read this because I'm reading (4+ / 0-)
    Recommended by:
    Danjuma, Rogneid, OHdog, Demi Moaned

    Neal Stephenson's "Cryptonomicon" in which Turing plays a role, and just today picked up Edmundo Paz Soldán's "Turing's Delirium."

    There's an old middle-eastern story about Moses walking along and seeing a man worshipping a cabbage. He beats the stuffing out of the idolatrous fool, and admonishes him about his bizarre beliefs. Later, God speaks to him and says "Moses, what's wrong with you? Worshipping a cabbage was as close to worshipping me as that person could get at this point. I didn't mind." Moses then goes back to apologize to the battered cabbage worshipper, who profusely thanks Moses for shaking him out of his delusion about the nature of God.

    Go figure.

    There's been a decades-long assault on, and cartoonization of, religion by the mass-reach media, aided and abetted by allowing only the parodists of religion--Falwell, Robertson, et al--as representative of real religion. Apparently, anything that gives people a larger perspective is bad for consumption, and needs to be countered.

    A lot of modern "god is bullshit" stuff comes from the, now decades-old, marketing conditioning, and a not very deep exploration of the premises of mature religionists. Fundamentalism, a self-serving perversion of religion pure and simple, is the choice of about one in six people worldwide, and hardly the only take on the subject.

    For instance the famous "how many angels on the head of a pin" was not monks sitting around shouting "412--ummm, no--1,318." It was a conscious reductio ad absurdum around the question of whether the laws of the ways things happen (for "laws' read "angels") were themselves of a material nature. Translated into modern perspective, I might ask you to show me this famous law of gravity we keep hearing about. Show me the thing itself, as opposed to showing me consistent results of the theory. The theory of angels as hidden cause of material world action, after all, pretty reliably predicted that the sap would rise in spring.

    It is, to me, no small matter that every single mystical tradition, monotheistic and otherwise, has a variation of "God is not reducible to any symbolic condition." As in fact the vast stream of self-arising activities, and the self-arising awareness of same, are not. Except when reduced to a very narrow field of consideration. Like zeros and ones for information.

    I think that point is what makes the positing of the Turing-God here flawed. But great fun in any case. Enjoyed the effort.

    Until we break the corporate virtual monopoly on what we hear and see, we keep losing, don't matter what we do.

    by Jim P on Sat Nov 10, 2007 at 12:15:15 PM PST

    •  well put... (2+ / 0-)
      Recommended by:
      Rogneid, Jim P

      Indeed, reducing conceptions of God, whatever that might or might not be, to strings of ones and zeros, is an inherently flawed exercise, as you quite eloquently point out. However, it is such a stretch to argue that any fundamentalist interpretation, such a dogmatic literal interpretation of scripture, makes the same error?  An algorithm is an algorithm, and as Turing proves, even the space of all possible algorithms contains non-computable questions.  Thus, perhaps we can agree that whatever the answer is, it cannot be reduced to black and white proscriptions, or ones and zeros, depending on what language you prefer.

      •  I'd agree with you to the extent (1+ / 0-)
        Recommended by:

        that any formulation about God and what such a Being can or cannot do or desire can always been falsified by an actual situation and it's requirements.  Granting a Being who stands outside of time/space constraints, no formulation of whatever sort could possibly limit or encompass said Being.

        Most importantly people into science, logic, and the abstract are ALWAYS more fun than fundamentalists. And more likely to actually bring benefit to their fellow beings.

        I personally prefer "The Absolute of which nothing more can be said" to "God" but that gets a little much in ordinary conversation. And stops all theological ones.

        Again, thanks for the fun and the mind-stretching.

        BTW, if you like this stuff (and I'm betting you do) I can't recommend Neal Stephenson's Baroque Cycle highly enough. All 2,700 pages of it. Basically it covers the foundation of modern science, industry, computers, and capitalism. Newton & Leibnitz and god & science and zeros & ones and much more!

        Although published after Cryptonomicon, which is set 200-300 years later than BQ, many of the characters and ideas in Crptmcn are enjoyed more fully having read BQ first.

        Until we break the corporate virtual monopoly on what we hear and see, we keep losing, don't matter what we do.

        by Jim P on Sat Nov 10, 2007 at 03:06:26 PM PST

        [ Parent ]

  •  Read Isaac Asimov's favorite story (2+ / 0-)
    Recommended by:
    Rogneid, OHdog
  •  Just for fun (2+ / 0-)
    Recommended by:
    Rogneid, condoleaser

    Speaking of Turing; you prompted me do dig up and resuscitate an old blog post of mine about alternative computing.  

    It's kind of a book report on "The Difference Engine" by William Gibson and Bruce Sterling. The plot is nothing to brag about, but the world view is an interesting one. Suppose that Charles Babbage's mechanical computer had taken over in 1855 in the same way that vacuum tube and solid state circuits have during the last fifty years. The story runs with that, and adds some elements of environmental crisis and social breakdown to the picture.

    The computer terminology is instructive--
    A program is called a clacking sequence, and a programmer/operator is a clacker,
    The programs don't run, they spin,
    The computer itself is called an engine.
    The programming inputs are managed with punch cards, still familiar to a few of us, and remarkably like the operating inputs for the player pianos, spinning jennies, and other industrial equipment of the time. The engine operators have to take into account all the limitations of huge, complex, and delicate mechanical devices, and steam cars are still coming into their own, with the consequent degradation of the air quality in London by intense coal smoke.

    I don't know if I would recommend the book to anyone who isn't a William Gibson fan. He really likes to wallow in scenes of lowlife depravity.

    Just for fun, (and I hope one or more geeks will follow through and comment), I went through a WAG to compare a difference engine with modern
    computing capacity. Here it is:


    A byte is 8 binary digits (bits) plus an error bit, so round off and call it 10 bits/byte.

    A rotating element, say a clock-like gear, can process one bit per revolution, and the density of the gears is ten bits or one byte per cubic
    inch, including bearings, line shaft, levers and springs to transmit data.

    Torque required to run the gears is 0.1 inch-pounds per byte, or round up and call it 0.01 ft-lbs/ in3 = 17.28 ft- lb/ft3..

    Average density of clockwork is (0.5)(density of brass) = (0.5)(8.55 sg)(62.4 lb/ft3) = 266.8 lb/ft3

    So a cubic foot of mechanical data processing equipment at a nominal speed of, say, 1800 rpm could process(1728 in3/ft3)(1 byte/rev)(1800 r/m)/(60 sec/min) = 51,840 bytes/sec, call it 50 kb/s-ft3, at a power input of (17.28 ft-lb)(1800 rpm)(2*pi) /(33000 ft-lb/min/HP)  ~6 HP/ft3

    6 HP/cubic foot sounds way high to me, for several reasons. Wear, heat, and noise would be way out of line with that kind of power consumption, and
    clockworks intuitively seem to be way more efficient than that (still, we're talking about the equivalent of 17000+ gears/cubic foot, and a fairly high operating speed). Let’s stick with it, though, and see where it takes us.

    The limit on size for this computer is probably reached at the point where the accumulated shaft torque and backlash causes the gears to be fatally out of time. Based on this assumption, we could possibly go with much higher bit densities, like say, 10 bits/gear revolution. Then each cubic inch of gear train would provide up to 10 binary operations/revolution. The limit for information density would be torque and backlash in the gear trains--at ten bits/revolution, the maximum backlash + torque would be 0.05 revolution, or
    18 degrees throughout the machine. Once again, lets stick with a conservative estimate of ten bits, or one byte/revolution/cubic inch.

    The power would be have to be supplied by several parallel line shafts so that there is only a few feet of secondary shafting to provide power to each
    unit to limit the torque problems.

    Error checking and repairs need to be constant on this machine. So assume that there is an error check every revolution, and that a failed error check automatically drops the unit off-line for replacement. So the clackers are constantly patrolling for stopped units and replacing them, and the units have to be easily replaceable, and they should weigh less than about 100# each (and of course, everyone uses hearing protection in the vicinity of the machine).

    So each replaceable maintenance unit is about 1/3 ft3 or 90# of delicate clockworks. The height of the computer is limited to the height a person can
    reach to replace the units, so each level is about 7’ high, and there is a corridor between pairs of racks of computing units, so the overall density
    of the computer is about 50% of the gross volume, or 25 kbytes/sec-ft3, including corridors between the racks of computing elements. As we will see,
    some of this volume will be inside the rack, for water cooling and heat

    So with these conservative assumptions (50kb/s-ft3);
    Each rack is 20’ long, 7 feet high, 2’ thick, or 280 ft3 (about 75000#)altogether, and consumes 1680 HP to provide a computational rate of 7 e6 floating point operations/sec (7 MFLOPS). If I recall correctly, this is about equal to the power of the old 8088 chips that appeared in the first IBM PCs.

    Note that the heat generation would be way high (748 watts/HP* 6HP/ft3 = 4488 watts/ft3), so we need to allow for water cooling. That heat recovery would in turn reduce the heating load on the boilers.

    So, long story short, a mechanical CPU would be at least as big as a D8 Caterpillar, and require even more fuel to operate.  

    The book described machines that were orders of magnitude larger than my assumptions-- awesome to consider when you look at it this way--many
    thousands of horsepower equivalents of computing capacity, and all powered by steam.

    How many wrongs does it take to make a right?

    by pdknz on Sat Nov 10, 2007 at 12:46:48 PM PST

    •  what if one uses fluidic logic gates instead? n/t (0+ / 0-)

      Looking for intelligent energy policy alternatives? Try here.

      by alizard on Sat Nov 10, 2007 at 02:23:31 PM PST

      [ Parent ]

    •  Was the Babbage machine book (0+ / 0-)

      about a cult of secret world-changers, who, with the machine worked out things like "well if Lincoln continues to live then there will be a world war in the 1890s, and if he dies we can buy another 20 years to stop it..." kind of things?

      The one I refer to was a fun read, but I'm wondering if it was Gibson's.

      Until we break the corporate virtual monopoly on what we hear and see, we keep losing, don't matter what we do.

      by Jim P on Sat Nov 10, 2007 at 03:13:20 PM PST

      [ Parent ]

      •  Not that I recall (0+ / 0-)

        There was some speculation about what we have since called Total Information Awareness--the idea that the government would keep tabs on everyone and everything all the time.  I suppose that's inevitable, though, given that the technology allows it...

        How many wrongs does it take to make a right?

        by pdknz on Sat Nov 10, 2007 at 05:36:43 PM PST

        [ Parent ]

Subscribe or Donate to support Daily Kos.

Click here for the mobile view of the site