# CSE 105: Introduction to Theory of Computability

Is there a problem that NO computer can ever solve?
What resources are needed to solve a problem?
Are some problems harder than others?

In this course, we will explore what it means to be "computable". We begin with a very simple model of computation, and work our way to the most powerful, the Turing machine, named after Alan Turing, who formalized the notion of "algorithm" even before there were any physical computers. You'll also learn about the relationship of these models to some essential tools in a computer scientist's toolkit, such as regular expressions and context-free grammars. Finally, you'll develop your technical communication skills in writing formal arguments and proofs.

## Syllabus

Upon successful completion of this course, you will be able to:

• Classify the computational complexity of a set of strings by determining whether it is regular, context-free, decidable, or undecidable.
• Give examples of sets in each of these classes (and prove them).
• Classify the computational complexity of a decision problem by translating it to a set of strings coding the problem.
• Use and design automata both formally and informally, including DFA, NFA, PDA.
• Deduce the language recognized by a machine or other formal description, including DFA, NFA, RegExp, PDA, CFG, TM.
• Prove invariants of computational classes, e.g. the class of regular languages is closed under ....
• Prove that certain models of computation are equivalent and translate between them algorithmically.
• Apply classical techniques including pumping lemma, determinization, diagonalization, and reduction to analyze the complexity of languages and problems.

## Getting in touch

With remote learning in place, we have new challenges (and opportunities) for connecting this quarter and working together on CSE 105. To start, here are the plans we have for scheduled and asynchronous ways to talk about CSE 105:

• Video content for class will be posted and shared before the MWF lecture times, here.
• On MWF 10am (Note: updated time), I'll be available on Zoom to answer questions and facilitate problem solving practice about the content covered in the videos. Join Zoom Meeting
• at the URL https://ucsd.zoom.us/wc/join/794807039
• using Meeting ID: 794 807 039
• with One tap mobile +16692192599,,794807039# US (San Jose) +16699006833,,794807039# US (San Jose)
These sessions will be recorded and shared. There will be no Zoom session on UCSD holiday Monday, May 25.
• Additional opportunities for office hours Q&A will be scheduled with each member of the instructional team, via Zoom and/or Piazza.
• You can post questions about the class content on Piazza anytime, via private posts (viewable to the instructor, TAs, and tutors) if about graded work, or public posts if about general questions and lectuer material.
• You can also reach out to me directly by email: minnes@eng.ucsd.edu . Quick note: I'm happy for you to address me as Prof. Minnes, Dr. Minnes, and/or Mia. Please do not use the title Ms./ Mrs. for me.
• We encourage you to find classmates to work on homework in groups. To help facilitate this, here are two guides:
• Updated In order to incorporate as many people's schedules as possible, discussion sections will be held at both of the originally scheduled times (2:00 - 2:50pm and 3:00 - 3:50pm on Fridays) via Zoom. The format of the discussion section will consist of a review of the lecture material for the week, as well as example problems. The same material will be presented during each session. In order to reap the full benefits of these sessions, we strongly recommend that you have reviewed all of the lecture materials for the week. While all discussion sections will be recorded, attending them live when possible will be a great opportunity for you to ask questions and will help promote an interactive environment. The link and password for these sessions will be posted on Piazza.

### Campus resources

The JSOE IDEA Engineering Student Center will offer remote Engineering Learning Communities (group tutoring) beginning first week of spring quarter. More information is available here: http://jacobsschool.ucsd.edu/idea/programs/idea_studylab.shtml

The Teaching and Learning Commons will also continue to offer their full suite of support programs. More information is available here: https://commons.ucsd.edu/

## Textbook and supplies

The required textbook for this course is

Sipser, Michael   Introduction to the Theory of Computation

