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.

May 7:

Final.

Mar 31:

Midterm, in class.

Jan 25:

Semester begins. Welcome!

Syllabus for CSC427 Introduction to the Theory of Computation.

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.

• Meet on Zoom
• Join the Slack channel, csc-courses.slack.com#csc427-212. Joining with email addresses cs.miami.edu, miami.edu, or umaimi.edu are immediate. If you have a problem, I can send an invitation.
• Please follow us on twitter/csc_517 (various courses use this same twitter-feed)
• Course materials are on Github at github.com/csc-courses/csc427-212
• The assigned textbook is Introduction to the Theory of Computer, Third Edition by Mike Sipser.
• There maybe reading assignments from texts other than the class text.
• The course assigns problem sets — either written assignments or programming projects.
• Programming assignments are in Python and Jupyter.
• Grace Periods
  • Points deducted beyond the grace period 25%, and 25% more each additional class date.
  • Starting with Problem Set 5, the new lateness policy is 0% one class late, 50% two classes late, and no credit when three classes late. Homework is due midnight Miami time of the date due; and late days are also counted at midnight Miami time of that day.
  • No work accepted after midnight of the last day of classes, and this rule has precedence over grace periods.
• Submitting your problem sets.
  • New! Your name must appear in the the notebook file, in the space provided at the top of the notebook. Attach the Jupyter notebook file (extension .ipynb) to an email, and send to burt+csc427@cs.miami.edu
  • Format the subject line: csc427 _your_name_ (ps|midterm|final) _n_ [version]
  • For instance: csc427 burt rosenberg ps 1 or csc427 burt rosenberg ps 1 resubmit 1
  • Please be accurate with the subject line syntax, and decide on the form of your name for all submissions.
• Our lead grader is Zishi Wu (zishi_at_cs.miami.edu). We also have Dylan Aron as an assistent grader.
• Grades are 30% final, 30% midterm, 40% problem sets.

Class notes for CSC427 Introduction to the Theory of Computation.

• Final:
  • The final is on Friday, May 7, at 11:00am–1:30pm
  • Coverage and suggested exercises are posted under Problem Sets
  • csc427_212_final.pdf
• Midterm:
  • The midterm is in-class on Wednesday, May 31.
  • csc427_212_midterm.pdf
  • Histogram and stats
• Previous Midterms:
  • 2020 spring (answer key)
  • 2017 spring
