Computer Science 427 Homepage

News and Announcements for CSC427 Introduction to the Theory of Computation.

Friday, May 6: 11:00–1:30
: Final exam according to our Official Schedule; Final exam information posted in Notes.
Friday, April 29:
: Last day of class
Monday, March 21:: Midterm rubric with some answers, and histogram posted. See Notes section.
Monday, March 7:: Midterm, in class; New due dates for problem sets 4 and 5.
Monday, Feb 21:: Zoom link 97283421063/332093
Wednesday, Jan 19:: Zoom link 97283421063/332093
Tuesday, Jan 18:: Semester begins.

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-222. 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.
The course assigns problem sets — either written assignments or programming projects.
Programming assignments are in Python and Jupyter.
We will use a subversion repository to distribute and collect the problem sets. You will have a subversion login to that repository. Subversion is available for all platforms.
Grace Periods
- Three days grace.
- After which 1/3 off (~~4 to 7 days~~).
- Until a week, when its 2/3 off (~~8 to 14 days~~).
- Until a second week, when it is 5/6 off (~~15 to 21 days~~).
- 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.
- Clarified rule on March 1.
Our TA is Alexandros Ali Khan axk1168@miami.edu
Grades are 30% final, 30% midterm, 40% problem sets.
The python assignments and quantum supplements are posted to github://csc-courses/csc427-222

Class notes for CSC427 Introduction to the Theory of Computation.

The ABC of python
- The A: defs/execution model
- The B: classes/inheritance
- The C: iterators/mutability
Examples of Automata
- 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
Finite Automata
- Notation, Deterministic Finite Automata
- The class of regular languages is closed by complementation and union
- Models of nondeterminism:
  - 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.
  - Existence — A string is accepted when there exists an accepting computation. There is no concern for producing said computation. The non-existence of an accepting computation is likewise taken without concern that this be proved. For a string in the language, if existence of an accepting path is asserted, and an accepting path is given, this is the oracle model.
  - Search — Is a model where nondeterminism just speeds things up. There is an exhaustive search procedure of all computation paths. Typically, the search time is exponentially longer than the solution length. However, there exists such a search procedure which will definitely terminate and be correct as to whether the string is accepted or not. Typically, if the string is accepted, the search will deliver proof of this in a computation path.
- Concatenation, Intersection and Kleene star by NFS's
- Epsilon moves; epsilon closures.
- All NFA's can be simulated by a DFA.
- 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
- Pushdown Automata
- 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.
- The Midterm was given at this point.
- Deterministic PDA's
- Ambiguous CLF's and essential nondeterminism.
- Chomsky Normal Form
- Cocke-Younger-Kasami algorithm
- The non-determinism of PDA's, the limits of search.
Midterm: Monday 7 March.
- Material through (including) section 2.3 is on the midterm.
- Old midterms:
- Chapter 1:
  - Exercises 1.1 — 1.10.
  - Exercises 1.16 — 1.21.
- Chapter 2:
  - Exercises 2.1 — 2.4 and 2.6.
- The grading rubric and the histogram.
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.
- The undecidability of the halting problem.
- Summary of decidability and undecidability
- Additional comments:
  - Nondeterminism and search;
  - The enumerability of a search space;
  - The halting asymmetry of search.
  - Decidable: {T, F}; R.E.: {T,⊥}; co-R.E.: {F,⊥}.
- Oracle machines and relativized decidability
Complexity Theory
- Review of Big Oh notation.
- Polynomial and non-deterministic polynomial time
- Satisfiability of boolean formula, and the universal NP problem
- NP Completeness
  - Polynomial time reductions
  - k-vertex cover
  - k-clique
  - hamiltonian path
- Probabilistic computation
  - The class RP
  - The Miller-Rabin test for non-primality.
- Interactive proof systems,
  - graph non-isomorphism
- Zero knowledge proof
  - Graph Isomorphism
  - Bit commitment
  - Zero knowledge for all NP proofs
Quantum Computation
- The four horsemen:
  1. Observations
  2. Superposition,
  3. Entanglement,
  4. Reversibility, no-cloning.
- Resources
  - CSC687-A: Quantum Computing, Prof. Rosenberg (2004)
  - CSC 685/595: Quantum Cryptography for Beginners, Prof. Rosenberg (watch for upcoming editions)
  - Quantum computing, in the physics department., Prof. Nepomechie (watch for upcoming editions)
  - IBM Quantum
Final exam
- Past years final exams,
  - Semester 172 (spring 2016-2017)
  - Semester 212 (spring 2020-2021)
- Topics covered,
  - From Part 1 of the text: all the midterm topics, as well as the CFL topics after the midterm.
  - From Part 2 of the text: chapters 3, 4, 5 except Posts Correspondence Problem in 5.2.
  - From Part 3 of the text: chapter 7 and the following topics from chapter 10,
    - Probabilistic computation, 10.2 (the RP class co- primality)
    - Interactive proof systems, 10.4
  - Not included, zero-knowledge proofs and quantum computing.

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.

