Study points for Test 3
- TM formal definition
- What is a TM configuration
- I won't ask the formal definition of ⊢,
but you should be able to carry out computations in simple examples.
- What it means for a TM to compute a function
- What deciding a language means
- What accepting a language means
Simple closure properties of recursive and recursively enumerable languages
- Simple 1-tape TM examples using component machines
- Simple multi-tape TM examples via descriptions
- 2-tape simulation of 2-way infinite tape
- NTM acceptance: what does this mean.
- NTM simulation by TM.
What are the "computation sequence strings"
and what do you do with them.
- Universal TM: conceptual understanding only, describe the idea
- Halting problem: statement and proof
- Problem Reduction: what is it, what does it achieve
- Sample basic reductions: something you've seen in class
Relevant Online Notes
Universal TM / Halting Problems
TM Undecidable Problems
Relevant Textbook Material
4.3: all, but focus on a conceptual understanding
of a multi-tape TM simulated by a standard TM.
4.5: all, but omit definition 4.5.2 and anything concerning
deciding a language or
computing a function
with an NTM.
5.2: The book's encoding is different from mine, so get
a conceptual understanding of how the Universal TM simulates the behavior of a TM