School of Computer Science, Tel Aviv University 

Fall 2004-2005

Computational Models

(or more accurately - introduction to the theory of computation)



Mondays 13:00-16:00, Dach Lecture Hall

Lecturer: Benny Chor

Teaching Assistant: Gadi Kimmel



 Solutions to Moed A Exam  (scanned, 5MB)

Moed A Grades   Moed B Grades


(Remark: Same factor applied to Moed A and B)

Contact Info:






Office Hours


Prof. Benny Chor


Schreiber  223

By  e-appointment

Teaching Assistant

Dr. Gad Kimmel


Schreiber  011

By  e-appointment 

Grader (Bodek)

Alexander Medvedovsky


 Mail Box 400

By  e-appointment



Course Outline

The course deals with fundamental questions of computer science:

  • What is a computer ?
  • What can computers do (and what can they not do)?
  • Why are some problems computationally hard, while very similar ones are computationally easy?


These questions were mostly raised during the 20th century, and they accompanied and guided the actual development of computers.
Many of these and related questions were resolved, but some (especially those dealing with computational hardness) retained their status
as "key open problems" into the 21st century.


The course is a required course for Computer Science students, and "extended intro to Computer Science" is a prerequisite.
Students from other disciplines are encouraged to contact the instructor.

Course Requirements and Important Dates:

  • 6 homework assignments. (Best 5 out of 6 will be part of the grade. Only parts of each assignment will be graded.)
  • Midterm exam: Friday, Nov. 26. Material: Lectures 1-5, Chapters 0 to 2. Grades.
  • Final exam. Closed book except for 4 double-sided pages of your choice.

Course Timetable (schedule and material of future lectures are tentative):

The course consists roughly of three parts:  Lectures 1-5 deal with languages and automata theory, lectures 5-10 with computability theory, and lectures 11-14 with complexity theory.









 Administrativia and introduction.  Mathematical terminology.  Finite automata and regular languages - examples.

 Chapter 0.
 Chapter 1, Section 1.1




Nondeterminism finite state automata; Regular expressions;
Equivalence of regular languages and regular expressions.

Chapter 1, Sections 1.1-1.3




The pumping lemma. Non regular languages.
Context free grammars. Chomsky normal form.

Chapter 1 and 2, Sections 1.4, 2.1, 2.2

Additional closure properties of regular languages



Push down automata. NonDeterminism adds power to PDAs. Equivalence of PDAs and CFGs. Pumping lemma for context free languages.

Chapter 2, Sections 2.2-2.3

Examples: Pumping lemma for (non) regular languages.  CFL~PDA



NonDeterminism adds power to PDAs (revised); Closure properties of CFLs; Algorithmic Aspects of PDAs and CFLs. Turing machines.

Chapter 2, Sections 2.2-2.3. Chapter 3, Section 3.1

Examples: Pumping  lemma for PDAs.



Turing machines. Algorithms. Multi-Tape TMs; RAMs; Nondeterministic TMs.  Church-Turing thesis. 
Printer friendlier version.

Chapter 3, Sections 3.1-3.3

More TM examples.
TM with two sided infinite tape.



Hilbert's tenth problem.  Encodings. Universal TM. Diagonalization.Proof of undecidability of the halting problem by diagonalization.
Printer friendlier version.

Chapter 3, Section 3.3,

Chapter 4, Sections 4.1-4.2

More TM examples.
Addition on TM.



Computable functions. Reductions. Proofs of undecidability via reductions by computation histories and by mapping reductions.

Printer friendlier version.

Chapter 5, Sections 5.1, 5.3 




Rice Theorem. Kolmogorov Complexity. RE completeness.
Turing reductions. Godel incompleteness theorem.

Printer friendlier version.

Chapter 6, 6.2, 6.3, 6.4.








Undecidable tiling, or domino,  problems

(old fashioned chalk dust presentation)
 Recursion theorem  (printable version)

 Unrestricted Grammars - David Galles slides (printable version)

Chapter 5, 5.2


Chapter 6, 6.1

Rice Theorem


Kolmogorov complexity



Time complexity – introduction. DTIME and NTIME.

Time dependence on models. The class P.  (printable version)

 Chapter 7, Sections 
  7.1- 7.2

The Recursion Theorem




The class NP.  Polynomial time Reductions. NP completeness, Cook-Levin theorem: SAT is NP-complete.
(printable version)

 Chapter 7, Sections   

Additonal languages in NP




Additional Reductions (IP, HamPath, Bounded Tiling).
On search vs. decision problems. Approximation Algorithms.   (printable version)

Reduction from 3SAT to Hamiltonian path (a separate ps file)

 Chapter 7, Sections   
Chapter 10, Section 10.1

Additional reductions:
3 coloring and set cover
are NP complete



Approaches to dealing with computational intractability:
1) fixed parameter algorithms, 2) randomization.
(13MB file!).  (printable version)

Chapter 10, Section 10.2.                          The view from Mars

Review of course material.

Presentations are based on those prepared by Prof. Maurice Herlihy for a similar course given at Brown University.

Problem Sets

Problem Set 1 -  Published Oct. 18, due Nov. 9, 2004.   Partial solution.

Problem Set 2 -  Published Nov. 9, due Nov. 23, 2004.   Partial solution.

Problem Set 3 -  Published Dec. 1, due Dec. 16, 2004.   Partial solution.              

Problem Set 4 -  Published Dec. 17, due Dec. 30, 2004.  Partial solution. 

Problem Set 5 -  Published Jan. 6, due Jan. 20, 2005.   Complete solution.


Early Printer Friendly Handouts  (courtesy of  Haim Tavor).


Each week (including 1st week) there will be a 3 hours lecture, preceeded by a 1 hour recitation. There will be 6 homework problems.  Homework submission is in singles only (no pairs, triplets, quartets, quintets etc.). External sources (books, journal articles, web pages) can be used but should be clearly quoted. Assignments due two weeks after publishing. Grading will apply to part of the problems in each assignment.   Solving assignments independently is key to understanding the material and to success in exams, and is strongly encouraged. Research done at the Technion shows that outright copying may be harmful to your health.


Grade:  10-15% based on homework assignments, 20-25% based on midterm, 60-70% on final exam. Midterm component weighted only if it contributes  non-negatively to final outcome.



 Introduction to the Theory of Computation, M. Sipser PWS Publishing Co.,  1997.


Reference Books

  • Computational Complexity, C. Papadimitriou, Addison-Wesley Publishing Co.,  1994.
  • Elements of the Theory of Computation, H. Lewis and C. Papadimitriou, Prentice-Hall, 1981.
  • Introduction to Automata Theory, Languages, and Computation, J. Hopcroft and J. Ullman, Addison-Wesley Publishing Co., 1979.


Other On-line Resources

Last year course
David Galles course at USF:

Exams from previous years (and previous instructors) in Tel-Aviv Univ.  This includes Fall 2003/4 exams from my last year's course.
Mid-term exams from previous years (and previous instructors) in Tel-Aviv Univ.
A virtual Turing machine you can possibly run


Other Interesting On-line Resources