• Day by Day:
  • Wednesday Jan. 27: (♾)
  • Friday Jan. 29: (♾)
    • DFA's
  • Monday Feb. 1: (♾)
    • string operations, union, concatenation, star.
  • Wednesday Feb. 3: (♾)
    • Python data structures
  • Friday Feb. 5: (♾)
    • Regular Expressions
  • Monday Feb. 8: (♾)
    • NFA's
  • Wednesday and Friday Feb. 10 and 12: (♾)
    • NFA to DFA construction
  • Wednesday Feb. 17: (♾)
    • RE to NFA construction
    • Closure properties of Regular Languages
  • Friday Feb. 19: (♾)
    • DFA to RE construction, via a GNFA.
  • Monday Feb. 22: (♾)
    • Non-regular languages
  • Wednesday Feb. 24: (♾)
    • What is the power of non-determinism for RE's?
  • Friday Feb. 26: (♾)
    • Pumping Lemma
  • Friday Mar. 5: (♾)
    • Pumping Lemma continued
  • Monday Mar. 8: (♾)
    • Context Free Langauges
    • Push down automata
  • Wednesday Mar. 10: no notes
  • Friday Mar. 12: (♾)
    • Context Free Grammars
    • Parse trees
  • Monday Mar. 15: no notes
    • Formal defintion of a CFG.
    • Ambiguity in grammer, and inherently ambiguous CFL
    • Examples, BNF, Python grammar.
  • Wednesday Mar. 17: (♾)
    • Closure properties of CFL's
    • Non-closure propertiles of CFL's
    • A non-CFL language
  • Friday Mar. 19:
    • Chomsky Normal Form
  • Monday Mar. 22: (♾)
    • Chomsky Normal Form (worked example)
    • The Cocke-Younger-Kasami algorithm
  • Wednesday Mar. 24: (♾)
    • The Cocke-Younger-Kasami algorithm
    • Recognizing non-CFL with a 2 stack PDA (TM's)
    • Brief look at the Pumping Lemma for PDA's.
  • Friday Mar. 26: (♾)
    • Pumping Lemma for PDA's.
  • Monday Mar. 29:
    • Midterm Review
  • Wednesday, Mar. 31: Midterm
  • Friday April 2: (♾)
    • Turing Machines
  • Monday April 5–12: (♾)
    • Turing Machine Programming Techniques
    • Multitape Turing Machines
  • Monday April 19: (♾)
    • Problem set 7
    • Nondeterministic TM
  • Wednesday April 21: (♾)
    • Universal TM
    • TM Enumeration
    • The Halting Problem is Undecidable
    • The Not Halting Problem is Unrecognizable
    • See section 4.2 Sipser and the recorded lecture
  • Friday April 23: (♾)
    • The uncountability of the real numbers.
    • Reducibilty
    • Undecidable problem by reducibility: HALT_TM, E_TM, REGULAR_TM
  • Monday April 26: (♾)
    • Algorithm complexity for 0ⁱ1ⁱ
    • Time to simulate alternative TM models
    • The Class P and reasonable models of computation
    • Polynomial time Verification and the Class NP
  • Wednesday April 28: (♾)
    • NP Complete Problems
    • Polynomial Time Reductions
    • Reduce 3SAT to k-clique
  • Friday April 30: (♾)
    • Cook Levin Theorem
    • Reduce SAT to 3SAT
    • Reduce 3SAT to k-vertex cover
  • Friday May 7: Final Exam
• Learning Python:
  • Where it can squeeze
  • Problem Set by Problem Set
• Automata in the World
  • The Jacquard Loom, invented 1804.
    A working example at the Paisley Museum in Scotland.
  • Charles Babbage's Analytical Engine, of Ada Lovelace fame.
  • Switches according to the phone company
• Introduction
  • See the blog posting.

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 0: Due: Wednesday, 3 February
  • Install the Individual Edition Anaconda.
  • Add to the end of your .zshrc or .bash_profile,
    • export PATH="~/opt/anaconda3/bin:$PATH"
  • Get a zip of the class github and copy csc427-ps0.ipynb to your workspace.
  • Open a terminal, navigate to csc427-ps0.ipynb and use the command line command "jupyter notebook".
  • Complete the project and submit, as described in the syllabus course requirements.
• Reading Assignment 0: 0.1, 0.2 and 1.1.
• Problem Set 1: Due: Wednesday, 10 February
  • Copy csc427-ps1.ipynb to your local workspace.
  • Open with Jupyter and complete the assignment.
  • Be aware that the passing the tests provided in the notebook does not mean your solution is completely correct. I suggest you add tests to make sure all cases are considered.
  • Attach the completed assignment to an email, to address and with subject line as described in the course syllabus.
• Reading Assignment 1.2 and 1.3.
• Problem Set 2: Due: Wednesday, 17 February
  • Please see csc427-ps2.ipynb
  • Other instructions as above.
• Reading Assignment 1.4.
• Problem Set 3: Due: Wednesday, 24 February
  • Please see csc427-ps3.ipynb
  • Other instructions as above.
• Problem Set 4: Due: Friday, 5 March
  • Please see csc427-ps4.ipynb
  • Other instructions as above.
• Reading Assignment 2.1.
• Reading Assignment 2.2.
• Problem Set 5: Due: Monday, 22 March
  • Please see csc427-ps5-PDA.ipynb
  • Other instructions as above.
  • sketch-PDA-examples.ipynb for example PDA programs.
• Reading Assignment 2.3.
• Midterm: Wednesday March 31.
  • csc427_212_midterm.pdf
• Problem Set 6: Due: Fri, April 16. (new due date)
  • Please see csc427-ps6.ipynb
  • Other instructions as above.
• Problem Set 7: Due: Monday, April 26.
  • Please see csc427-ps7.ipynb
  • There is also a thin version, that requires you clone the github, so that the pure python file csc427_code_ps7.py is in the directory.
  • Other instructions as above.
• Reading Assignment chapter 3.
• Reading Assignments for the Final:
  • Chapter 4. Decidability and Undecidability
  • Chapter 5, Section 1. Reducibility.
  • Chapter 5, Section 3, Mappig reducibilty
  • Chapter 7. The Classes P and NP. NP-Completeness.
• Suggested Problems for the Final:
  • Exercises 4.1, 4.2, 4.3, 4.4, 4.5, 4.7, 4.8.
  • Exercises 5.4, 5.5, 5.6, 5.7
  • Exercises 7.1, 7.2, 7.5, 7.6, 7.7, 7.8, 7.12.
  • Notes for the final
  • Chart of Decidable and undecidable problems
• Final: Friday, May 7, 11:00am–1:30pm
  • csc427_212_final.pdf

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