ESR's Dr Nim, a Finite State Automata game

CSC427-C: Introduction to the Theory of Computation

Friday, February 27

Midterm (in class)

29–6 April–May:

Final exam (TBA)

Monday 27 April:

Last day of class

7–15 March:

Spring Recess

Monday 19 Jan:

Holiday

Monday 12 Jan:

First day of class

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-262. 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-262 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:
  • Contact the "help desk" on slack.
• Grades are 40% final, 30% midterm, 30% problem sets.
• Midterm Date: In class.
• Final Exam Date:

• Written notes:
  • Day 1, during which computation is discussed.
  • Day 2, during which finite automata are dicussed.
  • Day 3, during which kleene algebras are discussed.
  • Day 4, during which regular expressions and non-regular languages are discussed.
  • Day 5, during which context free languages are discussed.
  • Day 6, during which Turing Machines are discussed.
  • Day 7, during which the halting problem is discussed.
  • Day 8, during which P, NP and co-NP 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
  • Context Free Grammars
  • Computation and Kleene Algebras
  • 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.
  • Languages which are not Context Free: Pumping Lemma for CFL's
  • Decision for Context Free languages
    • Chomsky Normal Form and the Cocke-Younger-Kasami algorithm.
  • inherent ambiguity
• Turing Machines and Computability
  • Concepts, formalism, and example programs.
    • A turing machine program to recognize a^ib^ic^i
    • Other examples of Turing Machine programs
  • Variants:
    • nondeterministic turing machines
    • multitape turing machines
    • enumerators.
    • universal turing machines
  • The undecidability of the halting problem.
  • The arithmetic hierarchy
    • Reductions
    • Emptiness and non-Emptiness
      • Recursive, Σ₀
      • Recursive Enumerable, Σ₁
      • co-Recursive Enumerable, Π₁
    • EQ (Π₂) and non-EQ (Σ₂)
    • Rice's Theorem
    • REG is Σ₃
  • Summary of decidability and undecidability
• Complexity Theory
  • Review of Big Oh notation.
  • Polynomial and non-deterministic polynomial time
  • Decidable languages,
    • Acceptance for Finite Automata
    • Emptiness of Regular Languages
    • Equality of Regular Languages
    • Acceptance for Context Free Grammars
    • Emptiness of Context Free Languages
  • NP Completeness
    • Satisfiability of boolean formula
    • Polynomial time reductions
    • k-clique
    • hamiltonian path
    • Cook-Levin theorem
  • Interactive Proof systems and Zero Knowledge
    • The class IP
    • A IP proof of graph non-isomorphism
    • Definition of knowledge
    • Zero Knowledge proof of graph isomorphism
    • All NP problems of ZK proofs

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(ɸ,Ʃ*)

Midterm review

• The material of the three projects is on the midterm.
• The class notes Days 1 through 4 are on the midterm, except the pumping lemma.
• From class notes Day 5
  • Basic definition of context free grammars is on the midterm.
  • The closure properties of CFL is on the midterm.
• Basic context free grammar skills,
  • Exercises 2.3 and 2.4 (third edition)
  • Convert to a CFG the three regular expressions in exercise 1.19 (third edition)

Previous midterms

• spring 2024 midterm
• spring 2022 midterm
• spring 2021 midterm
• spring 2020 midterm
• spring 2017 midterm

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

• Problem Set 1: Deterministic Finite Automata
  See Slack for github classroom invite.
  Due: Friday, 30 Jan, 2026
• Problem Set 2: Nondeterministic Finite Automata
  See Slack for github classroom invite.
  Due: Friday, 13 Feb, 2026
• Problem Set 3: Regular expressions
  See Slack for github classroom invite.
  Due: Monday, 23 February.
• Problem Set 4: Context Free Languages
  See Slack for github classroom invite.
  Due: Monday, 16 March.
• Problem Set 5: Turing Machines
  See Slack for github classroom invite.
  Due: Monday, 30 March.
• Problem Set 6: Decidable Languages
  See Slack for github classroom invite.
  Due: Monday, 13 April.
• Problem Set 7: NP-Completeness
  See Slack for github classroom invite.
  Due: Monday, 27 April.

Errata:

Problem Set 1:
-- none yet ---
Problem Set 2:
-- none yet ---
Problem Set 3:
-- none yet ---
Problem Set 4:
-- none yet ---
Problem Set 5:
   Due date was said to be Friday and the following Monday.
   Corrected to the more permissive Monday
Problem Set 6:
-- none yet ---
Problem Set 7:
-- 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.