Computer Science 427 Homepage

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.

Join the Slack channel, csc-courses.slack.com#csc427-232. 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.
There maybe reading assignments from texts other than the class text.
We have a csc427-232 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.
Our TA is Jamie Deng jdeng@cs.miami.edu
Grades are 30% final, 30% midterm, 40% problem sets.
Midterm Date: Wednesday 1 March. In class.
Final Exam Date: ~~Friday 5 May, 11:00–1:30.~~
Final Exam Replaced with a Final Project: Wednesday 3 May – Monday 8 May.

Class notes for CSC427 Introduction to the Theory of Computation.

Day-by-Day
- Day 1: classes 1–4, 18–25 of January, 2023.
- Day 2: classes 5–10, 27 of January–8 of February, 2023.
- Day 3: classes 11–18, 10–27 of February, 2023.
- Day 4: classes 20–26, 3–24 of March, 2023.
- Day 5: classes 27–29, 27–31 of March, 2023.
- Day 6: classes 30–33, 3–10 of April, 2023.
- Day 7: classes 34–40, 12–26 of April, 2023.
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, and can be applied to many models of computation.
- Understanding nondeterminism:
  - Computational — The Finite Automata can multiple outgoing arrows for a letter, even none. And epsilon moves can advance the state without consuming a letter. The accepting criteria is asymmetric, accept if there exists an accepting computation. It does not matter if there are also non-accepting computations.
  - Oracle — for the case of a string in the language, when we encounter a choice, we consult an oracle, and the oracle provides us an answer that can lead us to an accepting state. If the string is not in the language the oracle answers but it does not matter how it answers, it can never lead us to an accepting state. While a non-accepting computation is generally no proof that the string is not in the language, in this model, it is. For it there was an accepting computation, the oracle promises to produce it. The oracle can produce any accepting computation, and not always the same one, if there are many accepting computations.
  - Search/Multiple-worlds — All computation paths are tried, either serially or in parallel. In parallel, the Finite Automata clones itself in multiple worlds, and a great many worlds may be needed, but the computation time of any clone is unaffected. If serially, then the cost of searching all computations can be exponential. If the string in in the language, the computation can be provided as proof. That the search was exhaustive, means that not finding a path is proof that the string is not in the language. Whether or not this is a compact a representation as providing a computation path to verify, is a matter of opinion.
- 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
- All Regular Languages are CFL's.
- Languages which are not Context Free: Pumping Lemma for CFL's
- Closure properties of CFL's: Union, Concatenation, Star
- Non-closure properties of CLF's: not by complementation and not by intersection.
Midterm: Wednesday 1 March.
- Previous midterms:
- Exercises assigned:
  - Exercise 1.29 on the pumping lemma.
  - Exercises 2.3, 2.4, and 2.6 or writing CFGs.
- Midterm 2023 results
  - Midterm Histogram
  - Average: 17
  - Standard Deviation: 5
  - Median: 18
- Concluding remarks on CFLs.
Turing Machines and Computability
- Concepts, formalism, and example programs.
- Decidability and Recognizability
- Variants:
  - multitape turing machines
  - nondeterministic turing machines
  - enumerators.
- Properties of Recursive and Recursive Enumerable.
- 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 undecidability of the halting problem.
- Summary of decidability and undecidability
- Decidable: {T, F}; R.E.: {T,⊥}; co-R.E.: {F,⊥}.
- 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

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)	co-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	co-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	co-RE	because not recursive
E_TM	i ⊆ N s.t. L(M_i) = ∅	co-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(ɸ,Ʃ^*)

Problem Sets for CSC427 Introduction to the Theory of Computation.

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

Problem Set 1: Python Exercises
- Due: Friday, January 27.
Problem Set 2: Deterministic Finite Automata
- Due: Friday, February 3.
Problem Set 3: Nondeterministic Finite Automata
- Due: Friday, February 10.
Problem Set 4: Closure Properties of Regular Languages
- Due: Friday, February 17.
Problem Set 5: Regular Expressions
- Due: Friday, February 24.
Problem Set 6: Turing Machines
- Due: Friday, March 31.
Problem Set 7: Decidable Languages
- Due: Friday, April 14.
Problem Set 8: NP Completeness
- Due: Friday, April 28.

Errata:

Problem Set 1:
-- none yet ---

Problem Set 2:
ex_1_6l_test = (['1','11','','00','01010'],['0','1000','111000'])
ex_1_6i_test = (['','1','11','101','11101'],['0','01','100','110','10001'])

Problem Set 3:
-- none yet ---

Problem Set 4:
-- none yet ---

Problem Set 5:
-- none yet ---

Problem Set 6:
-- none yet ---

Problem Set 7:
Exercise A, m1_e definition, change accept set to: 'accept':{'q3'}

Exercise A, about the 14th line in the function basic_test, 
   change to: if not de.decide_empty():

In the basic_test, add/change to the red words:

    correct += 1
    p = de.prove_not_empty()
    m = SimpleFiniteAutomata(m1)
    if m.compute(p):
        print(f'm1:\tcorrect: the language accepts {p}')
        correct += 1

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, 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, 2023 (232)
MWF 10:10–11:00 AM
Whitten LC 190

Email: burt at cs miami edu

News Syllabus Notes Decidability Problem Sets References

General

CSC427-C: Introduction to the Theory of Computation

Prof. B. Rosenberg Spring Semester, 2023 (232) MWF 10:10–11:00 AM Whitten LC 190 Email: burt at cs miami edu

News Syllabus Notes Decidability Problem Sets References

General

Prof. B. Rosenberg
Spring Semester, 2023 (232)
MWF 10:10–11:00 AM
Whitten LC 190

Email: burt at cs miami edu