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