ESR's Dr Nim, a Finite State Automata game

CSC427-C: Introduction to the Theory of Computation

Friday, May 3:

Final 11:00–1:30

Friday, April 5:

Midterm Rubric and selected answers

Wednesday, April 3:

Midterm Histogram

Monday, March 25:

Midterm.

Wednesday, Jan 17:

Class begins.

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.

• Join the Slack channel, csc-courses.slack.com#csc427-242. Uses your cs.miami.edu, miami.edu, or umaimi.edu email to join.
• The assigned textbook is Introduction to the Theory of Computer, Third Edition by Mike Sipser.
• We have a csc427-242 github with some public information, and the assignments.
• The course assigns problem sets — either written assignments or programming projects.
• Programming assignments are in Python and Jupyter.
• You will need a github account.
• Assignments are distributed and submitted (and help can be obtained) using Github classroom.
• Grace Periods
  • Three days grace.
  • After which 1/3 off.
  • Until a week, when its 2/3 off.
  • Until a second week, when it is 5/6 off.
  • Until the third week, when it is not graded but marked submitted.
  • 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.
• TA's and graders,
  • CSC427 Help Desk: David Flowers, dff20@miami.edu
  • Contact the "help desk" on slack.
• Grades are 30% final, 30% midterm, 40% problem sets.
• Midterm Date: In class.
• Final Exam Date: Friday May 3 11:00am-1:30pm

• Day-by-Day
  • Day 1, during which computation is discussed.
  • Day 2, during which deterministic and non-deterministic finite automate are discussed
  • Day 3, during which regular expressions and non-regular languages are discussed
  • Day 4, during which context free languages are discussed.
  • Day 5, during which Turing Machines are discussed.
  • Day 6, during which forms of undecidability are discussed.
  • Day 7, during which NP Completeness and PPT machines are discussed.
  • Day 8, during which IP and Zero-knowledge is discussed.
• Finite Automata
  • Notation, Deterministic Finite Automata
  • Closure properties for regular languages: demonstrated by the product automata
    • Complementation
    • Product automata for union and intersection
    • Difficulty for concatenation
      • Consider {multiple of five 1's} ∘ {multiple of three 1's} = {0,3,5,6} ∪ {|x|≥8}
      • Product construction would need to assign F=Q.
      • However regular languages are closed by concatenation
  • Nondeterminism: proposed by Michael Rabin and Dana Scott in 1959.
  • Epsilon closures.
  • Closure properties for regular languages: demonstrated with NFA
    • Concatenation and Kleene star
    • Union revisited
  • All NFA's can be simulated by a DFA. Power set construction.
  • Regular Expressions
  • Equivalence of Regular Expressions and Regular Languages
  • The limits of DFA's:
    • {0^k1^k | ∀ k} is not regular
    • The Pumping Lemma
• Context Free Languages
  • Push down automata
  • Context Free Grammars
  • All Regular Languages are CFL's.
  • Closure properties of CFL's: Union, Concatenation, Star
  • Non-closure properties of CLF's: not by complementation and not by intersection.
  • Chomsky Normal Form and the Cocke-Younger-Kasami algorithm.
  • Languages which are not Context Free: Pumping Lemma for CFL's
• Material for Midterm up to this point.
• Midterm histogram
• Midterm rubric and selected answers
• Turing Machines and Computability
  • Concepts, formalism, and example programs.
  • Variants:
    • nondeterministic turing machines
    • multitape turing machines
    • enumerators.
  • Decidability and Recognizability
    • Recursive and Recursive Enumerable
    • Decidable: {T, F}; R.E.: {T,⊥}; co-R.E.: {F,⊥}.
    • Summary of decidability and undecidability
  • The undecidability of the halting problem.
  • Decidable languages,
    • Acceptance for Finite Automata
    • Emptiness of Regular Languages
    • Equality of Regular Languages
    • Acceptance for Context Free Grammars
    • Emptiness of Context Free Languages
  • The arithmetic hierarchy
    • EQ and REG are neither R.E. nor co-R.E.
    • Relative to HALT, co-EQ can be enumerated.
• Complexity Theory
  • Review of Big Oh notation.
  • Polynomial and non-deterministic polynomial time
  • NP Completeness
    • Satisfiability of boolean formula
    • Polynomial time reductions
    • k-clique
    • hamiltonian path
    • Cook-Levin theorem
  • Probabilistic computation
    • The class BPP
    • Primality testing
  • Interactive Proof systems
    • The class IP
    • A IP proof of graph non-isomorphism
  • Zero Knowledge proof systems
    • Definition of knowledge
    • Zero Knowledge proof of graph isomorphism
    • All NP problems of ZK proofs
