Introduction
I N C R E A S I N G C O M P L E X I T Y
Theory of Computation
Computability
Turing machines (1940s): -- The most general notion of computing -- The Church-Turing thesis -- Limits to computing: Uncomputable functions
factoring an integer into primes determining the shortest tour of given n cities
PART I
Sets, Relations, and Languages
Part I. Sets, Relations, and Languages
Verification of correctness of programs is hence impossible! (The woe of Microsoft!)
Complexity
Automata
Introduction
Theory of Computation
What problems can a computer solve? Computability
No one knows whether this terminates on on all inputs!
17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
Introduction
Theory of Computation
Computability
How fast can we compute a function? How much space do we require? • • • Polynomial time computable Non-det Poly Time (NP) Approximation, Randomization
- How fast can we solve a problem? - How little disk-space can we use to solve a problem
Automata
-What problems can we solve given really very little space? (constant space)
Restricted models: Finite automata Pushdown automata Context free grammars General models: Turing machine Variant Turing machines Church – Turing Thesis
Introduction
Basic questions:
What is an algorithm? What can and can’t be computed? When should an algorithm be considered practically feasible? What’s the basic capacity and the limit of computer?
Introduction
3 core domains:
Computability theory
Halting problem Tiling problem
What can and can not be computed? Some problems have no algorithms (we will prove this)
Complexity
What can we compute fast? -- Faster algorithms, polynomial time -- Problems that cannot be solved fast: * Cryptography What can we compute with very little space? -- Constant space (+stack) * String searching, language parsing, hardware verification, etc.
Automata
Introduction
I N C R E A S I N G C O M P L E X I T Y
Theory of Computation
Computability
Complexity
Automata
Automata: --- Foundations of computing --- Mathematical methods of argument --- Simple setting
Reference
Introduction to the theory of computation, Michael Sipser, Thomson, 1997. (中译本：计算理论导引， 张立昂，王捍贫，黄雄 译，机械工业出版社， 2000.2) 《可计算性与计算复杂性导引》，张立昂编著， 北京大学出版社，1997.1
Harry R. Lewis Christos H. Papadimitriou
Typos of Elements of the theory of computation
Text Book
Elements of the theory of computation （Second Edition）Harry R. Lewis,Christos H. Papadimitriou 《计算理论基础》，张立昂，刘田 译，清华大 学出版社，2000.7
How quickly can a problem be computed? Many problems probably have no efficient algorithms (no one knows how to prove this yet)
NP-hardness (= what can not be computed efficiently)
Automata
Introduction
Theory of Computation
Nondeterministic Weeks 15--16
Computability
Turing machines: Weeks 11--14
Complexity
Context-free languages: Weeks 7-10
Introduction
I N C R E A S I N G C O M P L E X I T Y
Theory of Computation
Computability
What can we compute? -- Most general notions of computability -- Uncomputable functions
Part I
CONTENTS
1. 2. 3. 4. 5. Introduction Sets, Relations, and Functions Finite Automata Context-free Languages Turing Machines Undecidablity
Authors of Elements of the theory of computation
The Theory of Computation 计算理论基础
主讲： 秦绪佳 教授 E-mail: qinxj@ qxj@ Office: 理学C501 电话：85290385 浙江工业大学 计算机学院
The Theory ofts
Set and its elements
Complexity
Motivation from mathematics: • Can we solve any mathematical question methodically? • Godel’s theorem: NO! • “Even the most powerful machines cannot solve some problems.”
Automata
Automata theory: Weeks 3 -6 Mathematical techniques: Week 1-2
Introduction
3 core domains:
Automata theory It discuss the definition & property of mathematical models.
Even checking whether a C-program will halt/terminate is not possible!
Complexity
Automata
input n; assume n>1; while (n !=1) { if (n is even) n := n/2; else n := 3*n+1; }
Introduction
Theory of Computation
What problems can a computer solve?
Not all problems!!!
Computability
Eg. Given a C-program, we cannot check if it will not crash!
Complexity
Automata
Functions that cannot be computed fast: • Applications to security • Encrypt fast, • Decryption cannot be done fast • RSA cryptography, web applications