Photo from BBC News article by Prof. Jack Copeland

CSC427-C: Introduction to the Theory of Computation

News and Announcements for CSC427 Introduction to the Theory of Computation.

THIS FALL:

Csc595/685 a monday-only 1 credit minicourse on Quantum Computing!

Wed May 6:

Problem Set 8 due.

Wed Apr 22:

Problem Set 7 due.

Wed Apr 8:

Problem Set 6 due.

Mon Apr 6:

No-class Zishi will teach

Sun Apr 5:

New version of tm-multitape gives homework hint.

Fri Apr 3:

Enable participant video on Zoom

Fri Apr 3:

Problem Set 6 due.

Mon 23 Mar:

Midterm grades and grade distribution; and an important honor code notice.

Mon 23 Mar and onwards:

Class meetings moved on line using Zoom

Mar 14–20:

Extended Spring Break (Coronavirus Social Distancing)

Mar 9–13:

Spring Break

Mar 4:

Midterm

Mar 2:

Problem Set 5 due.

Feb 24:

Problem Set 4 due.

Feb 18:

Problem Set 4 on github includes NFA examples

Feb 10:

Problem Set 3 due.

Feb 5:

Update on lateness policy

Feb 5:

Problem Set 3 due.

Jan 29:

Problem Set 2 due.

Jan 22:

Problem Set 1 due.

Jan 20:

MLK Day off.

Jan 13:

Semester begins. Welcome!

Syllabus for CSC427 Introduction to the Theory of Computation.

Grades and NEW grading policy

• Honor code please read memo.
• Problem Set 4 grade distribution.
• Sample midterm: csc427.172 midterm
• Midterm rankings and statistics
• Milestone (information about new grading policy, and students possible grade standing)
  • Milestone FAQ
  • Milestone Reference
  • Milestone Worksheet
• Problem set 6 grade distributions.

General

This is a first course in the theory of computation. The course is of a generally mathematical nature, however it requires no calculus, or other "normal" mathematics. It explores what is computation. This is presented by way of machine models, and also linguistic models.

• The assigned textbook is Introduction to the Theory of Computer, Third Edition by Mike Sipser.
• Please follow us on twitter/csc_517 (same as 317 twitter feed)
• Join the Slack channel, csc-courses.slack.com#csc427-202. Discussions are best held in Slack, so that on general matters, all the class can benefit.
• The course assigns problem sets — either written assignments or programming projects.
• Updated: Grace Periods
  • Problem sets have a grace period of until the next class period (48 hours if due Monday or Wednesday, and 72 hours if due Friday)
  • No work accepted after midnight of the last day of classes, and this rule has precedence over grace periods.
• Programming assignments are in Python. Students should learn Python, and our TA is available for help in this.
• There maybe reading assignments from texts other than the class text.
• Our lead grader is Zishi Wu zishi@cs.miami.edu.
• There will be an in-class midterm and a final at the assigned slot during finals period.
• Grades are 30% final, 30% midterm, 40% problem sets.
• Updated: Grading Policy
  • The grading weights shall not be change in response to the realities of COVID.
  • The "finals period" has been canceled by the administration, hence a final cannot exist as planned.
  • The new plan is a final project that will receive the 30% weight intended for the final.
  • In recognition that a C- is an F in P/F, but that the department considers C- as a passing grade, I will give no C-'s in this class. Any C- will be moved up to a C.

Class notes for CSC427 Introduction to the Theory of Computation.

• This is just a general guide. The curriculum is being updated.
• Introduction
  • An historical perspective. See the blog posting. (mon 13 jan)
• Finite Automata
  • Notation, Deterministic Finite Automata (wed 15, fri 17 jan)
  • The class of regular languages is closed by complementation and union (wed 22 jan)
  • Concatenation operator, examples. Acceptance by F.A, epsilon-moves (fri 24 jan)
  • Models of nondeterminism: pure (guessing); search (that there exists an accepting computation) (mon 27 jan)
  • Intersection and Kleene star of regular languages (wed 29 jan)
  • All NFA's can be simulated by a DFA (fri 31 jan)
  • DFA from NFA construction, continued; introducing Regular Expressions (mon 3 feb)
  • Equivalence of Regular Expressions and Regular Languages (wed and fri, 5 and 7 feb).
  • The limits of DFA's: {0^k1^k | ∀ k} is not regular, introducing the Pumping Lemma (mon 17 wed 19 feb)
  • The Pumping Argument in the Court of Logic (fri 21 feb)
  • Dr Nim
