CS计算机代考程序代写 flex algorithm Slide 1

Slide 1

Turing Machines
Chapter 17

Languages and Machines
SD

D

Context-Free
Languages

Regular
Languages
reg exps
FSMs

cfgs
PDAs

unrestricted grammars
Turing Machines

SD Language
Unrestricted Grammar
Turing Machine

L
Accepts
Grammars, SD Languages, and Turing Machines

Turing Machines
Can we come up with a new kind of automaton that has two properties:

● powerful enough to describe all computable things

unlike FSMs and PDAs.

● simple enough that we can reason formally about it

like FSMs and PDAs,
unlike real computers.

Turing Machines
At each step, the machine must:

● choose its next state,
● write on the current square, and
● move left or right.

A Formal Definition
A Turing machine M is a sixtuple (K, , , , s, H):

● K is a finite set of states;
●  is the input alphabet, which does not contain q;
●  is the tape alphabet, which must contain q and have  as a
subset.
● s  K is the initial state;
● H  K is the set of halting states;
●  is the transition function:

(K – H)   to K    {, }

non-halting  tape state  tape  action
state char char (R or L)

Notes on the Definition
1. The input tape is infinite in both directions.

2.  is a function, not a relation. So this is a definition for
deterministic Turing machines.

3.  must be defined for all (state, input) pairs unless the state is a halting state.

4. Turing machines do not necessarily halt (unlike FSM’s and
PDAs). Why? To halt, they must enter a halting state.
Otherwise they loop.

5. Turing machines generate output so they can compute
functions.

An Example
M takes as input a string in the language:

{aibj, 0  j  i},

and adds b’s as required to make the number of b’s equal the number of a’s.

The input to M will look like this:

The output should be:

