{"id":263,"date":"2007-01-05T13:08:13","date_gmt":"2007-01-05T13:08:13","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/01\/05\/turing-equivalent-vs-turing-complete\/"},"modified":"2007-01-05T13:08:13","modified_gmt":"2007-01-05T13:08:13","slug":"turing-equivalent-vs-turing-complete","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/01\/05\/turing-equivalent-vs-turing-complete\/","title":{"rendered":"Turing Equivalent vs. Turing Complete"},"content":{"rendered":"

In my discussion with Sal Cordova in this post<\/a>, one point came up which I thought was interesting, and worth taking the time to flesh out as a separate post. It’s about the distinction
\nbetween a Turing equivalent<\/em> computing system, and a Turing complete<\/em> computation. It’s true
\nthat in informal use, we often tend to muddy the line between these two related but distinct concepts. But in fact, they are distinct, and the difference between them can be extremely important. In some sense, it’s the difference between “capable of” and “requires”; another way of looking at it is
\n“sufficient” versus “necessary”.<\/p>\n

<\/p>\n

Let me start by giving you a definition of the two terms.<\/p>\n

A computing system<\/em> is called Turing equivalent<\/b> if it is capable of performing any
\ncomputation that can be performed on a Turing machine. Another term for a Turing equivalent computing
\nsystem is an effective computing system<\/b>. The importance of Turing equivalence comes down to the fact that computation has a fundamental limit; any Turing-equivalent\/effective computing system can
\nperform any<\/em> computation. There’s no computing device more powerful than a Turing machine – Turing machines and all other effective computing systems lie at the maximum point of capability of
\nmechanical computing devices.<\/p>\n

A computation<\/em> is Turing complete if it can only be computed by a Turing-equivalent computing
\nsystem. In fact, in the proper formal definition of Turing completeness, a computation C<\/em> is
\nTuring complete if and only if the fact that a given computing device φ can compute the result of
\nC<\/em> implies that φ can compute the result of any other Turing complete computation<\/em>.<\/p>\n

Why is this distinction so important?<\/p>\n

The biggest reason is because it turns out that being Turing equivalent is actually remarkably
\ntrivial. Intuitively, it seems like the maximum computation capability possible for a mechanical
\ncomputing device should be<\/em> hard to achieve. But it isn’t! As you can see by perusing the
\n
\narchives of the pathological programming language topic on this blog<\/a>, there are lots of ways of producing
\nTuring-equivalent computing systems, and many of them are incredibly simple. In fact, it’s pretty hard
\nto design a device capable of performing mechanical computations which is not<\/em>
\nTuring-equivalent. Almost any mechanical system that’s capable of performing any kind of computation
\nends up being Turing equivalent; it’s only by imposing deliberate restrictions on them that we generally achieve less than Turing-equivalent capabilities. The only part of Turing equivalence that’s
\ndifficult at all is unbounded storage; as long as you have the ability to perform anything like iteration or recursion, and you have some theoretically unbounded\/expandable storage, you’ve got
\na Turing-equivalent computing device.<\/p>\n

Turing-completeness, on the other hand, is a rarer beast. Most computations simply don’t<\/em> require the full capability of a Turing machine. There are a number of simpler classes of computing
\ndevices; linear-bounded automata, primitive recursive automata, finite-state automata, etc. Most of the computations that we encounter are actually computable by a member of one of those simpler classes of devices.<\/p>\n

To give a couple of concrete examples:<\/p>\n

    \n
  1. The common factorial function is primitive recursive. It does not<\/em> require Turing-equivalent computational capabilities to compute.<\/li>\n
  2. Searching a telephone book for a specific person to find their phone number is at worst
    \nlinear-bounded; it does not require a Turing-equivalent computing device.<\/li>\n
  3. Compiling a program in most programming languages does not<\/em> require Turing
    \nequivalent capabilities. (The language<\/em> may be capable of expressing Turing-complete
    \ncomputations, but the process of translating from the language to code for a specific
    \ncomputing device does not require Turing equivalent computation capabilities.)<\/li>\n<\/ol>\n

    The reason that this entered into my debate with Sal is because he, like many other people,
    \nconfused these two ideas. Because the DNA molecule can, in fact, perform Turing-complete computations,
    \nyou can view DNA (or, more generally, cell biochemistry) as a Turing-equivalent computing system. This
    \ndoes not<\/em> mean that cells require<\/em> Turing-equivalent computational capabilities.<\/p>\n

    My argument with Sal is basically that Sal claims that the fact that DNA is Turing-equivalent means that life requires<\/em> Turing-equivalent capabilities – which is another way of saying that some part<\/em> of the basic biochemical processes that make up life are equivalent to a
    \nTuring-complete<\/b> computation. But that is not<\/em> true – it’s an invalid implication. The fact that living things possess a component which is capable<\/em> of Turing-equivalent computation
    \ndoesn’t mean that living things require<\/em> Turing-equivalent computation.<\/em><\/p>\n

    To say that life contains DNA, which is a Turing-equivalent computing system, is saying that
    \nTuring equivalent computational capability is sufficient<\/em> for life. It is not<\/em> saying
    \nthat it is necessary<\/em> for life. The latter is a much<\/em> stronger claim, and requires
    \nmore evidence.<\/p>\n","protected":false},"excerpt":{"rendered":"

    In my discussion with Sal Cordova in this post, one point came up which I thought was interesting, and worth taking the time to flesh out as a separate post. It’s about the distinction between a Turing equivalent computing system, and a Turing complete computation. It’s true that in informal use, we often tend to […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[24,31,54],"tags":[],"class_list":["post-263","post","type-post","status-publish","format-standard","hentry","category-goodmath","category-intelligent-design","category-programming"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-4f","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/263","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=263"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/263\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=263"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=263"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=263"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}