I highly recommend this book for the class - it's very well-written and we'll be using it extensively. Due to the current global situation, the textbook publisher is offering free access to the electronic version of this book for this quarter. To get access, you need to create an account with them (you only have to do this once) and select "Start Free Trial". In two weeks, you will need to renew the free trial; they've set it up so you can continually renew free access through end of this term. Here are more details from Cengage:
• For students who have purchased Cengage Unlimited, they can continue to use Cengage Unlimited with no interruption in service, and we will extend access as needed, based on the situation at your institution (i.e. more days are added to your spring semester). For these students, there is no action item at this time.
• For students who are not currently using Cengage Unlimited and have not otherwise activated a trial with us within the last 75 days, they should go to www.cengage.com, create an account with us, and choose "Start Trial". Here is a link to help you with the process: https://www.cengage.com/coursepages/CU_Access_Spring
For a physical copy, the Third Edition (international) of this book is available at the UCSD Bookstore (see their website for details on free shipping) for approximately \$20.

To brush up on proofs, use: Richard Hammack, Book of Proof, 2nd ed. (available for download here)

### Machine visualization resources

There are multiple tools to help you visualize and test finite state machines, the foundational computer models we are studying in this class. We will support two of these tools in CSE 105 this quarter: JFLAP and flap.js. JFLAP was developed starting in the 1990 by a team led by Susan Rodger (RPI, then Duke). It is now a mature tool with a lot of functionality. Some of the conventions and notation it uses differ from the course textbook for CSE 105. The second tool, flap.js, is a webapp under development by a group of UCSD students that is being piloted in CSE 105. It is being customized for use in this class. Let me know if you're interested in joining the development team for flap.js to help future CSE 105 students.

#### flap.js

The homepage for the tool is at https://flapjs.github.io/FLAPJS-WebApp/; a detailed tutorial is available here. It currently has many features for designing and working with DFA and NFA. The module on PDA allows you to draw state diagrams.

#### JFLAP

The homepage for the tool is at www.jflap.org; the current stable version is version 7.1.

##### Basic installation and configuration

For those who already have Java Virtual Machine installed. NOTE: you should be able to install JFLAP on systems with JVM even if you don't have install/Administrator rights.

2. Double-click it to run JFLAP. If it doesn't launch, that probably means you don't have JVM installed. See instructions below.
3. Go to Preferences, then select "Set the Empty String Character," and change it from "Lambda" to "Epsilon." This will make JFLAP match the notation we use in the book and in class for the empty string character.
##### If you don't already have JVM (Java Virtual Machine) installed on your computer

You'll need to get the JVM in order to run JFLAP. You will need install/Administrator rights to do this. To install:

4. After the install is finished, you may need to reboot.
5. Now follow the "Basic Install and Configuration" instructions above to install and configure JFLAP.

Regular Expressions Do not use whitespace in your regular expressions unless a space is a valid symbol in the alphabet. JFLAP uses a + symbol instead of the U used in the textbook to indicate union.

Start and Accept States Don't forget to specify these when drawing your automata!

Multiple Transitions If you need multiple possible inputs for the same arrow in your diagram (e.g. if you can move between states on either a 0 or a 1), this is done by creating separate edges in JFLAP for each input symbol. JFLAP will combine these into one arrow on your diagram. Automata with transitions labeled with a comma (e.g. "0,1") are not equivalent, because those transitions will not be followed unless "0,1" actually appears in your input string.

