EECS2001 EECS 2001: Introduction to the Theory of Computation
                                                      Jeff Edmonds: 2025 (C)    ACW 004


Jeff, Readme, Marking, Times, Dates, Description,
Enrolling, Mental Health, EClass, Zoom, Solutions

Hi All,
I am excited to get passionate about Theory of Computation with you.
Though it is REALLY important to come to class, sit in the front, and talk to me,
I am going to be bad and hold the first class (Thur Sept 4) by Zoom.
I am letting you know now incase you are buying plane tickets.
Also we will not have a tutorial on Fri Sept 5.

Topics (VIDEOS BELOW) Slides Ques Sol 2017 Sol
Intro
Turing Machines and other models
DFA Machines
DFA Classes
Context Free Grammars
Countable and Uncountable Infinite
Undecidability
Reductions For Uncomputability
No Proof System for Number Theory
NP-completeness
Machine Learning

Request: Jeff tends to talk too fast. Please help him go pole pole slowly.


Texts: (No text is required.)
       - Some online notes that I (Jeff Edmonds) wrote years ago when teaching this course.
       - Michael Sipser. Introduction to the Theory of Computation.
       - Harry R. Lewis and Christos H. Papadimitriou, "Elements of the Theory of Computation",,
       - J. E. Hopcroft and J. D. Ullman, "Introduction to Automata Theory",, Addison-Wesley.
       - Ding-Zhu Du and Ker-I Ko. Problem Solving in Automata, Languages, and Complexity. Wiley, 2001.
       - John C. Martin. Introduction to Languages and the Theory of Computation. McGraw-Hill, 2003.
       - Daniel Solow. How to Read and Do Proofs: An Introduction to Mathematical Thought Processes. Wiley, 2002.
       - A freely downloadable book on the foundations of Computer Science is here.
       - A freely downloadable book on Discrete Math is here.
       - Veritasium - Math's Fundamental Flaw

0 Intro: (ppt)

1 Predicate Logic: (ppt) (Math1090 )
           (Before a student can understand or prove anything in mathematics, it
           is essential to first be able to represent it in first order logic.)
           Jeff's Logic Chapter, Logic Questions, & Solutions

2 Models of Computability: (ppt)
           (Historic and mathematical ways of modeling machines for computing.)

3 Deterministic Finite Automata - Machine: (ppt)
           (Useful for modeling simple machines eg coke machine.)

4 Deterministic Finite Automata and Regular Languages Classes: (ppt, longer)
           (We classify computational problems based on the amount of resources
           used to compute them.)

5 Context Free Grammars: (ppt)
           (Useful for modeling and parsing languages.)


Computing (Math 1090) (ppt):
Complexity (Math 1090) (
ppt): Classifying Computational Problems, NP, & Computable

6.0 Countable and Uncountable Infinite: (ppt)
           (There are more real numbers than fractions and the same number of
           fractions as integers.)

6.1 Halting Problem is Uncomputable: (ppt)
           (Some computational problems are solved by NO algorithms.)

6.2 Reductions For Uncomputability: (ppt)
           (Knowing that some computational problems are hard, we prove that
           others are.)

6.3 No Proof System for Number Theory: (ppt)
           (Godel proved that there is no mechanical way of proving everything in
           mathematics.)

7 NP-completeness: (ppt)
           (Reductions involve writing an algorithm for one problem from that for
           another. NP-Completeness give strong evidence that most search
           problems that industry cares about are believed to not have poly-time
           algorithms.)

99 Machine Learning Made Easy: (ppt), ML Labs
           (The basic math needed to understand machine learning)

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.