{"id":1306,"date":"2011-02-06T20:50:59","date_gmt":"2011-02-07T01:50:59","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/?p=1306"},"modified":"2011-02-06T20:50:59","modified_gmt":"2011-02-07T01:50:59","slug":"computability","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2011\/02\/06\/computability\/","title":{"rendered":"Computability"},"content":{"rendered":"

I just recently realized that I only wrote about computability back in the earliest days of this blog. Those posts have never been re-run, and they only exist back on the original blogger site. When I wrote them, I was very new to blogging – looking back, I think I can do a much better job now. So I’m going to re-do that topic. This isn’t just going to be a re-post of those early articles, but a complete rewrite.<\/p>\n

The way that I’m going to cover this is loosely based on the way that it was first taught to me by a wonderful professor, Dr. Eric Allender at Rutgers, where I went to college. Dr. Allender was a really tremendous professor: he managed to take an area of computer science that could seem hopelessly abstract and abstruse, and turned it into something fun and even exciting to learn about.<\/p>\n

Computability is the most basic and fundamental sub-field of theoretical computer science. It’s the study of what a mechanical computing device can do. Not just what a specific mechanical computing device can do, but what can any<\/em> mechanical computing device do? What are the limits of what you can do mechanically? And once we know the limits, what can we discover about the nature of computation?<\/p>\n

<\/p>\n

The study of computability has its roots in mathematical logic. The earliest study of computability was done by logicians that were looking at proofs and provability. The connection there is one of the things that fascinates me: from the outside, why on earth would things like the Principia Mathematica, which attempted to completely formalize mathematics from first principles, be connected to the theory of how the computer that I’m typing this article on? Once you understand what’s going on, it becomes almost obvious<\/em>!<\/p>\n

In logic, the process of proof is completely mechanical. You have a set of statements, and a set of inference rules. The inference rules allow you to use the initial statements to produce new statements. The sequence of inference steps that lead to the production of a particular new statement is a proof of that statement. The important thing about logic is that the inference rules are mechanical<\/em>: you don’t need to know what a statement means<\/em> to be able to use it in a proof. The inference rules just describe a syntactic structure in the statements, and tells you what you can produce if you can find an instance of that structure.<\/p>\n

For example, one of the classic rules of inference is: given two statements, A(x) and forall y: A(y) rightarrow B(y), you can infer B(x). (Note: a typo in the previous sentence was corrected after being pointed out by commenters.)<\/em> A could be any<\/em> predicate at all. It could be “IsBig”, or “IsBlue”, or “Simple”, or “Less than 8”, or “Is cute”. x could be any object: it could be a person, or it could be a crayon, or it could be an abstract set. It doesn’t matter.<\/p>\n

So you can view the process of proof as computation. And we do. The rallying cry of functional programmers is: “The program is the proof”, because a functional program can be read as a (very complicated) proof; and the type system that’s used to analyze the program is<\/em> a very simple proof.<\/p>\n

Anyway, the way that we talk about computability takes a lot from logic. <\/p>\n

You can describe the basics of computability in a few different ways. You can take the very strict logical route; you can take the recursive function theory route; or you can take the automata route. I like to follow the basic way that Prof. Allender taught me, which is the automata version. I like this approach, because as we’ll see, it gives you an almost tactile sense of the differences between the different classes of computability.<\/p>\n

One of the many legacies of the logical roots of computability is that we talk about it in terms of languages<\/em>. We could just as easily talk in terms of functions<\/em> (which is the way that the recursive function theory approach does it), but the logicians that built the foundations worked in terms of languages.<\/p>\n

Given a computational problem, you can express it as a language; and you can express solving that problem as determining whether or not a given string is a member of that language. That sounds very abstract – so let’s take an example.<\/p>\n

Suppose that the problem we want to solve is adding two numbers. Then we can describe it as a language consisting of sentences “x+y=z”, where a sentence is a member of the language if and only if the sum of x and y is z. So “1+2=3” and “27+42=69” are valid strings in the language, but “19+18=54” and “2+4” are not. (“2+4” because it doesn’t even have the right structure.)<\/p>\n

Any formal language can be described using something called a phrase structure grammar<\/em> or Chomsky grammar<\/em> (after Noam Chomsky – yes, that<\/em> Noam Chomsky, who is a brilliant logician\/linguist as well as a political gadfly.). That means that any computation can be described as a grammar – which is, in itself, pretty amazing – but we’ll get to that in a future post.<\/p>\n

A Chomsky grammar consists of four elements:<\/p>\n

    \n
  1. A set of terminal symbols<\/em> (also called characters<\/em>). This set is called the grammar’s alphabet<\/em>. All strings in the language will consist of sequences of terminal symbols.<\/li>\n
  2. A set of non-terminal symbols<\/em> (NTSs). <\/li>\n
  3. One distinguished member of the set of NTSs, called the start symbol<\/em>.<\/li>\n
  4. A collection of replacement rules<\/em> (also called productions<\/em>). Each replacement rule consists of a left-hand-side and a right-hand-side. The right hand side is a sequence of mixed terminals and non-terminal symbols, or \t\tthe empty string (which is written epsilon).<\/li>\n<\/ol>\n

    It’s easiest to explain how this works with an example. We can \tdefine a language that consists of sequences of any number of \t“1”s followed by at least one “2”:<\/p>\n

      \n
    • Terminals: {1, 2}.<\/li>\n
    • Non-terminals: {S, A, B}<\/li>\n
    • Start: S<\/li>\n
    • Productions:\n
        \n
      1. S rightarrow A B<\/li>\n
      2. A rightarrow 1 A<\/li>\n
      3. A rightarrow epsilon<\/li>\n
      4. B rightarrow 2 B<\/li>\n
      5. B rightarrow 2<\/li>\n<\/ol>\n<\/li>\n<\/ul>\n

        So what this says is: you to produce a string in this language, you start with S. Then you do whatever productions you want, until you have a\tstring of all terminals, and then you stop. <\/p>\n

        So you could produce the string “112222”:<\/p>\n

          \n
        1. S <\/li>\n
        2. AB (Rule 1, replacing S by AB.)<\/li>\n
        3. 1AB$ (rule 2, replacing A by 1A.)<\/li>\n
        4. 11AB (rule 2, again)<\/li>\n
        5. 11B (rule 3, replacing A with the empty string)<\/li>\n
        6. 112B (rule 4, repcaing B by 2B.)<\/li>\n
        7. 1122B (rule 4 again)<\/li>\n
        8. 11222B (rule 4 again)<\/li>\n
        9. 112222 (rule 5, replacing B with 2.)<\/li>\n<\/ol>\n

          Another example, is considerably more complex computationally, is paren matching. It produces strings that have the same number of open and close parens – but not just N opens followed by N closes – any sequence of opens \tand closes, as long as it ends up matching.<\/p>\n

            \n
          • Terminals: {(, )}.<\/li>\n
          • Non-terminals: { S }<\/li>\n
          • Start: S<\/li>\n
          • Productions:\n
              \n
            1. S rightarrow S S\n
            2. S rightarrow (S)\n
            3. S rightarrow epsilon<\/li>\n<\/ol>\n<\/li>\n<\/ul>\n

              For an example of this, we can generate the string “(()(()()))”:<\/p>\n

                \n
              1. S<\/li>\n
              2. (S) (rule 2)<\/li>\n
              3. (SS) (rule 1)<\/li>\n
              4. ((S)S) (rule 2)<\/li>\n
              5. (()S) (rule 3)<\/li>\n
              6. (()(S)) (rule 2)<\/li>\n
              7. (()(SS)) (rule 1)<\/li>\n
              8. (()((S)S)) (rule 2)<\/li>\n
              9. (()(()S)) (rule 3)<\/li>\n
              10. (()(()(S))) (rule 2)<\/li>\n
              11. (()(()())) (rule 3)<\/li>\n<\/ol>\n

                In computability theory, we talk about four general classes of computability – and those four classes can each be expressed by using different restrictions on the structure of production rules in Chomsky grammars. They’re typically talked about in terms of a hierarchy defined by Chomsky:<\/p>\n

                \n
                Level 3: the regular languages<\/dt>\n
                These are very simple languages, which can’t do anything particularly interesting: no counting, nothing beyond sequencing and repetition. Regular languages can be recognized by a simple kind of machine called a finite state automaton.<\/dd>\n
                Level 2: the context free languages (CFLs)<\/dt>\n
                These are widely used in practical computer science. They’re reasonably expressive; you can do a limited kind of counting with them, but nothing too deep. CFLs can be recognized by a machine called a push-down automaton.<\/dd>\n
                Level 1: the context sensitive languages (CSLs)<\/dt>\n
                Context sensitive languages are the things that can be written a more advanced kind of grammar. You can express a lot of quite deep computation using CSLs. CSLs can be recognized by a very interesting machine: a linear-bounded tape non-deterministic turing machine. Level 1 includes most things that we can really compute: the linear-bounding non-deterministic machine is a pretty good match for the capability of a real computer; level 0 conceptually requires infinite memory.<\/dd>\n
                Level 0: the recursively enumerable languages.<\/dt>\n
                Anything computable. Level 0 languages are languages which can be accepted<\/em> by a regular, unbounded turing machine.<\/dd>\n<\/dl>\n

                The Chomsky hierarchy is traditional, but it’s not perfect. There are a couple of things missing in it; there are some things between level 0 and level 1 in the Chomsky hierarchy.<\/p>\n

                There’s also one little cheat in the definition above about level 0. I said that level 0 is equivalent to Turing machines that can accept<\/em> an input. When you get to a machine as sophisticated as a Turing machine, it can do one of two things on a given input: it can accept the input, or it can decide about the input.<\/p>\n

                Accepting the input means that if the input is a member of the language, it will eventually stop and say “Yes, this is in my language”. Deciding about the input means that that the machine will eventually stop and say either “Yes, this is in my language”, or “No, this is not in my language”. The difference is that an accepting machine does not<\/em> stop if the string is not<\/em> in the language. It might be able to stop and say no sometimes, but there is no guarantee. So it will say “Yes” if the string is in the language; it will not<\/em> say no if the string is not in the language. The set of languages that’s acceptable by a Turing machine are called the Chomsky level-0 languages; the languages decidable<\/em> by a Turing machine are called the recursive<\/em> languages.<\/p>\n

                In the next couple of posts, we’ll look at the grammars and corresponding computing machines for the Chomsky levels. Then we’ll use that as a launching pad for exploring more about computability.<\/p>\n","protected":false},"excerpt":{"rendered":"

                I just recently realized that I only wrote about computability back in the earliest days of this blog. Those posts have never been re-run, and they only exist back on the original blogger site. When I wrote them, I was very new to blogging – looking back, I think I can do a much better […]<\/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":[94,79],"tags":[107,123,131,172,193],"class_list":["post-1306","post","type-post","status-publish","format-standard","hentry","category-computability","category-computation","tag-automata","tag-chomsky","tag-computability-2","tag-grammar","tag-logic-2"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-l4","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/1306","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=1306"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/1306\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=1306"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=1306"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=1306"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}