The Details
K = {1, 2, 3, 4, 5, 6},  = {a, b},  = {a, b, q, $, #},
s = 1, H = {6},  =

Halting
● A DFSM M, on input w, is guaranteed to halt in |w| steps.

● A PDA M, on input w, is not guaranteed to halt. To see
why, consider again M =

But there exists an algorithm to construct an equivalent PDA
M that is guaranteed to halt.

A TM M, on input w, is not guaranteed to halt. And there exists no algorithm to construct one that is guaranteed to do so.

Formalizing the Operation
A configuration of a Turing machine

M = (K, , , s, H) is an element of:

K  ((- {q}) *)  {}    (* (- {q}))  {}

state up scanned after
to scanned square scanned
square square

Example Configurations

(1) (q, ab, b, b) = (q, abbb)
(2) (q, , q, aabb) = (q, qaabb)

Initial configuration is (s, qw).

Yields
(q1, w1) |-M (q2, w2) iff (q2, w2) is derivable, via , in one step.

For any TM M, let |-M* be the reflexive, transitive closure of |-M.

Configuration C1 yields configuration C2 if: C1 |-M* C2.

A path through M is a sequence of configurations C0, C1, …, Cn for some n  0 such that C0 is the initial configuration and:

C0 |-M C1 |-M C2 |-M … |-M Cn.

A computation by M is a path that halts.

If a computation is of length n or has n steps, we write:

C0 |-Mn Cn

A Notation for Turing Machines
(1) Define some basic machines

● Symbol writing machines

For each x  , define Mx, written just x, to be a machine that writes x, then halts.

● Head moving machines

R: for each x  , (s, x) = (s, x, )
L: for each x  , (s, x) = (s, x, )

● Machines that simply halt:
h, which simply halts.
n, which halts and rejects.
y, which halts and accepts.

Next we need to describe how to:
● Check the tape and branch based on what character
we see, and
● Combine the basic machines to form larger ones.

To do this, we need two forms:
● M1M2
Begin in start state of M1, run M1 until halts, begin M2 in start state, run M2 until halts, then halt. If either fails to halt, then M1M2 fails to halt.

● M1 M2

The same, except that is checked to move from M1 to M2.

Checking Inputs and Combining Machines

A Notation for Turing Machines, Cont’d
Example:

>M1 a M2
b

M3

● Start in the start state of M1. (“>” marks the beginning)
● Compute until M1 reaches a halt state.
● Examine the tape and take the appropriate transition.
● Start in the start state of the next machine, etc.
● Halt if any component reaches a halt state and has no place
to go.
● If any component fails to halt, then the entire machine may fail to halt.

a
M1 M2 becomes M1 a, b M2
b

M1 all elems of  M2 becomes M1 M2
or
M1M2
Variables

M1 all elems of  M2 becomes M1 x  a M2
except a and x takes on the value of
the current square

M1 a, b M2 becomes M1 x  a, b M2
and x takes on the value of
the current square

M1 x = y M2
if x = y then take the transition

e.g., > x  q Rx if the current square is not blank, go right and copy it.
Shorthands

Some Useful Machines
Find the first blank square to
the right of the current square.

Find the first blank square to
the left of the current square.

Find the first nonblank square to
the right of the current square.

Find the first nonblank square to
the left of the current square
Rq
Lq
Rq
Lq

More Useful Machines
La Find the first occurrence of a to
the left of the current square.

Ra,b Find the first occurrence of a or b
to the right of the current square.

La,b a M1 Find the first occurrence of a or b
to the left of the current square,
b then go to M1 if the detected
character is a; go to M2 if the
M2 detected character is b.

Lxa,b Find the first occurrence of a or b
to the left of the current square
and set x to the value found.

Lxa,bRx Find the first occurrence of a or b
to the left of the current square,
set x to the value found, move one
square to the right, and write x (a or b).

An Example
Input: qw w  {1}*
Output: qw3

Example: q111qqqqqqqqqqqqqq

A Shifting Machine S
Input: quqwq
Output: quwq

Example: qbaqabbaqqqqqqqqqqqq

Turing Machines as Language Recognizers
Convention: We will write the input on the tape as:
qwq, w contains no q’s

The initial configuration of M will then be:
(s, qw)

Let M = (K, , , , s, {y, n}).

● M accepts a string w iff (s, qw) |-M* (y, w) for some string w.

● M rejects a string w iff (s, qw) |-M* (n, w) for some string w.

Turing Machines as Language Recognizers
M decides a language L  * iff:
For any string w  * it is true that:
if w  L then M accepts w, and
if w  L then M rejects w.

A language L is decidable iff there is a Turing machine M that decides it. In this case, we will say that L is in D.

A Deciding Example
AnBnCn = {anbncn : n  0}

Example: qaabbccqqqqqqqqq

Example: qaaccbqqqqqqqqq

Another Deciding Example
WcW = {wcw : w  {a, b}*}

Example: qabbcabbqqq

Example: qacabbqqq

Semideciding a Language
Let M be the input alphabet to a TM M. Let L  M*.

M semidecides L iff, for any string w  M*:

● w  L  M accepts w
● w  L  M does not accept w. M may either:
reject or
fail to halt.

A language L is semidecidable iff there is a Turing machine that semidecides it. We define the set SD to be the set of all semidecidable languages.

Example of Semideciding
Let L = b*a(a  b)*

We can build M to semidecide L:

1. Loop
1.1 Move one square to the right. If the character under
the read head is an a, halt and accept.

In our macro language, M is:

Example of Semideciding
L = b*a(a  b)*. We can also decide L:

Loop:
1.1 Move one square to the right.
1.2 If the character under the read/write head is
an a, halt and accept.
1.3 If it is q, halt and reject.

In our macro language, M is:

Computing Functions
Let M = (K, , , , s, {h}). Its initial configuration is (s, qw).

Define M(w) = z iff (s, qw) |-M* (h, qz).

Let    be M’s output alphabet (i.e., the set of symbols that M may leave on its tape when it halts)

Let f be any function from * to *.

M computes f iff for all w  *, M(w) = f(w).

A function f is recursive or computable iff there is a Turing machine M that computes it.

(Note that M always halts.)

Example of Computing a Function
Let  = {a, b}. Let f(w) = ww.

Input: qwqqqqqq Output: qwwq

Define the copy machine C:
qwqqqqqq  qwqwq

Remember the S machine:
quqwq  quwq

Then the machine to compute f is just >C S Lq

8.unknown

Computing Numeric Functions
For any positive integer k, valuek(n) returns the nonnegative integer that is encoded, base k, by the string n.

For example:

● value2(101) = 5.

● value8(101) = 65.

TM M computes a function f from ℕm to ℕ iff, for some k:

valuek(M(n1;n2;…nm)) = f(valuek(n1), … valuek(nm)).

Computing Numeric Functions
Example: succ(n) = n + 1

We will represent n in binary. So n  0  1{0, 1}*

Input: qnqqqqqq Output: qn+1q
q1111qqqq Output: q10000q

Not All Functions Are Computable
Let T be the set of all TMs that:
● Have tape alphabet  = {q, 1}, and
● Halt on a blank tape.

Define the busy beaver functions S(n) and (n):

● S(n): the maximum number of steps that are executed by any element of
T with n-nonhalting states, when started on a blank tape, before it halts.
● (n): the maximum number of 1’s left on the tape by any element
of T with n-nonhalting states, when it halts.
n S(n) (n)
1 1 1
2 6 4
3 21 6
4 107 13
5  47,176,870 4098
6  3101730  1.2910865

Why Are We Working with Our Hands Tied Behind Our Backs?
Turing machines Are more powerful than any of
the other formalisms we have
studied so far. 
Turing machines Are a lot harder to work with than
all the real computers we have
available.

Why bother?

The very simplicity that makes it hard to program Turing machines makes it possible to reason formally about what they can do. If we can, once, show that anything a real computer can do can be done (albeit clumsily) on a Turing machine, then we have a way to reason about what real computers can do.