Basic Definition & Concepts

Basic Definition & Concepts

Let M = ( S, ∑, , δ, po, F ) be a k-tape Turing Machine . M has k work tapes with k work tape heads. Each work tape head is associated with one of the work tapes. The heads can move independently. The first work tape is designated as the input tape. All cells not containing input symbols must contain the blank symbol.

A TM that has a separate read-only input tape is called an off-line TM if the input head moves both left and right it is called an On-line TM if the input head moves left to right only

Def of well formed formula

Let v be a set of logical (Boolean) variables.

A w.f.f. is defined inductively by

1)Every variable is a w.f.f.

2)If w is w.f.f. then is a w.f.f.

3)If w1 & w2 are w.f.f. then (w1 + w2), (w1. w2), (w1 w2), (w1 w2) are also w.f.f.

A w.w.f. is satisfiable if there exits an assignment of the values true or false to the individual variables in w so that the whole w.f.f. w has the value “true”

Eg. (p + q + r)( + + r)(p + + r)( + +) is satisfiable

p = 0 p = 1

q = 1 q = 0

r = 1 r = 1

A w.f.f. is a tautology if it has the value “true” under every assignment of the values true & false to its individual variable

Eg p p is tautology

A logical predicate p with k variables x1… xk ( k ≥1 )

Denoted by p (x1…xk) is a function from Sk { true, false, for some set S, and integer k}

If p(x1…xk) is a predicate then the predicate Q(x1…xk) defined by

xk (P(x1,…………,xk))has the value true xk S P(x1,…………,xk) has the value true

Similarly

Q(x1,…………,xk) xk P(x1,…………,xk) has the value True for every xk S, P(x1,…………,xk) has the value 1.

Situation of a worktape

Let S1 = { ⌐ ↑ w | ⌐ ( – {B})* & w ( – {B})

S2 = { ↑ Bw | w ( – {B})+}

S3 = { ⌐ ↑ B | ⌐ ( – {B})+}

A string in the set Q = S1U S2 U S3 is called a situation of a work tape. Work tape i , 1 ≤ I ≥ k, being in situation ⌐ ↑ w represent the configuration of the ith tape when the concatenation of symbol in the active cells of work tape i forms the string vw & the head of worktape i is scanning the (|v|+1)th cell of the string of active cells. The initial situation of the k-tape of a k-tape TM. M on input w is, for tape 1, the situation is ↑ w, & for all other tapes the situation is ↑ B.

A configuration of M is a (k+1) – tapes

K=(p, w11 ↑ w 12, w21 ↑ w22 , …….., wk1 ↑ wk2) where p S & wi1 ↑ wi2 is a situation of a worktape of M, for every i 1 ≤ i ≤ k.

Initial configuration on input x denoted by Im(x)

Define a binary relation on the set ψ of all situation of worktape

Let C, A , D € AND C ≠ B, D ≠ B

w1, w2 ( – {B}*

C1 L

w1 D ↑ A w2 w1 ↑ DC w2

C1 R

w1 ↑ A w2 w1 C ↑ w2

C1 L

↑Aw2 ↑ BCw2

C1 R

W1 ↑ A w1C ↑ B

C1 P

W1 ↑ A w2 w1 ↑ Cw2

The set of final w.w.f, denoted by Am is the set of all w.w.f. (q, w11 ↑ w11, w21 ↑ w22… wk1 ↑ wk1,)

Transition Relation (denoted by ||==M )

Let K1 & K2 be 2 configurations

We have K1 ||==M K2 The TM can move in one step from w.w.f. K1 to w.w.f K2

Let

K1 = ( p , ⌐11 ↑ A1⌐12, ⌐21↑ A2⌐22… ⌐k1 ↑ Ak⌐k2)

K2 = ( q , w11 ↑ w12, w21↑ w22… wk1 ↑ wk2)

Then K1 ||==M K2 (q,C1, X1, C2, X2,………, Ck, Xk) δ ( p, A1, A2,………. ,Ak)

And i ( 1≤ i ≤ k ) (Ci , Xi )

⌐i1 ↑ Ai ⌐i2 wi1 ↑ wi2

Where Xi { L, P, R } & Ci Γ – {B}

Eg ( p, ↑ abbbbbba, ↑B ) ||==M ( p, a ↑ bbbbbba, a↑B)

Transitive & reflexive closure of ||==M ( denoted ||==*M)

The language accepted by M, denoted by T(M) is the set

T(M) = { x ∑*| Im(x) ||==*M K for some K Am}

Def. TM

A k-tape TM M = ( S, ∑, , δ, po, F ) is deterministic if , p S & a1, a2,………….., ak Γ, the set δ ( p, A1, A2,………. ,Ak) contains at most one element

Time Complexity

Let M be a TM M = ( S, ∑, , δ, po, F )

An accepting computation by M on input x ∑* is a sequence configuration k1, k2,…………… kt ( for some t ≥ 1 )

1)K1 = Im (x)

2)i ( 1 ≤ i ≤ t ) Ki ||== Ki+1 and

