Lecture 18
(TM variants), 3/29/06
Concepts, definitions (in italics):
- Examples of TMs and TM diagrams from the book
- Two ways that TMs "remember" -- special symbols on tape, different states.
-
Simulating a TM that allows non-writing transitions with one that does not.
-
Simulating a TM that allows non-reading transitions with one that does not.
- Simulating a TM that allows non-moving transitions with one that does not
(requires adding new states).
- Multihead or multitape Turing Machine (with k heads/tapes) - new transition definition,
3k+2 elements per tuple.
- The idea of simulating one machine with another.
- Simulating multitape TMs with regular TMs
- Universal Turing Machine.
Reading:
- Chapter 3.1 finish
- Chapter 3.2 through corollary 3.15 (up to Nondeterministic TMs)
- The "Links" section of the course web site has a link to my paper
about the Church-Turing thesis and about statement 3 of chapter 3.1
- The deterministic multitape TM simulator is now available
in the "Links" section of the CSE237 web site.
Play with it -- you will need it for the homework!
Skills:
- Know new definitions, understand new concepts.
- Given a set-based description of a TM (states, transitions, etc), create a
diagram for a TM
- Given an description (algorithm) for a TM, be able to follow a diagram for a
TM
- Be able to design a simple TM
either as pseudocode or as a transition diagram.
- What does transition function for a Multitape TM look like?
- What does a configuration of a Multitape TM look like?
- How to encode (represent) a configuration of a Multitape TM on a single-tape TM?
- What role do configuration encodings have in simulations of one machine with
another?
Notes:
- TMs always have exactly one state, even when they have many tapes and/or reading heads.
- TM inputs/outputs can be anything that is encodable as a string -- including
a description of another TM.
- Sigma (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).
- We can always increase Q, the set of states.