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}, (0k : 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: