Photo from BBC News article by Prof. Jack Copeland

CSC427-D: Introduction to the Theory of Computation
formerly CSC527

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

Apr 25:

Solution to read compound state posted.

Apr 16:

Problem Set 10 posted. Due Apr 22.

Apr 9:

Problem Set 9 posted. Due Apr 15.

Mar 28:

Problem Set 8 posted. Due Apr 8.

Mar 28:

Problem Set 7 posted. Due Apr 1.

Mar 28:

Problem Set 6 posted. Due Mar 25.

Feb 18:

Midterm: how does Wed, March 4th work? To discuss in class.

Feb 18:

Problem Set 5 posted. Due Feb 25.

Feb 11:

Problem Set 4 posted. Due Feb 18.

Feb 5:

Problem Set 3 posted. Due Feb 11.

Jan 23:

Problem Set 2 posted. Due Feb 3.

Jan 14:

Problem Set 1 posted. Due Jan 21.

Jan 12:

Important dates:

• Jan 19, Holiday.
• Mar 7–15, Spring Recess
• Apr 24, Classes end
• Apr 29, Final exam

Jan 12:

Semester begins. Welcome!

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.

• The assigned textbook is Introduction to the Theory of Computer, Third Edition by Mike Sipser.
• Please follow us on twitter/csc_517 (same as 317 twitter feed)
• Some course notes will be found on the Csc427 blog.
• The course assigns weekly problem sets, due on Wednesdays. It is very important to do the homeworks.
• There maybe reading assignments from texts other than the class text.
• Our grader is Parul Maheshwari, p.maheshwari _at_ umiami.edu.
• No late homeworks accepted after the last day of classes.
• Midterm: Monday, TBA.
• The final will be in MM 200, Wednesday, April 29, 11:00am — 1:30pm.
• Grades are 40% final, 30% midterm, and 30% homework.

Writing Credit

Three essays, each at least 1500 words. Some possible topics/books are (for books, read and report):

• The origin of algorithms. A historical paper. There is actually a book, History of Algorithms ... that might guide you.
• The origins of computation theory. There is a nice book by Matiyasevich and Martin Davis called "Hilbert's 10th Problem".
• G Spencer Browns, "The Laws of Form". This book seems to be very updated since I read it.
• The need to break military codes drove forward the construction of computers during World War II. Among the early computers were the Colossus designed by Tommy Flowers, to break German Navel Codes (Tunny) and Turing's Bomb, to break army and high command codes (Enigma). These were really the first computers ever built.
• A science fiction short story about algorithms, computers, etc. If not original, you can do an analysis of some Sci-Fi books like The Diamond Age, or Snow Crash.
• I've recently been reading Norbert Wiener's "The Human Use of Human Beings", and that might be of interest to some of you.
• Yardley's "American Black Chamber" is another interesting book about the start of America's secret interception, code breaking activities.
• The Theory of Numbers by Richard Dedekind. A math book about what a real number means. It's here because this was the start of the questions that lead to the need to think more about the nature of proof, language and computation.

Please write me with your proposed topics, if you elect writing credit. One paper must be done before the midterm, and the other two before reading days.

Class notes for CSC427 Introduction to the Theory of Computation.

• Introduction
  • An historical perspective. See the blog posting.
• Finite Automata
  • Deterministic
  • Nondeterministic
  • Regular Expressions
  • Pumping Lemma and non-regular languages
• Context Free Languages
  • Grammars
  • Ambiguity
  • Push down automatas
  • Deterministic PDA's and ambiguity
  • Closure properties for CFL's
  • Pumping Lemma and non CF languages
• Turning Machines
  • Definition and programming
  • Multitape and nondeterministic
  • Enumerators
  • Turing decidable, a.k.a. recursive
  • Turing recognizable, a.k.a. recursively enumerable
  • Decidability of regular languages and CFL's.
  • Decidability of equality of regular languages and emptiness for a CFL.