Empty String In class and in the text, we use ε (epsilon) to denote the empty string. The instructions above help you change the JFLAP default λ (lambda) to match our conventions. If you need a state transition (or a stack symbol for PDA's) for ε, do not enter any characters into the text box for that transition and ε will appear. Entering a space does not work; that transition will be followed only if the input string has a space on it. Similarly, entering E or "epsilon" will not work because JFLAP will try to match those exact symbols in your input string for the transition.

Push Down Automata Each transition has three labels: an input symbol, a stack symbol to pop, and a stack symbol to push. JFLAP uses the semicolon (;) instead of a right arrow to separate the stack symbols. Any of the three labels can be the empty string. Settings: Your PDAs should be "Single Character Input" (this option appears when you first create an automaton), and they should accept by final state, not by empty stack.

Context Free Grammars If you have a production rule of the form "S -> A | B", enter it as two rules "S -> A" and "S -> B".

### Typesetting (LaTeX) Resources

All submitted homework for this class must be typed. Diagrams may be hand-drawn and scanned and included in the typed document. You can use a word processing editor if you like (Microsoft Word, Open Office, Notepad, Vim, Google Docs, etc.) but you might find it useful to take this opportunity to learn LaTeX. LaTeX is a markup language used widely in computer science and mathematics. The homework assignments are typed using LaTeX and you can use the source files as templates for typesetting your solutions.

If you have never used LaTeX, we recommend cloud resources (e.g. Overleaf) that don't require you to download and install LaTeX on your local machine. In particular, Overleaf has great collaboration functionality if you choose to work with a group.

An open source LaTeX reference is here, and you can Google for many templates and examples to get you started.

My hope is that we will focus most of our CSE 105 energies on exploring theory of computation together and with integrity. Grades in this class are designed to reflect your work and evidence of learning of this core material. They are also designed to accommodate the emergency remote learning context we're all facing this quarter. Please reach out to me (minnes@eng.ucsd.edu) if you have extenuating circumstances that you think will impede your ability to participate in the planned CSE 105 activities; I'd like to work out a solution together.

You may consider whether you would like to take this course for letter grade or P/NP. To help make this decision, I encourage you to reach out to your college and major advisers. The following guidelines from campus might also be useful:

• P/NP grades taken during Spring 2020 will not count towards the 25% cap on P/NP (P/NP courses will be removed from both the numerator and denominator in this calculation).
• Students will be able to select P/NP (and S/U) grades through the end of the 10th week.
• The add deadline is extended to the end of Week 3.
• The drop deadline, without a W, is extended to the end of Week 5.
• The undergraduate drop deadline, with a W, is extended to the end of Week 7.
• The graduate student drop deadline, with a W, remains at the end of Week 9.
• Undergraduates may petition to drop a class or withdraw from the University after the end of week 7 and by the end of Week 10 for emergency reasons. These petitions are decided by the college provost.
• Graduate students may petition to drop a class or withdraw from the University after the end of week 9 and by the end of Week 10 for emergency reasons. These petitions are decided by the Dean of the Graduate Division.

Revised grading policy to incorporate additional flexibility and leniency in light of current traumatic events. Differences from the original policy are highlighted in bold.

The graded components for CSE 105 will be Homework, Review quizzes, Project, Final exam. Each student's overall average in the course will be computed as MAX(Original, New Option 1, New Option 2)

• Original (+ drop more quizzes) means:
• Homework - 50% of overall score (We'll drop the lowest HW score.)
• Review quizzes - 20% of overall score (We'll drop the lowest six quiz scores.)
• Project - 15% of overall score, computed by weighting the three parts as 15% Part 1, 60% Part 2, 25% Part 3
• Final exam - 15% of overall score
• New Option 1 (final has zero weight) means
• Homework - 50% of overall score (We'll drop the lowest HW score.)
• Review quizzes - 20% of overall score (We'll drop the lowest six quiz scores.)
• Project - 30% of overall score, computed by weighting the three parts as 15% Part 1, 60% Part 2, 25% Part 3
• Final exam - 0% of overall score
• New Option 2 (Part 3 of the project has zero weight)
• Homework - 50% of overall score (We'll drop the lowest HW score.)
• Review quizzes - 20% of overall score (We'll drop the lowest six quiz scores.)
• Project - 15% of overall score, computed by weighting the three parts as 25% Part 1, 75% Part 2
• Final exam - 15% of overall score
Homework
• 1-hw Regular Languages (due Sunday of Week 3, April 19)
• 2-hw Nonregular Languages and Context-free Languages (due Sunday of Week 5, May 3)
• 3-hw Turing Machines, the Church-Turing thesis (due Sunday of Week 7, May 17)
• 4-hw Decidability and Undecidability, Reductions (due Sunday of Week 9, May 31)
All assignment files can be accessed at this Google Drive folder.
Review quizzes
Regular quizzes on textbook reading, and class videos to keep on track. You can submit these quizzes as many times as you like up to the deadline. We will drop your lowest 6 review quizzes when computing your quiz average. We will also re-open all review quizzes from this quarter for (re)submission until the end of finals week, Saturday June 13.
Project
The project component of this class will be an opportunity for you to extend your work on assignments and explore an extension or application of your choosing.
This project replaces the in-class exams we would have during an in-person quarter. The main thing that in-person, on-paper exams let us do is easily verify that it is in fact you, the student, completing a major assessment. Many students have told us that they are concerned that cheating will be frequent in all-remote courses. Incorporating some video assessement and some open-ended personalized projects help ensure that we are giving credit and grades to the people who earned them. Hopefully, you will also find them interesting and valuable activities in their own right. The project description is available at this Google doc. The project consists of three parts.
• Part 1 of Project: due by Friday of Week 6, May 8. This is a screencast video, submitted via Google form.
• Part 2 of Project: due by Friday of Week 8, May 22. This is a typed document, submitted via Gradescope.
• Part 3 of Project: due by Wednesday of Finals week, June 10. This is a screencast video, submitted via Google form.
You will need to achieve a passing grade (70%) on the project to pass this course.
Final exam

Homework
50% of overall score
• 1-hw Regular Languages (due Sunday of Week 3, April 19)
• 2-hw Nonregular Languages and Context-free Languages (due Sunday of Week 5, May 3)
• 3-hw Turing Machines, the Church-Turing thesis (due Sunday of Week 7, May 17)
• 4-hw Decidability and Undecidability, Reductions (due Sunday of Week 9, May 31)
All assignment files can be accessed at this Google Drive folder.
Review quizzes
20% of overall score
Regular quizzes on textbook reading, and class videos to keep on track. You can submit these quizzes as many times as you like up to the deadline.
Project
15% of overall score
More details later.
Final exam
15% of overall score
Cumulative quiz on class content during exam week of Spring quarter.

The Jacobs School of Engineering code of Academic Integrity is here. Academic integrity violations will be taken seriously and reported to the campus-wide Academic Integrity Office. Key facts about academic integrity related to CSE 105:

• Use resources from this offering of CSE 105 when you are working on assignments for this class, without consulting any written or video material from other classes or other sources.
• Do not share written solutions or partial solutions for homework with other students in the class who are not in your group. Doing so would dilute their learning experience and detract from their success in the class.
• Before taking the final exam, do not attempt to obtain information about the contents of the exam from students who have already taken it.
• After taking an exam or quiz, do not discuss its contents with anyone in the class who has not yet taken it. Do not post information about it or share information about it with other who haven't taken it.

## Policies

### Accommodations for students with disabilities

Students requesting accommodations for this course due to a disability must provide a current Authorization for Accommodation (AFA) letter issued by the Office for Students with Disabilities (OSD) which is located in University Center 202 behind Center Hall. Students are required to present their AFA letters to Faculty (please make arrangements to contact me privately) and to the OSD Liaison in the department in advance (by the end of week 2, if possible) so that accommodations may be arranged. For more information, see here.

### Class material and intellectual property

My lectures and course materials, including videos, assignments, and similar materials, are protected by U.S. copyright law and by University policy. I am the exclusive owner of the copyright in those materials I create. You may take notes and make copies of course materials for your own use. You may also share those materials with another student who is enrolled in or auditing this course. You may not reproduce, distribute or display (post/upload) lecture notes or recordings or course materials in any other way — whether or not a fee is charged — without my express prior written consent. You also may not allow others to do so. If you do so, you may be subject to student conduct proceedings under the UC San Diego Student Code of Conduct.