**Lecture 15 (TM Diagrams), 10/25/17**

**Concepts, definitions (in italics):**

·
The set of Turing-decidable languages is a
subset of Turing-recognizable languages.

·
If on first cell, a TM will just stay there
instead of moving left.

· While the TM tape is infinite, its contents at any point is finite (followed by infinitely many blanks).

· How would one design TM that decides {w#w}?

· Two ways that TMs "remember" -- special symbols on tape, different states.

· S (input alphabet) is fixed (it represents the language we are trying to decide/recognize).

· We can always increase Gamma, the tape alphabet (e.g. with markers of all kinds), as long as we increase by a finite amount.

· We can always increase Q, the set of states, as long as we increase by a finite amount.

·
Notation for *TM diagrams*

·
Diagrams for {w#w}, (0^{k}
: k is a power of 2}

·
Replacing a TM that allows *non-writing
transitions* – just writes the same thing it reads!

·
TMs can also be used to *compute* functions,
where they accept all inputs and leave the output string on the tape when done

**Reading:**

· Chapter 3.1 to the end

**Skills:**

· Know new definitions, understand new concepts.

· Given a diagram for TM, create a formal description for it (states, gamma, etc, etc)

· Given a formal description of a TM, create a diagram for it

· Given an (algorithmic) description of a simple TM, be able to follow a diagram for this TM

· Be able to design a simple TM either as pseudocode or as a transition diagram.

**Notes:**