This course is on the Theory of Computation<\/a>, which tries to answer the following questions:<\/p>\n Purpose of the Theory of Computation: Develop formal mathematical models of computation that reflect real-world computers.<\/em><\/p>\n This field of research was started by mathematicians and logicians in the 1930\u2019s, when they were trying to understand the meaning of a \u201ccomputation\u201d. A central question asked was whether all mathematical problems can be solved in a systematic way. The research that started in those days led to computers as we know them today.<\/p>\n Nowadays, the Theory of Computation can be divided into the following three areas: Complexity Theory<\/a>, Computability Theory<\/a>, and Automata Theory<\/a>.<\/p>\n The main question asked in this area is \u201cWhat makes some problems computationally hard and other problems easy?\u201d<\/p>\n Informally, a problem is called \u201ceasy\u201d, if it is efficiently solvable. Examples of \u201ceasy\u201d problems are (i) sorting a sequence of, say, 1,000,000 numbers, (ii) searching for a name in a telephone directory, and (iii) computing the fastest way to drive from Ottawa to Miami. On the other hand, a problem is called \u201chard\u201d, if it cannot be solved efficiently, or if we don\u2019t know whether it can be solved efficiently. Examples of \u201chard\u201d problems are (i) time table scheduling for all courses at Carleton, (ii) factoring a 300-digit integer into its prime factors, and (iii) computing a layout for chips in VLSI.<\/p>\n Central Question in Complexity Theory: Classify problems according to their degree of \u201cdifficulty\u201d. Give a rigorous proof that problems that seem to be \u201chard\u201d are really \u201chard\u201d.<\/em><\/p>\n In the 1930\u2019s, Go\u0308del, Turing, and Church discovered that some of the fundamental mathematical problems cannot be solved by a \u201ccomputer\u201d. (This may sound strange, because computers were invented only in the 1940\u2019s). An example of such a problem is \u201cIs an arbitrary mathematical statement true or false?\u201d To attack such a problem, we need formal definitions of the notions of<\/p>\n The theoretical models that were proposed in order to understand solvable and unsolvable problems led to the development of real computers.<\/p>\n Central Question in Computability Theory: Classify problems as being solvable or unsolvable.<\/em><\/p>\n Automata Theory deals with definitions and properties of different types of \u201ccomputation models\u201d. Examples of such models are:<\/p>\n Central Question in Automata Theory: Do these models have the same power, or can one model solve more problems than the other?<\/em><\/p>\n In this course, we will study the last two areas in reverse order: We will start with Automata Theory, followed by Computability Theory. The first area, Complexity Theory, will be covered in COMP 3804.<\/p>\n Actually, before we start, we will review some mathematical proof techniques. As you may guess, this is a fairly theoretical course, with lots of definitions, theorems, and proofs. You may guess this course is fun stuff for math lovers, but boring and irrelevant for others. You guessed it wrong, and here are the reasons:<\/p>\n Where does this course fit in the Computer Science Curriculum at Carleton University? It is a theory course that is the third part in the series COMP 1805, COMP 2804, COMP 3803, COMP 3804, and COMP 4804. This course also widens your understanding of computers and will influence other courses including Compilers, Programming Languages, and Artificial Intelligence.<\/p>\n","protected":false},"excerpt":{"rendered":"\n
1.1.1 Complexity theory<\/h4>\n
1.1.2 Computability theory<\/h4>\n
\n
1.1.3 Automata theory<\/h4>\n
\n
1.1.4 This course<\/h4>\n
\n