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

Room:TWHC 307

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

• The instructor's office hours are Mondays and Wednesdays 3-4:20 pm, or by appointment.
• If you want to contact the instructor during the scheduled office hours, there is no need to schedule an appointment.
• If you cannot contact the instructor during the instructor's scheduled office hours, please schedule an appointment in the following way:
  • use the instructor's appointments page https://www.cs.utep.edu/vladik/appointments.html to find the time when the instructor is not busy (i.e., when he has no other appointments), and
  • send him an email, to vladik at utep.edu, indicating the day and time that you would like to meet.
  He will then send a reply email, usually confirming that he is available at this time, and he will place the meeting with you on his schedule.

Main Objectives:

• to teach the foundations of computing, and
• to enable students to prove (not only to program).

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:
   • parallelism,
   • algebraic computations,
   • computations with real data (including the idea of interval mathematics),
   • fuzzy algorithms,
   • neural computing,
   • chemical computing,
   • quantum computations, etc.

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:

• An ideal class project is if you do something related to theory which is useful for your future thesis or dissertation. Please check with your advisor about it, maybe he or she wants you to read and report on some theory-related paper, maybe you need to do some theory-related research, whatever your advisor recommends will be a very good project for this class, just let the class instructor know what exactly you plan to do.
• If you have not yet selected an advisor, but you already know what research area you want to work in, come talks to the class instructor, we will try to find some appropriate topic -- and if you have any proposals already, great.
• If you do not have a research topic or you have a one but your advisor cannot find anything theory-related that will be helpful for your future thesis or dissertation, come talk to the instructor too.
• Maybe you like theory and want to start doing a project in theory, then come and talk to the instructor, we will try to find something that will be of interest to you.

• reviewing and reporting on a related paper; if you selected this project, make sure -- by googling -- that this paper is not outdated, that no more recent paper has better results; otherwise, why study the paper's algorithm ia better one is known? or
• doing some independent research (not research as in high school, but research as in graduate school, i.e., trying to come up with something new), or
• programming something theory-related.

Assignments: Reading and homework assignments are 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. Home assignments are posted on the homeworks website. General comments.

• Solutions to the homeworks should be submitted to the instructor as attachments to an email. If your solution is on paper, scan it and send the scanned file. Make sure that the instructor's computer can read the this file. In general, pdf, jpeg, and many other general formats are OK, the instructor will let you know if the format is not readable.
• When submitting a homework, please add its number to the email subject. Please use the same number as in this list of homeworks.
• In general, for full credit, homeworks need to be submitted before 4:30 pm on the due date. You can submit your solutions after the deadline -- but before the solutions are posted. In general, points will be taken off for late submissions. The only two exception are:
  • students who have a special CASS permission to submit solutions at any time before the solutions are posted, and
  • students who have a legitimate reason to be late; if you have such a reason, let the instructor know; once the instructor approves late submissions. you can then submit your solutions until the homeworks are posted.
  In these two cases, there will be no penalty for later submissions.
• In general, solutions to the homeworks that are due on the day of a class will be posted right after the next class:
  • if a homework is due on Monday, the solutions will be posted on Wednesday, and
  • if a homework is due Wednesday, the solutions will be posted next Monday.
  Once the correct solutions are posted, student answers will no longer be accepted. The only exception is programming assignments: there will be no posted solutions to these assignments, so you can submit solutions to these assignments any time -- with the corresponding penalty for late submissions.
• Things happen. If there is an emergency situation and you cannot submit your solution before the solutions are posted, let the instructor know, the instructor will then make sure that your overall grade for the homeworks is not affected by this situation.
• Homeworks are an indicator how well students understand the material. The instructor is not supposed to help solve the assigned homeworks, but the instructor is always willing to show how to solve a similar problem.

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 and the final exam.

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 test at a time convenient for you.

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

• first test: 10
• second test: 10
• third test: 15
• home assignments: 10
• final exam: 35
• project: 20

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:

• to get an A, you must gain, on all the tests and home assignments, at least 90% of the possible amount of 80 points (i.e., at least 72), and also at least 90 points overall (i.e., 90% of all 100 possible points including points for the project);
• to get a B, you must gain, on all the tests and home assignments, at least 80% of the possible amount of 80 points (i.e., at least 64), and also at least 80 points overall;
• to get a C, you must gain, on all the tests and home assignments, at least 70% of the possible amount of 80 points (i.e., at least 56), and also at least 70 points overall.

