THEORY OF COMPUTATION
Syllabus for the course CS 5315/6315, Spring 2021

Class time: TR 1:30-2:50 pm

Class mode: online

Instructor: Vladik Kreinovich, email vladik@utep.edu, office CCSB 3.0404,
office phone (915) 747-6951.

Prerequisite: CS 3350 (Automata)

Main Objectives:

Contents

  1. Turing's snakelike machine: not very fancy, but it can compute anything (you just wait and wait and wait, ...). Finally: something purely theoretical (and not real machines): recursive functions. Church's bold statement: if anyone can compute anything on any machine, I can compute it on a Turing snake! Universal Turing machine. Can anyone really beat Church? We'll discuss the attempts (Gandi, Kreisel, etc) if time allows.
  2. You are accustomed to the fact that everything is computable, and if your program does not work, that means a bad grade. Finally! Only in this course! Computational problems that cannot be solved! (and so you get a bad grade, if your program solves them - just kidding).
  3. If a program requires a billion years to finish its computations, only a crazy theoretician can call it an algorithm. So, to sound more reasonable, we will talk about computational complexity, realistic (polynomial-time) computations, P and NP, NC, limitations on space and on the number of processors, etc. "P=NP?" as a challenge to mankind. Will science ever stop? Again, we will find here lots of undecidability results. And maybe, as a project, you will be able to prove that some problem that you were planning to solve is undecidable.
  4. What to do if your problem turned out to be undecidable? For sure: not to give up. It can be still decidable in some sense: for almost all cases, by a Monte-Carlo algorithm that gives an answer with probability close to 1, etc. Few results and lots of open problems.
  5. Turing machine was invented in the 30s, P=NP problem appeared when many of you guys were too young to count. What is the modern state of the Theory of Computation? We'll try to cover briefly:

Learning Outcomes

1. Knowledge and Comprehension

a. Describe the practical need for theory of computing: to know which computational problems are solvable and which are not, and which problems can be, in principle, solved within given computation time, to avoid wasting resources on trying to solve problems in such a general context that they become unsolvable

b. Describe different models of computing, including recursive functions, different versions of Turing machine, etc.

c. Describe how computability in a programming language is related to formal models of computing, on the example of primitive recursive and recursive functions

d. Understand Church-Turing thesis and understand the status of this thesis - that it is, in effect, a statement about the physical world

e. Define decidable and recursively enumerable (r.e., semi-decidable) sets

f. Understand the notion of an oracle and of computing relative to an oracle

g. Define classes P, NP, the notions of polynomial time reduction, NP-hardness, and NP-completeness; understand the motivations behind these definitions: P means feasible, NP stands for a problem; understand the difference between the formal notion of polynomial time and the practical notion of feasibility

i. Understand the difference between a proof and a sequence of reasonable arguments which does not constitute a proof

j. Know several NP-hard problems

k. Define complexity classes from the absolute and relative polynomial hierarchy; give examples of problems

l. Understand the main idea of parallelization

m. Define the class NC of parallelizable P problems, know the relation between NC and P, and an example of a P-complete problem

n. Understand the difference between the formal computation time of a parallel program and the actual time which takes communication time into account

o. Define Kolmogorov complexity, understand motivations behind this definition

p. Be aware of the main ideas behind different physical schemes of computing beyond traditional Turing machines, such as quantum computing

2. Application and Analysis

a. Trace the computation of a primitive recursive or recursive function on a numerical example

b. Translate a formal description of a primitive recursive or recursive function into a program

c. Trace a Turing machine on a given input

d. Prove that satisfiability is NP-hard, and that one more problem is NP-hard

e. Know how to parallelize standard simple parallelizable algorithms (e.g., search, or dot product of two vectors)

f. Use the definition of Kolmogorov complexity K(x) to provide reasonable upper bounds for K(x) of a given string x

3. Synthesis and Evaluation

a. Prove, from the definition, that a given function (e.g., a given polynomial or propositional function) is primitive recursive or recursive

b. Design a Turing machine that computes a given function

c. Synthesize Turing machines that compute two functions into a Turing machine for computing their composition

d. Prove that not every problem is computable - e.g., that the halting problem is undecidable

e. Apply diagonalization to prove results similar to what we had in class

f. Prove that given simple sets are decidable and/or r.e.

g. Prove that the union, intersection, and complement of decidable sets are decidable

h. Prove that the union and intersection of r.e. sets is r.e.; prove that the complement to a r.e. set is not always r.e.

i. Prove that not every r.e. set is decidable and that not every set is r.e.