• Lectures on Python by Professor Zishi (feb 10, 12 and 14)
• Context Free Languages
  • Context free grammars, parse trees (mon 24 feb)
  • Nondeterminism and ambiguity, {a^kb^kc^k | ∀ k} , RE ⊂ CFG (wed 26 feb)
  • (Non-)Closure properties, CFG for RE constructions (fri 28 feb)
  • Push down automatas (fri 6 mar)
• Midterm
  • Solutions to practice Midterm and to PS 5. (mon 2 mar)
  • Midterm (wed 4 mar)
• Turning Machines
  • Introduction (fri 6 mar)
  • Models of computation and the Church–Turing Thesis
    • 1933: Gödel and Herbrand — general recursive functions
    • 1936: Church, λ–calculus
    • 1936: Turing, the Entscheidungsproblem (vocab: Entscheidung)
  • The Turing Machine (mon 23, wed 25 mar)
    • An easy Turing Machine simulator in Python
  • Variants: multi-tape and nondeterministic
    • Python partial implementation of a multi-tape simulator
    • Variants of Turing macines. (PDF)
      • Multi-tape (fri 27 mar)
      • Universal (mon 31 mar, wed 1 apr)
      • Nondeterministic
  • Programming and Turing Machines
  • Godel Encoding
• Decidability and Undecidability
  • Decidable and recognizable sets (fri 3 apr)
    • Regular expressions ans CFL's are decidable.
    • Halting set is recognizable.
  • The Undecidability of the Halting problem (wed 8, fri 10 apr)
  • Unrecognizable sets, counting infinities (mon 13 apr)
• Complexity Theory
  • Time complexity, Big Oh (wed 15 apr Professor Zishi)
  • Overview of the theory of NP completeness. (fri 17 apr Professor Zishi)
  • Polynomial algorithms and the class P (Jupyter Notebook ) (mon 20 apr)
  • Exponential algorithms and the class NP (Jupyter Notebook) (mon 20 apr)
  • In clase quiz (wed 22 apr)
  • Nondeterminism and interpretations of NP (fri 24 apr)
  • reducibility, SAT reduced to 3-SAT (mon 27 apr)
  • 3-SAT reduced to k-VC (wed 29 apr)
  • NP-completeness, SAT as a nondeterministic P-time computation (fri 1 may)
• Quantum computation
  • Introduction by Dario Gil, IBM VP of Science and Solutions (fri 1 may)
  • The qubit (mon 4 may)
  • Superposition (mon 4 may, wed 6 may)
  • Entanglement (wed 6 may)
• THIS FALL! csc595/685 a monday-only 1 credit minicourse on Quantum Computing!

Decidability Round Up

Problem	Description	Computability	Notes
AFA	(i,j) ⊆ N × N s.t. FAi accepts j	decidable	run DFA
EFA	i ⊆ N s.t. L(FAi) = ∅	decidable	non-det guess element in complement
EQFA	(i,j) ⊆ N × N s.t. L(FAi) =L(FAj)	decidable	emptiness of symmetric difference
ACFG	(i,j) ⊆ N × N s.t. PDAi accepts j	decidable	Chomsky Normal Form
ECFG	i ⊆ N s.t. L(CFGi) = ∅	decidable	marking algorithm
X	x ∉ X, where X is decidable	decidable
co-EQCFG	(i,j) ∉ EQCFG	RE	∃ x s.t. (x,i) ∈ ACFG etc
EQCFG	(i,j) ⊆ N × N s.t. L(PDAi) = L(PDAj)	co-RE
ATM	(i,j) ⊆ N × N s.t. Mi(j) halts accepts	RE	run j on Mi
co-ATM	(i,j) ∉ HALT	co-RE
HALT	(i,j) ⊆ N × N s.t. Mi(j) halts	RE	run j on Mi
co-HALT	(i,j) ∉ HALT	co-RE
ETM	i ⊆ N s.t. L(Mi) = ∅	co-RE	Rice's theorm
co-ETM	i ∉ETM	RE	∃ x s.t. (x,i) ∈ ATM
EQTM	(i,j) ⊆ N × N s.t. L(Mi)=L(Mj)	non-RE	¬(RE ∪ co-RE)
co-EQTM	(i,j) ∉ EQTM	non-RE

Problem Sets for CSC427 Introduction to the Theory of Computation.

• Problem Set 1: due Wed Jan 22
  • Read chapters 0 and 1 of Sipser.
  • Exercises 0.1 through 0.6
  • Problem 0.11
  • Turn this in on paper, in class.
• Problem Set 2: due Wed Jan 29
  • Read chapters 0 and 1 of Sipser.
  • Exercises 1.1, 1.2, 1.3, and 1.4.
  • Turn this in on paper, in class.