• Midterm
• Undecidability
  • Countable and uncountable infinities
  • The diagonalization method
  • non-decidability of membership.
  • non-recognizability of non-membership
  • reductions
  • the Halting problem is not decidable
• Undecidability of Number theory
  • Mapping reductions
  • see Standford's CSC103 notes
  • Logical theories
  • Reduction of the Halting problem to number theory
  • Godel encoding of a computation into number theory
• Complexity Theory
  • Time complexity
  • Nondeterministic TM
  • The classes NP and co-NP
  • Polynomial time reduction and NP completeness
  • SAT is NP complete
  • Clique, Hamiltonian Path, and Vertex Cover are NP complete
• Additional important models
  • Probabilistic computation and the class BPP
  • Primality and classes RP and co-RP
  • The class ZPP
  • Interactive proof systems and the class IP
  • Zero Knowledge protocols

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)	co-RE
ATM	(i,j) ⊆ N × N s.t. Mi(j) halts accepts	RE	run j on Mi
co-ATM	(i,j) ∉ HALT	co-RE
HALT	(i,j) ⊆ N × N s.t. Mi(j) halts	RE	run j on Mi
co-HALT	(i,j) ∉ HALT	co-RE
ETM	i ⊆ N s.t. L(Mi) = ∅	RE	Rice's theorm
co-ETM	i ∉ETM	co-RE	∃ x s.t. (x,i) ∈ ATM
EQTM	(i,j) ⊆ N × N s.t. L(Mi)=L(Mj)	non-RE	¬(RE ∪ co-RE)
co-EQTM	(i,j) ∉ EQTM	non-RE

Problem Sets for CSC427 Introduction to the Theory of Computation.

• Problem Set 1: due Wed Jan 21
  • Exercises 0.1 through 0.7
  • Problem 0.11
• Problem Set 2: due Wed Feb 4
  • Exercises 1.1, 1.2, 1.4-a, 1.4-c, 1.5-d and 1.5-e
  • Exercise 1.6
  • Exercise 1.7
  • Give a regular expression for the Language of Dr. Nim.
• Problem Set 3: due Wed Feb 11
  • Exercises 1.16, 1.17, 1.18 (but only 7 of the 14 languages of Exercise 1.6, your choice), 1.19, 1.20, 1.21 and 1.24.
  • Problem 1.37.
• Problem Set 4: due Wed Feb 18
  • Problems 1.46 and 1.49
  • Exercises 2.1, 2.2, 2.4, 2.5. 2.16 and 2.17
• Problem Set 5: due Wed Feb 25
  • Exercise 2.11
  • Problems 2.20, 2.30, 2.31, 2.32
  • Exercises 3.1, 3.2
• Problem Set 6: due Wed March 25
  • Exercise 4.6, 4.7, 4.8, and 4.9.
  • The three problems of Part A on my blog post: Programming and Turing Machines
• Problem Set 7: due Wed April 1
  • Exercises 5.1, 5.2, 5.3, 5.4.
  • Problems 5.12, 5.13, 5.14, 5.15.
• Problem Set 8: due Wed April 8
  • Problems 6.11, 6.13 and 6.28.
  • The problems of Part B on my blog post: Programming and Turing Machines
  • The extra credit part is due in two weeks.
• Problem Set 9: due Wed April 15
  • Exercises 7.1, 7.2, 7.4, 7.5, 7.6 and 7.7.
• Problem Set 10: due Wed April 22
  • Exercises 7.9, 7.13, 7.14, 7.18, 7.22 and 7.24.

Solutions:

• Solution to the Read Compound state.
  • Diagrams
  • Explanations for the diagrams
  • Errata: there are two X5's in the final R drawing. Replace the second with X6.
• Solution to the Write Compound state.
  • Diagrams
  • Explanations for the diagrams

References for CSC427 Introduction to the Theory of Computation.

• History of Computing Hardware at wikipedia