Page 1 Courtesy: Costas Busch / Jeff Ullman 1 CS-208 Theory of Computation Slides have been modified by Shaukat Wasi â€“ CS@DSU Page 2 Courtesy: Costas Busch / Jeff Ullman 1 CS-208 Theory of Computation Slides have been modified by Shaukat Wasi â€“ CS@DSU Human â€¢ A machine that â€“ recognizes one/multiple languages â€“ performs useful work when given instructions in the recognized language (s) â€“ has a capability of processing the instructions/input to â€¢ Solve a set of problems [NOT ALL Problems] Courtesy: Costas Busch / Jeff Ullman 2 Page 3 Courtesy: Costas Busch / Jeff Ullman 1 CS-208 Theory of Computation Slides have been modified by Shaukat Wasi â€“ CS@DSU Human â€¢ A machine that â€“ recognizes one/multiple languages â€“ performs useful work when given instructions in the recognized language (s) â€“ has a capability of processing the instructions/input to â€¢ Solve a set of problems [NOT ALL Problems] Courtesy: Costas Busch / Jeff Ullman 2 Human Capabilities â€¢ To judge the capabilities of humans (in general) with respect to: â€“ What problems can be solved by humans? â€¢ Canâ€™t experiments with all humansâ€¦ â€¢ We would like to develop an abstract model of humans â€“ Processing Model (Abstract Machine) [IPO] â€“ A set of problems Courtesy: Costas Busch / Jeff Ullman 3 Page 4 Courtesy: Costas Busch / Jeff Ullman 1 CS-208 Theory of Computation Slides have been modified by Shaukat Wasi â€“ CS@DSU Human â€¢ A machine that â€“ recognizes one/multiple languages â€“ performs useful work when given instructions in the recognized language (s) â€“ has a capability of processing the instructions/input to â€¢ Solve a set of problems [NOT ALL Problems] Courtesy: Costas Busch / Jeff Ullman 2 Human Capabilities â€¢ To judge the capabilities of humans (in general) with respect to: â€“ What problems can be solved by humans? â€¢ Canâ€™t experiments with all humansâ€¦ â€¢ We would like to develop an abstract model of humans â€“ Processing Model (Abstract Machine) [IPO] â€“ A set of problems Courtesy: Costas Busch / Jeff Ullman 3 Problems solvable by Humans â€¢ Recognition of a Language â€“ A Problem (itself) â€¢ Hence â€“ Language = Problem ? â€¢ Is language â€˜xâ€™ recognizable by the machine? â€¢ Is problem â€˜xâ€™ solvable by the machine? â€¢ We (in this course) will focus mainly on this simple Problem (w.r.t Computers) Courtesy: Costas Busch / Jeff Ullman 4 Page 5 Courtesy: Costas Busch / Jeff Ullman 1 CS-208 Theory of Computation Slides have been modified by Shaukat Wasi â€“ CS@DSU Human â€¢ A machine that â€“ recognizes one/multiple languages â€“ performs useful work when given instructions in the recognized language (s) â€“ has a capability of processing the instructions/input to â€¢ Solve a set of problems [NOT ALL Problems] Courtesy: Costas Busch / Jeff Ullman 2 Human Capabilities â€¢ To judge the capabilities of humans (in general) with respect to: â€“ What problems can be solved by humans? â€¢ Canâ€™t experiments with all humansâ€¦ â€¢ We would like to develop an abstract model of humans â€“ Processing Model (Abstract Machine) [IPO] â€“ A set of problems Courtesy: Costas Busch / Jeff Ullman 3 Problems solvable by Humans â€¢ Recognition of a Language â€“ A Problem (itself) â€¢ Hence â€“ Language = Problem ? â€¢ Is language â€˜xâ€™ recognizable by the machine? â€¢ Is problem â€˜xâ€™ solvable by the machine? â€¢ We (in this course) will focus mainly on this simple Problem (w.r.t Computers) Courtesy: Costas Busch / Jeff Ullman 4 Theory of Computation â€¢ Theory of computation is the branch that deals with how efficiently problems can be solved on a Model of Computation, using an Algorithm. â€¢ The field is divided into three major branches: â€“ Automata Theory and language , â€“ Computability Theory, â€“ Computational Complexity Theory [Efficiency], â€¢ Which are linked by the question: "What are the fundamental capabilities and limitations of computers?" Courtesy: Costas Busch / Jeff Ullman 5Read More

36 videos|39 docs|39 tests

### Proving Techniques

- Doc | 5 pages
### Recursive Function Theory

- Doc | 10 pages
### Computable and Non-Computable Functions

- Doc | 2 pages
### Introduction to Theory of Computation

- Video | 11:35 min
### Formal Representation of Languages

- Doc | 7 pages

- Introduction - Theory of Computation
- Doc | 1 pages