j. Prove, for a given software requirement, it is algorithmically impossible to check whether a given program satisfies this requirement

k. For problems similar to ones considered in class, prove their NP-hardness

l. Be able to parallelize simple algorithms

m. Be able to understand and present a research paper in Theory of Computing - with a minor help from a professor

Main Source: Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Co., 2nd or later edition

Projects: An important part of the class is a project. There are three possible types of projects:

A project can be: The most important aspect of the project is that it should be useful and/or interesting to you. The instructor can assign a project to you, there are plenty of potential projects, but if each student selects a project that he or she likes, this will be much much better for everyone.

Assignments: Reading and homework assignments will be announced on the class website. You should expect to spend at least 10 hours/week outside of class on reading and homework.

Homework Assignments: Each topic means home assignments. Howeworks will be due by the start of the next class:

To submit a homework, send it to me by email. If it is not electronic, scan it and send him/her the scanned version.

One week after the homework was assigned, I will post correct solutions. I will be glad to answer questions if needed.

If you have a legitimate reason to be late, let me know, you can then submit it until the homeworks are posted. If you were simply late, you can still submit until the homeworks are posted, but then points will be taken off points for submitting late.

Since I will be posting correct solutions to homeworks, it does not make any sense to accept very late assignments: once an assignment is posted, it make no sense for you to copy it in your own handwriting, this does not indicate any understanding. So, please try to submit your assignments on time.

Things happen. If there is an emergency situation and you cannot submit it on time, let me know, you will then not be penalized -- and I will come up with a similar but different assignment that you can submit to me when you become available again.

Homework must be done individually. While you may discuss the problem in general terms with other people, your answers and your code should be written and tested by you alone. If you need help, consult the instructor.

Exams: There will be three tests: on February 18, March 25, and April 29, and the final exam on May 13, 1-3:45 pm. The logistics of each test is very straightforward:

Similar to homeworks, I will post solution, send you the grades, and answer questions if something is not clear.

As usual, if you are unable to attend the test, let me know, I will organize a different version of the text at a time convenient for you.

Grades: Each topic means home assignments (mainly on the sheets of paper, but some on the real computer). Some of them may be graded. Maximum number of points:

(smart projects with ideas that can turn into a serious scientific publication get up to 40 points).

A good project can help but it cannot completely cover possible deficiencies of knowledge as shown on the test and on the homeworks. In general, up to 80 points come from tests and home assignments. So:

Special Accommodations: If you have a disability and need classroom accommodations, please contact the Center for Accommodations and Support Services (CASS) at 747-5148 or by email to cass@utep.edu, or visit their office located in UTEP Union East, Room 106. For additional information, please visit the CASS website at http://www.sa.utep.edu/cass. CASS's staff are the only individuals who can validate and if need be, authorize accommodations for students.

Scholastic Dishonesty: Any student who commits an act of scholastic dishonesty is subject to discipline. Scholastic dishonesty includes, but not limited to cheating, plagiarism, collusion, submission for credit of any work or materials that are attributable to another person.

Cheating is:

Plagiarism is: To avoid plagiarism see: https://www.utep.edu/student-affairs/osccr/_Files/docs/Avoiding-Plagiarism.pdf

Collusion is unauthorized collaboration with another person in preparing academic assignments.

Instructors are required to -- and will -- report academic dishonesty and any other violation of the Standards of Conduct to the Dean of Students.

NOTE: When in doubt on any of the above, please contact your instructor to check if you are following authorized procedure.

Daily Schedule: (tentative and subject to change)

January 19: topics to cover:

January 21: topics to cover:

January 26: topics to cover:

January 28: topics to cover:

February 2: topics to cover:

February 4: topics to cover:

February 9: topics to cover:

February 11: topics to cover:

February 16: overview for Test 1.

February 18: Test 1.

February 23: overview of Test 1 results.

February 25: topics to cover:

March 2: topics to cover:

March 4: topics to cover:

see lecture on feasibility, lecture on P and NP, and Sections 2.2 and 2.3 from the lecture

March 9: topics to cover:

March 11: topics to cover -- other examples of NP-complete problems:

March 23: preview for Test 2

March 25: Test 2

March 30: review of Test 2 results

April 1: topics to cover:

April 6: topics to cover:

April 8: topics to cover:

April 13: topics to cover:

April 15: topics to cover:

April 20: topics to cover:

April 22: project presentations

April 27: preview for Test 3

April 29: Test 3.

May 4: overview of Test 3 results.

May 6: preview for final exam.

See You All in the Class!