**Lecture 14 (Turing Machines), 10/23/17**

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

*Turing machine*: another finite state machine*Infinite tape*-- While the TM tape is infinite, its contents at any point is finite (followed by infinitely many blanks).*Blanks*are part of the tape alphabet but not of input alphabet; initially, all cells right of input string are blanks.*Deterministic Turing machine*: formal definition (p. 168)*2**halting**states:**accept**,**reject*- Computation finishes when we reach one of these two
states –
*accept*or*reject*(NOT when we finish reading input) *TM transitions**Can move either right or left**TM configurations*- (current state, tape contents, head position)
*Initial configuration*for TM computations.- The textbook’s shorthand notation for configurations
*Every TM computation either**terminates**/**halts*(at which point it either accepts or rejects), or*goes into an infinite loop.*- A
*language*of a TM = set of string it*accepts* - TM
*decides*a language*L*– it terminates for all inputs; all w in L are*accepted*, all*w*not in*L*are*rejected* - Turing
*decidable*language*L*– there exists TM which decides L - TM
*recognizes*a language*L*– all w in L are*accepted*, but*w*not in*L*may be rejected or may never halt (go into infinite loop) - Turing
*recognizable*language – there exists TM which recognizes L - There was no distinction between deciding and
recognizing before, because those machines always terminated. But
for Turing Machines, this IS an issue.
*Example: Halting problem*: Given a description of a TM*M*and input string*w*, will*M*halt on*w*?- We will prove that the halting problem is
*undecidable*; i.e. there exists no algorithm that will always answer YES or NO correctly - However, this problem is recognizable; i.e. one can
simulate a Turing Machine and wait for it to terminate.
- LANGUAGES VS.
YES/NO PROBLEMS
- YES/NO
problem is a question of the form:
*given X, is it true that X ….* - One-to-one
mapping between languages and yes/no problems
- Example: a Turing machine deciding w#w
(not context free) [p. 167]
- Any problem that can be solved with any computer can be
solved with a TM.
- Despite what our textbook says, they CANNOT do
everything that computers do, because they are limited to the
*mathematical*notion of computation. - Meaning: (a) every computation starts in the initial
configuration, and (b) computations proceed in black-box fashion, with no
interaction with outside world

**Reading:**

- Chapter 3.1 through page 170

**Skills:**

- Know new definitions, understand new concepts.
- What does it mean that a TM
*accepts*a string?*rejects*a string? - Understand the difference between a decidable and a
recognizable language
- Given a configuration and the transitions, figure out which
transition applies?
- Given a configuration and a matching transition, figure
out what will be the next configuration?

**Notes:**

- 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).
- We will prove that the set of Turing-decidable
languages is a strict subset of Turing-recognizable languages, and the set
of context-free languages is a strict subset of the set of
Turing-decidable languages.
- TMs can also be used to
*compute*functions, where they accept all inputs and leave the output string on the tape when done.