We have studied two types of languages from the Chomsky hierarchy: regular languages and context-free languages. These languages can describe many practically important systems and so they are heavily used in practice. They are, however, of limited capability and there are many languages that they can not process. Here we are going to study the most general of the languages in Chomsky hierarchy, the phrase structure languages (also called Type 0 languages), and the machines that can process them: Turing machines.

Turing machines were invented of by the English mathematician Alan Turing as a model of human “computation”. Later Alonzo Church says that any computation done by humans or computers can be carried out by some Turing machine. This statement is known as Church’s thesis and today it is generally accepted as true. Computers we use today are as powerful as Turing machines except that computers have finite memory while Turing machines have infinite memory.

Turing Machines can be represented using a 7-tuple:

## TM as ACCEPTOR

A Turing machine *halts* when it no longer has any available moves. If it halts in a final state, it accepts its input; otherwise, it rejects its input.

Turing machine accepts its input if it halts in a final state. There are two ways of rejecting the input string in case of TM:

- The Turing machine could halt in a nonfinal state, or
- The Turing machine could never stop i.e hang (in which case we say it is in an
*infinite loop.*)

**L = {1**^{m} | m is odd}

^{m}| m is odd}

The Transition δ(q_{0}, 1) = δ(q_{1}, 1, R) means Initially q_{0} will read the input 1 from Tape, move to state q_{1},1 is replaced by 1 and read/write head moves to right.

δ(q_{0}, 1) = δ(q_{1}, 1, R)

δ(q_{1}, 1) = δ(q_{0}, 1, R)

δ(q_{1}, β) = δ(qf, β, L/R)

If Blank is reached in q_{1} state then input string contain odd no. of 1’s. because on reading odd 1’s machine moves to q_{1 }state.

**L = {0**^{m} | m is even}

^{m}| m is even}

δ(q_{0 }, 0) = δ(q_{1 }, 0, R)

δ(q_{1 }, 0) = δ(q_{0 }, 0, R)

δ(q_{0 }, β) = δ(q_{f }, β, L/R)

**L = {a**^{n}b^{n}| n > 0}

^{n}b

^{n}| n > 0}

There is no concept of minimal TM, change state only if needed. Do not think about ∈ in TM.

Strings Accepted by language = {ab, aabb, aaabbb, …}

δ(q_{0}_{ }, a) = (q_{1 }, x, R)

δ(q_{1 }, a) = (q_{1 }, a, R)

δ(q_{1 }, b) = (q_{2 }, y, L)

δ(q_{2 }, a) = (q_{2 }, a, L)

δ(q_{2 }, x) = (q_{0 }, x, R)

δ(q_{1 }, y) = (q_{1 }, y, R)

δ(q_{2 }, y) = (q_{2 }, y, L)

δ(q_{0 }, y) = (q_{3 }, y, R)

δ(q_{3 }, y) = (q_{3 }, y, R)

δ(q_{3 }, β) = (q_{f }, β, R/L)

## TM as TRANSDUCER

A Turing machine can be used as a transducer. The most obvious way to do this is to treat the entire non-blank portion of the initial tape as input, and to treat the entire non-blank portion of the tape when the machine halts as output.

#### Qus 1: Design TM to calculate m – n, where m, n are positive integer and m > n.

f(m,n) = m – n

Here suppose m is 5 and n is 3 then we can represent m by 5 o’s and n by 3 o’s. Both m and n are separated by 1.

5 – 3 = 2

000001000 = 00

The transition’s for this TM is as below –

δ(q_{0 }, 0) = (q_{1 }, β, R)

δ(q_{1 }, 0) = (q_{1 }, 0, R)

δ(q_{1 }, 1) = (q_{2 }, 1, R)

δ(q_{2 }, 0) = (q_{2 }, 0, R)

δ(q_{2 }, β) = (q_{3 }, β, L)

δ(q_{3 }, 0) = (q_{4 }, β, L) // when all 0’s are over at q_{3 }, it receive 1 at end.

δ(q_{4 }, 0) = (q_{4 }, 0, L)

δ(q_{4 }, 1) = (q_{5 }, 1, L)

δ(q_{5 }, 0) = (q_{5 }, 0, L)

δ(q_{5 }, β) = (q_{6 }, β, R)

δ(q_{6 }, 0) = (q_{1 }, β, R) // See Note 1 below

δ(q_{3 }, 1) = (q_{f }, 0, L)

Note 1: Beginning of next cycle for cancellation of 0 by 0. This process continues till all 0’s in n are cancelled by an equal no of 0’s in m. In the next cycle a 0 is cancelled in m but n has no more 0’s so read/write head receives the separator 1 in q_{3} state and replace it with 0 and enters in final state q_{f}.

#### Qus 2: Design TM to calculate m + n, where m, n are positive integer

f(m,n) = m + n

Here suppose m is 3 and n is 4 then we can represent m by 3 1’s and n by 4 1’s. Both m and n are separated by 0.

3 + 4 = 7

__111__0__1111__ = 1111111

The transition’s for this TM is as below –

Logic: When 0 is encountered, it is changed to 1 and last 1 is replaced by β.

δ(q_{0 }, 1) = (q_{0}_{ }, 1, R)

δ(q_{0 }, 1) = (q_{1}_{ }, 1, R)

δ(q_{1 }, 1) = (q_{1 }, 1, R)

δ(q_{1 }, β ) = (q_{2 }, β, L)

δ(q_{2}_{ }, 1) = (q_{f}_{ }, β, L)

Hello, you used to write magnificent, but the last several posts have been kinda boring… I miss your great writings. Past few posts are just a little bit out of track! come on!