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).
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
- TM transitions
- Can move either right or left
- TM configurations
- (current state, tape contents, head position)
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
- 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
- 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
- However, this problem is recognizable; i.e. one can
simulate a Turing Machine and wait for it to terminate.
- LANGUAGES VS.
problem is a question of the form:
given X, is it true that X ….
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
- Chapter 3.1 through page 170
- 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
- Given a configuration and the transitions, figure out which
- Given a configuration and a matching transition, figure
out what will be the next configuration?
- The set of Turing-decidable languages is a subset of
- If on first cell, a TM will just stay there instead of
- 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
- TMs can also be used to compute functions, where
they accept all inputs and leave the output string on the tape when done.