• Final exams
  • Semester 172 (spring 2016-2017)
  • Semester 212 (spring 2020-2021)

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)	non-RE	because not recursive
ATM	(i,j) ⊆ N × N s.t. Mi(j) halts accepts	RE	run j on Mi
co-ATM	(i,j) ∉ HALT	non-RE	because not recursive
HALT	(i,j) ⊆ N × N s.t. Mi(j) halts	RE	run j on Mi
co-HALT	(i,j) ∉ HALT	non-RE	because not recursive
ETM	i ⊆ N s.t. L(Mi) = ∅	non-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	ɸi,j(x)=(x!=j)?F:Mi(j), solve EQ(ɸ,∅)
co-EQTM	(i,j) ∉ EQTM	non-RE	ɸi,j(x)=(x!=j)?T:Mi(j), solve NEQ(ɸ,Ʃ*)

The problem sets are on github classroom. An invitation is posted in our Slack channel for each assignment.

• Problem Set 1: Review of proofs PDF
  Will be submitted by GitHub Classroom. Please follow directions to enroll.
  However please get started on this now; there will be a review of Python homework coming up quickly as well.
  Due: Friday 26 Jan (midnight Miami time)
  Hint: DL & run this code
• Problem Set 2: Deterministic Finite Automata.
  Install Jupyter notebook along with all of Anaconda and Jupyter Notebook.
  Edit the notebook file there and submit. The name must not change.
  Due: Friday 9 February.
• Problem Set 3: Nondeterministic Finite Automata.
  Edit the notebook file there and submit. The name must not change.
  Due: Friday 16 February.
• Problem Set 4: Regular Languages and Regular Expressions
  Edit the notebook file there and submit. The name must not change.
  Due: Friday 23 February.
• Problem Set 5: Regular expressions in Python
  Due: Friday 1 March.
• Problem Set 6: Context Free Grammars
  Due: Friday 8 March.
  Grace Period: until Wednesday, March 20.
• Problem Set 7: Turing Machines
  Due: Friday 5 April.
• Problem Set 8: Decidable Languages
  Due: Friday 19 April.
  Grace Period: until Wednesday, April 24.
• Problem Set EC: NP-Completeness
  Due: Monday 29 April.
  Credit towards previous assignments. Lateness policy applies to points.

Errata:

Problem Set 1:
-- none yet ---

Problem Set 2:
-- none yet ---

Problem Set 3:
-- none yet ---

Problem Set 4:
    The git-hub repository is called Project 5.

Problem Set 5:
-- none yet ---

Problem Set 6:
-- none yet ---

Problem Set 7:
    The signature might be ojo.
    The two tape solution to the w&w must be linear time.
    
Problem Set 8:
-- none yet ---   
 
Problem Set EC:
-- none yet ---

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, rebuttal to Lady Ada Lovelace.
• 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)
• Norbert Weiner, The Human User of Human Beings (1950)
• Michael Rabin and Dana Scott, Finite Automata and Their Decision Problems (1959) Introduced nondeterminism.
• G. Spencer Brown, The Laws of Form. (1969)

Understanding Computation

• Michael Rabin interviewed about nondeterministic finite automata.
• Steven Hazel at Hackerdashery
  • #1: What is math computer science.
  • #2: P vs. NP and the Computational Complexity Zoo,
• Math Has a Fatal Flaw by Veritasium.
• The Bit Player, Documentary about Claude Shannon (email me for the link)

Programming References

• Python tutorial from the official Python site.
• Scipy Lectures, including Python tutorial and numpy.
• Jupyter Markdown
• HTML Entity Chart
• My class notes on Python
  • defs/execution model
  • classes/inheritance
  • iterators/mutability

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
• The Story of Shor's Algorithm, Peter Shor
• A Brief History of Superconducting Quantum Computing, Steven Girvin

Other References

• The Jacquard Loom, invented 1804.
  • A working example at the Paisley Museum in Scotland.
  • Jacquard fabrics
  • Sample book at the George Washing University.
• Charles Babbage's Analytical Engine, of Ada Lovelace fame.
• The phone system, creator of unix for a reason
  • Historical: relays and wires.
  • Switches according to the phone company
• Dr Nim
• How to Play Dr Nim

Other classes

• Tom Murtagh at Dartmouth.
• Mike Sipser at MIT.