A comment about partial credit. In pedagogical literature, it has been noticed that there is a problem with giving 9 out of 10 points for minor mistakes. The problem is that when in a test with 10 questions, a student is almost correct on each of them – getting 9 out of 10 points for each problem – the student's overall grade for the test is 90 out of 100 – which usually corresponds to A ("excellent"). This does not seem to be right: a student is classified as excellent, but in all 10 problems, the student's answers are wrong! To avoid such situations, it is recommended to give at most 8/10 when the answer is wrong. In our grading of the tests, we will follow this recommendation.

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 https://www.utep.edu/student-affairs/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:

• copying from the test paper of another student;
• communicating with another student during a test to be taken individually;
• giving or seeking aid from another student during a test to be taken individually;
• possession and/or use of unauthorized materials during tests (i.e. crib notes, class notes, books, etc.);
• substituting for another person to take a test;
• falsifying research data, reports, academic work offered for credit.

• using someone's work in your assignments without the proper citations;
• submitting the same paper or assignment from a different course, without direct permission of instructors.

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 21: topics to cover:

• what is Theory of Computation and why it is important, see lecture; see also the following file
• Church-Turing Thesis, see lecture
• how can we use Church-Turing Thesis to prove results?; see lecture.

January 26: discussion of possible projects

January 28: work on your project day

February 2: work on your project day

February 4: topics to cover:

• primitive recursive functions as description of for-loops, see lecture; see also primitive recursive parts of file 1 and file 2, and notes

February 9: topics to cover:

• many functions and constructions are primitive recursive, see lecture

February 11: topics to cover:

• proving that not all computable functions are primitive recursive, see lecture

February 16: topics to cover:

• mu-recursive functions as description of while-loops, see lecture; see mu-recursive parts of file 1 and file 2

February 18: topics to cover:

• Turing machines, see lecture

February 23: review for Test 1

February 25: Test 1.

March 2:

• overview of Test 1 results
• how to simulate a Turing machine; see lecture.

March 4:

• equivalence of Turing machines and mu-recursive functions, see lecture.

March 9: topics to cover:

• how to represent a Turing machine as a finite automaton with two stacks; see paper;
• halting problem, see lecture;
• impossibility to check whether a program -- that always halts -- is correct, see lecture;
• feasible and non-feasible algorithms; intuitive idea, precise definition, and why this definition is not perfect; see lecture on feasibility, lecture on P and NP, and Sections 2.2 and 2.3 from the lecture

March 11: topics to cover:

• P, NP, notion of reduction, NP-hard; see lecture on feasibility, lecture on P and NP, and Sections 2.2 and 2.3 from the lecture

March 23: review for Test 2

March 25: Test 2.

March 30: topic to cover:

• decidable and enumerable sets, see lecture

April 1: topics to cover:

• proof that propositional satisfiability is NP-hard, see Sections 2 and 3 of lecture 1 and lecture 2

April 6:

• rehearsals of project presentations

April 8:

• rehearsals of project presentations,
• 3-SAT, see lecture,
• 3-coloring, see lecture.

April 11: NMSU/UTEP workshop

April 13: topics to cover:

• 3-coloring, see lecture,
• clique problem, see lecture,
• subset sum is NP-complete, see lecture.

April 15: topics to cover:

• subset sum is NP-complete, see lecture,
• interval computations are NP-hard, see lecture
• parallel computations; see lecture and Section 2 of the following lecture

April 20: topics to cover:

• probabilistic algorithms; see lecture,
• greedy algorithms; see lecture,
• a natural feasible algorithm that checks satisfiability of 2-CNF formulas, see lecture
• Kolmogorov complexity; see lecture
• project presentations

April 22:

• quantum computing, see lecture
• review for Test 3

April 27: Test 3.

April 29: topics to cover:

• polynomial hierarchy; see lecture
• unconventional computation schemes; see lecture 1, lecture 2, lecture 3, and lecture 4

May 4:

• overview of Test 3 results;
• preview for the final exam;
• project presentations

May 6: no class, compensation for attending NMSU/UTEP and CoProD workshops May 13: 4-6:45 pm final exam