TCS-TR-B-07-2

Date: Wed Aug 15 05:23:06 2007

Title: Course Notes on Theory of Computation

Authors: Thomas Zeugmann

Contact:

First name: Thomas
Last name: Zeugmann
Address: Division of Computer Science, Hokkaido University, N-14, W-9, Sapporo 060-0814, Japan
Email: thomas@ist.hokudai.ac.jp

Abstract. The main purpose of this course is an introductory study of the formal relationships between machines, languages and grammars. The course covers regular languages, context-free languages and touches context-sensitive languages as well as recursive and recursively enumerable languages. Relations to and applications in UNIX are discussed, too.

Moreover, we provide a framework to study the most general models of computation. These models comprise Turing machines and partial recursive functions. This allows us to reason precisely about computation and to prove mathematical theorems about its capabilities and limitations. In particular, we present the universal Turing machine which enables us to think about the capabilities of computers in a technology-independent manner.