Study points for Test 3
Concepts
 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 and a language means
 What accepting and a language means

Simple closure properties of recursive and recursively enumerable languages
 Simple 1tape TM examples using component machines
 Simple multitape TM examples via descriptions
 2tape simulation of 2way 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

Turing Machines

TM Computations

TM Extensions

Universal TM / Halting Problems

TM Undecidable Problems
Relevant Textbook Material

4.1: all

4.2: all

4.3: all, but focus on a conceptual understanding
of a multitape 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

5.3: all

5.4: all