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 407)

__here__to view.

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

BA- Political Science | |||

BA-Cultural Studies | |||

BA-Cultural Studies | |||

BA-Economics | |||

BA-Economics | |||

BA-International Studies | |||

BA-International Studies | |||

BA-Management | |||

BA-Management | |||

BA-Political Sci.&Inter.Relat. | |||

BA-Social & Political Sciences | |||

BA-Visual Arts&Visual Com.Des. | |||

BA-Visual Arts&Visual Com.Des. | |||

BS-Biological Sci.&Bioeng. | |||

BS-Computer Science & Eng. | * | ||

BS-Computer Science & Eng. | * | ||

BS-Electronics Engineering | * | ||

BS-Electronics Engineering | * | ||

BS-Industrial Engineering | * | ||

BS-Manufacturing Systems Eng. | * | ||

BS-Materials Sci. & Nano Eng. | * | ||

BS-Materials Science & Eng. | * | ||

BS-Mechatronics | * | ||

BS-Mechatronics | * | ||

BS-Microelectronics | |||

BS-Molecular Bio.Gen.&Bioeng | |||

BS-Telecommunications | * |

### 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

### 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. 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 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; choose and apply suitable analysis 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; possess knowledge of standards used in engineering applications; use information technologies effectively. 4

**4.** Ability to design a complex system, process, instrument or a product under realistic constraints and conditions, with the goal of fulfilling specified needs; apply modern design techniques for this purpose. 2

**5.** Design and conduct experiments, collect data, analyze and interpret the results to investigate complex engineering problems or program-specific research areas. 2

**6.** Knowledge of business practices such as project management, risk management and change management; awareness on innovation; knowledge of sustainable development. 2

**7.** Knowledge of impact of engineering solutions in a global, economic, environmental, health and societal context; knowledge of contemporary issues; awareness on legal outcomes of engineering solutions; understanding of professional and ethical responsibility. 1

**1.** Design, implement, test, and evaluate a computer system, component, or algorithm to meet desired needs and to solve a computational problem. 5

**2.** Demonstrate knowledge of discrete mathematics and data structures. 5

**3.** Demonstrate knowledge of probability and statistics, including applications appropriate to computer science and engineering. 2

**1.** Applying fundamental and advanced knowledge of natural sciences as well as engineering principles to develop and design new materials and establish the relation between internal structure and physical properties using experimental, computational and theoretical tools. 1

**2.** Merging the existing knowledge on physical properties, design limits and fabrication methods in materials selection for a particular application or to resolve material performance related problems. 1

**3.** Predicting and understanding the behavior of a material under use in a specific environment knowing the internal structure or vice versa. 1

**1.** Familiarity with concepts in statistics and optimization, knowledge in basic differential and integral calculus, linear algebra, differential equations, complex variables, multi-variable calculus, as well as physics and computer science, and ability to use this knowledge in modeling, design and analysis of complex dynamical systems containing hardware and software components. 4

**2.** Ability to work in design, implementation and integration of engineering applications, such as electronic, mechanical, electromechanical, control and computer systems that contain software and hardware components, including sensors, actuators and controllers. 3

**1.** Use mathematics (including derivative and integral calculations, probability and statistics, differential equations, linear algebra, complex variables and discrete mathematics), basic sciences, computer and programming, and electronics engineering knowledge to
(a) Design and analyze complex electronic circuits, instruments, software and electronics systems with hardware/software.
or
(b) Design and analyze communication networks and systems, signal processing algorithms or software 4

**1.** Formulate and analyze problems in complex manufacturing and service systems by comprehending and applying the basic tools of industrial engineering such as modeling and optimization, stochastics, statistics. 2

**2.** Design and develop appropriate analytical solution strategies for problems in integrated production and service systems involving human capital, materials, information, equipment, and energy. 1

**3.** Implement solution strategies on a computer platform for decision-support purposes by employing effective computational and experimental tools. 3

### 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 : |