3) Kt Am

The time taken by M , denoted by time m is the from ∑ * to the set N { ∞ } defined by

1)If an accepting computation of M on x then timeM(x) is the length of the shortest computation and

2)If there is no acceptance computation of M on x then timeM(x0 = ∞)

Complexity classes defined by TM

Let M = ( S, ∑, , δ,po, F ) be a TM. Let f : N N

The language by M in time f, denoted by T(M1, f ) = { x ∑* | timeM (x) ≤ f(|x|) }

T(M,f) ≤ T(M) but T(M) ≠ T(M,f)

Example

Let f1(n) = n & f2 (n) = n+1 V n ≥ 0

Then T(M1 f1) = Ф & T(n,f2) = { w wk | w {a,b}+}

{ M of eg 1.1}

The family of all languages recognizable by nondeterministic TM in time f , denoted by NTIME(f), is the set NTIME(f) = { L | L = T(M) = T (M,f) function some TM M} That is , L NTIME(f) fn every string x L , an accepting computation taking at most f(|x|) steps

Similarly the family of all languages by definition TM in time F, denoted by DTIME(f) = { L | L = T(M) = T(M,f) for some definition TM M}

Definition: A ( nondet) off – line TM is a 6 – tuple

M =(S, Σ,, δ, Po , F) where

(1)S is a finite set (of state).

(2)Σ is a finite set (of infinite symbols )

which does not contain the two symbols ¢ & $ ( the left and right marker )

(3) is a finite set ( of tape symbols ) which includes the symbol R.

(4) δ transition function mapping

δ: δx { Σu {¢, $ }) X  δx { L,P,R} X { - {B } { L,P,R}

(5)Po S is the initial state.

(6)F S ( theset of finite state )

Conf of an off-line TM :

A configuration of M on input ¢ x $ is a 3 – tuple K = ( P, i, w, w2 ) where P Є S , i Є M ( 0 ≤ i ≤ | x | + 1) & w1 w2 is a situation of worktape. The conf ( P, i, w, w2 ) represents indicate that the TM is in state P, scanning the i th cell & that the current situation of the worktape is given by w1 & w2. IM(x) is (PO, 1, B). If input empty then input head scan all containing right end marker (b). . The read of final conf. A M are

( P, i, w, w2 ) P F .

A binary relation ╞ is defined on all conf. of an off-line TM. M on input ¢ x $ where

M, X

x Σ*. Let K1 = ( p, i, v, Av 2 ) & K2 = ( q, j, w, w2) & ¢x$ = a0a1……an an+1. |x| = n.

Then K1 ╞ K2 ( q, X1, C, X2) δ ( p, ai, A)

M,1 X

V1 ↑ A V2 C1X2 W1 ↑ W2 AND

J = I + Δ1 where Δ1 = -1 if X1 = L

= 0 if X1 = P

= 1 if X1 = R

The lang accepted by M 1 denoted by L(M) is the set

L(M) = { x Σ* | IM (x) ╞* k , for some k A M }

M1, x

SPACE measurement of an off-line TM

Let r = k1 k2 …..kt be an accepted computation of M on input x where kt = Am. Then the amount of worktape used in the computation r, denoted by tape M (r) , is defined to be the length of the string w 1w 2. The space used by an off-line TM M, denoted by space M, is the from Σ* to NU {∞} defined by

(1)If there is an accepting computation by M m x then space M (x) is the smallest elt in the set { tapeM ( r ) | r is an accepting computation of M on x } and

(2)If there is no accepting comp then spaceM (x) = ∞ . space M(x) is the length of the worktape at the end of that accept. Compute that uses the fewest # of worktape cells, if there is one .

An offline TM M = ( S, Σ , , δ, Po , F) is defined if p S

symbols a Σ U { ¢, $ ) b the set δ ( p, a ,b ) contains at most one element.

Let M be an off-line TM. F : NN.

The lang accepted by M in space f, denoted by L(M, f) is { x Σ* | space M (x) ≤ | f( |x| ) }.

The family of all the lang. recognizable by nondet. off-line TM in space f, denoted by NSPACE (f) = {L | L = = L(M,f) for some nondet off-line TM M}.

Similarly, DSPACE (f) = { L | L= L(M) = L(M,f), for some det. Off-line TM M }.

P-SPACE = Uk21 DSPACE (n )

NP = Uk21NTIME (n)

P = Uk21DTIME (x)