Problem Set 0: Up and running, Due: Friday 21 January
1. Join the Slack channel. Emails cs.miami.edu, miami.edu, or umaimi.edu are free to join.
2. Install Anaconda
  1. Check that it works by |jupyter notebook| at the command line (don't include the vertical bars)
  2. Your browser should now come to the foreground with the Jupyter work panel.
  3. Choose New Python3. In the box type |2+2| (no vertical bars) and Shift-Return
  4. If you get "4" then it's working.
  5. Have fun with some small python programs.
3. Install subversion and check-out the class repository
4. Notes for Mac users. Install subversion from homebrew. So please install homebrew.
5. Notes for Windows users:
  1. For this class, you do not need WSL, as might be recommended for other courses in CSC. You can install Anaconda for Windows and launch Jupyter from the Anaconda Navigator panel.
  2. Install TortoiseSVN, which integrates SVN into you right-click file menu. Subversion is standard across plateforms, but whether file names respect capital letters or not, is not. Please stick with the capitalization as requested.
6. Watch the video Math Has a Fatal Flaw by Veritasium.
7. Answer these questions:
  1. Name a couple intuitionists and a couple formalists.
  2. Who did Kurt Godel speak to at the conference?
  3. What is a Von Neumann architecture machine?
  4. Are there any commonly used computers that follow other architectures? What architecture and what device?
  5. What problem was Turing trying to solve?
  6. Is Conway's Game of Life Turing Complete?
  7. Is the game of chess Turing Complete?
Problem Set 1: Up and Running
- On GitHub
- Copy [repo]/class/proj1/* to [repo]/[your-folder]/proj1/.
- svn add and commit as an initial commit.
- Run jupyter notebook to complete the tasks in proj1.ipynb.
- Due: Wednesday 2 February
Problem Set 2: Implementing a Finite Automata
- On GitHub
- Copy [repo]/class/proj2/* to [repo]/[your-folder]/proj2/, complete and commit.
- Due: Wednesday 9 February
Problem Set 3: Machine Combinations
- On GitHub
- Copy [repo]/class/proj3/proj3.ipynb to [repo]/[your-folder]/proj3/, complete and commit.
- Due: Wednesday 16 February
Problem Set 4: Nondeterminism
- On GitHub
- Copy [repo]/class/proj4/proj4.ipynb to [repo]/[your-folder]/proj4/, complete and commit.
- Due: ~~Wednesday 24~~ Monday 28 February
Problem Set 5: Regular expressions
- On GitHub
- Copy [repo]/class/proj5/proj5.ipynb to [repo]/[your-folder]/proj5/, complete and commit.
- Note that this problem set is about the re package of python. Regular expressions are on the midterm.
- Due: Friday 11 March
Problem Set 6: Turing Macines
- On GitHub
- Copy [repo]/class/proj6/proj6.ipynb and turing_machine_sim.py to [repo]/[your-folder]/proj6/.
- Complete and commit.
- Due: Friday 1 April
Problem Set 7: Multitape Turing Macines
- On GitHub
- Copy [repo]/class/proj7/proj7.ipynb, proj7_util.py and turing_machine_sim.py to [repo]/[your-folder]/proj7/.
- Complete and commit.
- Due: Wednesday 13 April
Problem Set 8: P and NP Complexity Classes
- On GitHub
- Copy [repo]/class/proj8/proj8.ipynb to [repo]/[your-folder]/proj8/.
- Complete and commit.
- Due: Friday 22 April
Problem Set 9: Reductions and NP Completeness
- On GitHub
- Copy [repo]/class/proj9/proj9.ipynb to [repo]/[your-folder]/proj9/.
- Complete and commit.
- Due: Friday 29 April

References for CSC427 Introduction to the Theory of Computation.

Versions of the course on the web

This course derives from MIT 18.404. That course is available under a Creative Commons License from MIT's Open Courseware (OCW) (18-404JF20). The OCW 18.404 version differs from CSC427 in that CSC427 is taught from an experimental viewpoint, emphasizing experiences in Python over formal proof. OCW 18.404 is a math course, CSC427 is a science course.

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)
Michale Rabin and Dana Scott, Finite Automata and Their Decision Problems (1959)
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)

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

Programming References

Python tutorial from the official Python site.
Scipy Lectures, including Python tutorial and numpy.
Jupyter Markdown
HTML Entity Chart

CSC427-C: Introduction to the Theory of Computation

Prof. B. Rosenberg
Spring Semester, 2022 (222)
MWF 10:30–11:20 AM
Aresty 103

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, 2022 (222) MWF 10:30–11:20 AM Aresty 103 Email: burt at cs miami edu

News Syllabus Notes Decidability Problem Sets References

General

Prof. B. Rosenberg
Spring Semester, 2022 (222)
MWF 10:30–11:20 AM
Aresty 103

Email: burt at cs miami edu