ESR's Dr Nim, a Finite State Automata game

CSC427-C: Introduction to the Theory of Computation

Monday, Jan 13:

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-252. 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-252 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 30% final, 30% midterm, 40% problem sets.
• Midterm Date: In class.
• Final Exam Date:

• Finite Automata
  • Notes from the previous semester:
    • 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
  • 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
  • Notes from the previous semester:
    • Day 4, during which context free languages are discussed.
  • 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
• Turing Machines and Computability
  • Notes from the previous semester:
    • Day 5, during which Turing Machines are discussed.
    • Day 6, during which forms of undecidability are discussed.
  • 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
  • Notes from the previous semester:
    • Day 7, during which NP Completeness and PPT machines are discussed.
    • Day 8, during which IP and Zero-knowledge is discussed.
  • 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

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: Boolean Logic
  See Slack for github classroom invite.
  Due: Friday, 31 January
• Problem Set 2: Deterministic Finite Automata
  See Slack for github classroom invite.
  Due: Wednesday, 12 February

Errata:

Problem Set 1:
-- none yet ---

Problem Set 2:
-- 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.