Computer Science 427 Homepage

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.
  - Class notes
- 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.
  - A turing machine program to recognize a^ib^ic^i
  - Other examples of Turing Machine 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 probabilistic proof systems 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
A_FA	(i,j) ⊆ N × N s.t. FA_i accepts j	decidable	run DFA
E_FA	i ⊆ N s.t. L(FA_i) = ∅	decidable	non-det guess element in complement
EQ_FA	(i,j) ⊆ N × N s.t. L(FA_i) =L(FA_j)	decidable	emptiness of symmetric difference
A_CFG	(i,j) ⊆ N × N s.t. PDA_i accepts j	decidable	Chomsky Normal Form
E_CFG	i ⊆ N s.t. L(CFG_i) = ∅	decidable	marking algorithm
X	x ∉ X, where X is decidable	decidable
co-EQ_CFG	(i,j) ∉ EQ_CFG	RE	∃ x s.t. (x,i) ∈ A_CFG etc
EQ_CFG	(i,j) ⊆ N × N s.t. L(PDA_i) = L(PDA_j)	non-RE	because not recursive
A_TM	(i,j) ⊆ N × N s.t. M_i(j) halts accepts	RE	run j on M_i
co-A_TM	(i,j) ∉ HALT	non-RE	because not recursive
HALT	(i,j) ⊆ N × N s.t. M_i(j) halts	RE	run j on M_i
co-HALT	(i,j) ∉ HALT	non-RE	because not recursive
E_TM	i ⊆ N s.t. L(M_i) = ∅	non-RE	Rice's theorm
co-E_TM	i ∉E_TM	RE	∃ x s.t. (x,i) ∈ A_TM
EQ_TM	(i,j) ⊆ N × N s.t. L(M_i)=L(M_j)	non-RE	ɸ_i,j(x)=(x!=j)?F:M_i(j), solve EQ(ɸ,∅)
co-EQ_TM	(i,j) ∉ EQ_TM	non-RE	ɸ_i,j(x)=(x!=j)?T:M_i(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
Problem Set 3: Nondeterministic Finite Automata
See Slack for github classroom invite.
Due: Friday, 21 February
Problem Set 4: Regular Expressions
See Slack for github classroom invite.
Due: Wednesday, Mar 5
Problem Set 5: Context Free Grammars
See Slack for github classroom invite.
Due: Wednesday, Mar 19.
Problem Set 6: Turing Machines
See Slack for github classroom invite.
Due: Wednesday, April 2
Problem Set 7: Turing Machines written assignment
See Slack for github classroom invite.
Due: Monday, April 14.

Errata:

Problem Set 1:
-- none yet ---

Problem Set 2:
-- none yet ---

Problem Set 3:
-- none yet ---

Problem Set 4:
-- none yet ---

Problem Set 5:
-- none yet ---

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

The best computing toys

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.

CSC427-C: Introduction to the Theory of Computation

Prof. B. Rosenberg
Spring Semester, 2025 (252)
MWF 10:10–11:00 AM
Witten LC 110

Email: burt at cs miami edu

News Syllabus Notes Decidability Problem Sets References

CSC427-C: Introduction to the Theory of Computation

Prof. B. Rosenberg Spring Semester, 2025 (252) MWF 10:10–11:00 AM Witten LC 110 Email: burt at cs miami edu

News Syllabus Notes Decidability Problem Sets References

Prof. B. Rosenberg
Spring Semester, 2025 (252)
MWF 10:10–11:00 AM
Witten LC 110

Email: burt at cs miami edu