Turing machines; recursive numbers and turing computability; solvability and unsolvable problems; concepts of and results on computational complexity; some NP complete problems

### Theory of Computation (CS 503)

__here__to view.

__here__to view.

Programs\Type | Required | Core Elective | Area Elective |

MA-European Studies | |||

MA-European Studies-Non Thesis | |||

MA-Political Science | |||

MA-Political Science-Non Thes | |||

MA-Visual Arts&Vis. Com Des-NT | |||

MA-Visual Arts&Visual Com Des | |||

MS-Bio. Sci. & Bioeng. LFI | |||

MS-Bio. Sci. & Bioeng. LFI-ENG | |||

MS-Biological Sci&Bioeng. | * | ||

MS-Business Analytics | |||

MS-Computer Sci.&Eng. LFI | |||

MS-Computer Sci.&Eng. LFI-ENG | |||

MS-Computer Science and Eng. | * | ||

MS-Cyber Security(with thesis) | * | ||

MS-Data Science | |||

MS-Elec. Eng&Comp Sc.LFI-ENG | |||

MS-Electronics Eng&Comp Sc.LFI | |||

MS-Electronics Eng&Computer Sc | * | ||

MS-Electronics Eng. | * | ||

MS-Electronics Eng. LFI | |||

MS-Electronics Eng. LFI-ENG | |||

MS-Energy Techno.&Man. | * | ||

MS-Industrial Eng. LFI-ENG | |||

MS-Industrial Engineering | * | ||

MS-Industrial Engineering LFI | |||

MS-Manufacturing Eng-Non Thes | * | ||

MS-Manufacturing Engineering | * | ||

MS-Materials Sci & Engineering | * | ||

MS-Materials Sci. & Eng. LFI | |||

MS-Materials Sci.&Eng. LFI-ENG | |||

MS-Mathematics | |||

MS-Mechatronics | * | ||

MS-Mechatronics LFI | |||

MS-Mechatronics LFI-ENG | |||

MS-Physics | |||

MS-Physics-Non Thesis | * | ||

MS-Psychology | |||

MS-Psychology-Non Thesis | |||

PHD-Biological Sci&Bioeng. | * | ||

PHD-Comp. Sci and Eng.after UG | * | ||

PHD-Computer Science and Eng. | * | ||

PHD-Cyber Security | * | ||

PHD-Electronics Eng&ComputerSc | * | ||

PHD-Electronics Eng. | * | ||

PHD-Electronics Eng. after UG | * | ||

PHD-Experimental Psychology | |||

PHD-Industrial Engineering | * | ||

PHD-Management | |||

PHD-Manufacturing Eng after UG | * | ||

PHD-Manufacturing Engineering | * | ||

PHD-Materials Sci.&Engineering | * | ||

PHD-Mathematics | |||

PHD-Mechatronics | * | ||

PHD-Mechatronics after UG | * | ||

PHD-Physics | |||

PHD-Physics after UG | |||

PHD-Social Psychology | |||

PHDBIO after UG | * | ||

PHDCYSEC after UG | * | ||

PHDEECS after UG | * | ||

PHDEPSY after UG | |||

PHDIE after UG | * | ||

PHDMAN after UG | |||

PHDMAN after UG-Finance | |||

PHDMAN after UG-Man. and Org. | |||

PHDMAN after UG-Op.&Sup. Cha. | |||

PHDMAN-Finance Area | |||

PHDMAN-Man. and Org. Area | |||

PHDMAN-Op. & Supp. Chain Area | |||

PHDMAT after UG | * | ||

PHDMATH after UG | |||

PHDSPSY after UG |

### CONTENT

### OBJECTIVE

To introduce the foundations of computations in terms of the hierarchy of expressibility of languages culminating with the Turing Machine ; the equivalences between different computational mechanisms as a warm-up to the Church-Turing thesis ; the theoretical limits of computation in terms of decidability and semidecidability of problems starting with the halting problem of a TM and computability of functions ; the practical limits to computation in terms of the tractability of problems , that is, the growth of necessary time and space resources as a function of the size of the problem instances ; recursion theorem as the critical and possibly the only link between existing human-made technologies and self-reproducing biological mechanisms.

### LEARNING OUTCOME

Upon completion of the course, student should be able to :

Construct deterministic and nondeterministic Turing Machines and their multitape and other variants by using compositional techniques for formulating and solving decision problems of practical or theoretical significance

Demonstrate the equivalence between different computational tools such as different variants of the Turing Machines using concepts of decidability and semidecidability

Use random access machines (RAMs) and generalized grammars (or rewriting systems) as yet other tools of computation that are equivalent to the TM.

Demonstrate the fact that all multivariable functions on integers (primitive recursive functions) can be derived from simple functions by repeated use of composition and recursion

Demonstrate that not all reasonably computable functions are recursive and extend this set to mu-recursive functions by introducing the minimalizable functions

Show that the computational power of generalized grammars, mu-recursive functions and Turing machines are identical

Understand and use the concept of a Universal Turing Machine (UTM) and compute a concrete version of it using either the classical 3-tape model or a RAM

Demonstrate the undecidability of the famous halting problem for TMs and using Turing-computable reductions generate a host of undecidable and un-semidecidable problems

Understand the significance of the busy-beaver problem as an example of the intuitively difficult concept of an uncomputable function

Show that a computer program can use its own definition within its program in a recursive manner by using the recursion theorem and apply this idea to a number of novel decidability problems

Formulate problems of computational complexity and use the associated tools to categorize a problem to be in the polynomial (P), nondeterministic polynomial (NP) , NP-complete or NP-hard class

Generate the starting branches of the tree of NP-complete problems by using polynomial reductions after establishing the SAT problem as the root of this tree using Cook's Theorem where the nodes involved in this tree are the well-known NP-complete problems like the Hamiltonian Cycle , Traveling Salesman and others

Extend the computational time complexity problem to space complexity and formulate some game-theoretic problems that are P-space complete

### Update Date:

### ASSESSMENT METHODS and CRITERIA

Percentage (%) | |

Final | 30 |

Midterm | 25 |

Exam | 35 |

Homework | 10 |

### RECOMENDED or REQUIRED READINGS

Textbook |
MAIN TEXT: Elements of the Theory of Computation, Lewis & Papadimitrious, Prentice Hall 1998 (out of print and discontinued) |

Readings |
AUXILIARY TEXTS : |