• Problem Set 3: due Wed Feb 5 Mon Feb 10
  • Read chapters 0 and 1 of Sipser.
  • Exercises 1.7, 1.8, 1.9 and 1.10.
  • Turn this in on paper, in class.
• Problem Set 4: due Mon Feb 24
  • Install and learn Python:
    • Use the Anaconda installer
    • Install Jupyter, an integrated notebook/code environment.
    • Refer to the Python tutorial, and Zishi will present in class.
    • The DFA version of the code is the Jupyter notebook dfa-sim, posted to github.
  • Your assignment is to create an NFA simulator.
    • Download the dfa-sim and rename it nfa-sim.
    • Change the title, author, etc, in the text of the notebook, where appropriate.
    • Modify the code to implement an NFA:
      • Use the python container "set" for the the "current_states" (rather then current_state).
      • Update the transition dictionary to be a dictionary with values in pyton set.
      • Implement epsilon closure.
      • Modify the next step code to follow each transition from set of states to set of states.
  • To submit your program and to get help,
    • Subscribe to the Slack channel, csc-courses.slack.com#csc427-202, if you have not already.
    • To submit your resulting notebook,
      1. Create a folder with FIRSTNAME_LASTNAME (using the underscore)
      2. Place your nfa-sim.ipynb in that folder
      3. Compress the folder and attach it to an email
      4. Subject line is: "CSC427 PS4"
      5. Send to burt@cs.miami.edu and zishi@cs.miami.edu
• Problem Set 5: due Mon Mar 2
  • This problem refer to the court of logic. Show the complete "trial transcript" in the court of law convicting:
    • {aⁱba²ⁱ} of not being regular.
    • {w # w^R} of not being regular, where w is a string of 0, 1's, and # is itself, and the superscript R means "string in reverse".
  • This problem refer to the court of logic. Show a complete "trial transcript" in the court of law acquitting:
    • The set of strings (abc)* of the alphabet {a,b,c}.
    • The set of strings {aⁱ | i is a multiple of 10}.
  • Exercise 2.1, 2.4 and 2.6.
• Problem set 5 solutions
• Problem Set 6: due Fri Apr 3Wed Apr 8
  • Complete the exercises in the Jupyter Notebook of Turing Machine Programming.
  • Download and run locally on Juptyer, as you did for Problem Set 4.
  • To submit your resulting notebook,
    1. Create a folder with FIRSTNAME_LASTNAME (using the underscore)
    2. Place your nfa-sim.ipynb in that folder
    3. Compress the folder drop DM to Zishi on Slack
• Problem Set 7: due Wed Apr 22
  • Exercises 4.1 through 4.8.
  • To complete the exercise, work in the provided notebook
  • The text questions have been supplemented with coding sub-assignments.
• Final Project 8: due Wed May 6
  • The final project is given as the final project notebook

References for CSC427 Introduction to the Theory of Computation.

Promethean References

• Alan Turing, On computable numbers, with an application to the Entscheidungsproblem, 1936. In english, entscheiden is "to decide", to this translate to a decision problem, as in to decide whether to accept or reject a string.
• Alan Turing, Computing Machinery and Intelligence, 1950. The Imitation Game, and other thoughts.
• Richard Dedekind Essays on the Theory of Numbers, 1901. In case you ever had a curiosity about what really are numbers. It introduces the Dedekind Cut, that achieves the reals from the rationals by essentially replacing an irrational by the set of all rationals less than that irrational.
• Georg Cantor, Contributions to the founding of the theory of Transfinite Numbers, 1895, 1897. A careful investigation of infinity. The Cantor Diagonalization argument is create to prove uncountable infinities is used in this course to show non-Recursive sets, and the possibility of truths indescribable by finite methods (that is, logic).
• Frank P. Ramsey, Truth and Probability. (1926)
• G. Spencer Brown, The Laws of Form. (1969)

Understanding Computation

• Steven Hazel at Hackerdashery
  • #1: What is math computer science.
  • #2: P vs. NP and the Computational Complexity Zoo,

The best computing toys

• DIY Turing Machine
• Lego Turing Machine at CMU
• CWI Lego Turing Machine
• Digicom I
• Think-a-Dot
• Dr Nim

Quantum Computation References

• Scott Aaronson
• Umesh Vazirani at Berkeley
• John Preskill at CalTech

Programming References

• Python tutorial from the official Python site.
• Scipy Lectures, including Python tutorial and numpy.
• Jupyter Markdown
• HTML Entity Chart