Theory of Computation (CS 407)

2024 Spring
Faculty of Engineering and Natural Sciences
Computer Sci.& Eng.(CS)
3
6
Kemal İnan inan@sabanciuniv.edu,
Click here to view.
English
Undergraduate
CS302
Formal lecture,Interactive lecture,Recitation
Interactive,Communicative,Guided discovery
Click here to view.
Programs\Type Required Core Elective Area Elective
Computer Science and Engineering *
Computer Science and Engineering *
Electronics Engineering *
Electronics Engineering *
Industrial Engineering *
Industrial Engineering (Previous Name: Manufacturing Systems Engineering) *
Materials Science and Nano Engineering *
Materials Science and Nano Engineering (Previous Name: Materials Science and Engineering) *
Mechatronics Engineering *
Mechatronics Engineering *
Microelectronics *
Telecommunications *

CONTENT

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

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 OUTCOMES

  • 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

PROGRAMME OUTCOMES

1. Understand the world, their country, their society, as well as themselves and have awareness of ethical problems, social rights, values and responsibility to the self and to others. 2

2. Understand different disciplines from natural and social sciences to mathematics and art, and develop interdisciplinary approaches in thinking and practice. 3

3. Think critically, follow innovations and developments in science and technology, demonstrate personal and organizational entrepreneurship and engage in life-long learning in various subjects; have the ability to continue to educate him/herself. 3

4. Communicate effectively in Turkish and English by oral, written, graphical and technological means. 3

5. Take individual and team responsibility, function effectively and respectively as an individual and a member or a leader of a team; and have the skills to work effectively in multi-disciplinary teams. 1

1. Possess sufficient knowledge of mathematics, science, fundamental engineering, computational methods and program-specific engineering topics; use theoretical and applied knowledge of these areas in complex engineering problems. 4

2. Identify, define, formulate and solve complex engineering problems while considering the UN Sustainable Development Goals; choose and apply suitable analysis, design, estimation/prediction and modeling methods for this purpose. 3

3. Develop, choose and use modern techniques and tools that are needed for analysis and solution of complex problems faced in engineering applications; use information technologies effectively. 4

4. Have the ability to design a complex system, process, instrument or a product under realistic constraints and conditions, with the goal of fulfilling creative current and future requirements. 2

5. Use research methods, including conducting literature reviews, designing experiments, performing experiments, collecting data, analyzing results, and interpreting results, to investigate complex engineering problems or discipline-specific research topics. 2

6. Possess knowledge of business practices such as project management, risk management, change management, and economic feasibility analysis; awareness on entrepreneurship and innovation. 2

7. Possess knowledge of impact of engineering solutions on society, health and safety, the economy, sustainability, and the environment within the framework of the UN Sustainable Development Goals; awareness on legal outcomes of engineering solutions; awareness of acting impartially and inclusively without any form of discrimination; act in accordance with ethical principles, possessing knowledge of professional and ethical responsibilities. 1

8. Communicate effectively, both orally and in writing, on technical subjects, considering the diverse characteristics of the target audience (such as education, language, and profession). 2

ASSESSMENT METHODS and CRITERIA

  Percentage (%)
Final 30
Midterm 25
Quiz 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 :
Introduction to the Theory of Computation, Sipser, 1997 PWS
Computers and Intractability, Garey& Johnson, Freeman 2000