Question

Examine the formal definition of a Turing machine to answer the following questions, and explain your reasoning.

a. Can a Turing machine ever write the blank symbol on its tape?

b. Can the tape alphabet$\mathbf{\Gamma }$be the same as the input alphabet$\mathbf{\sum }$?

c. Can a Turing machine’s head ever be in the same location in two successive steps?

d. Can a Turing machine contain just a single state?

Short answer

(a) Yes. The tape alphabet $\mathrm{\Gamma }$contains. A Turing machine can write any characters in$\mathrm{\Gamma }$ on its tape.

(b) No.$\sum$ never contains , but$\mathrm{\Gamma }$ always contains . So they cannot be equal.

(c) Yes. If the Turing machine attempts to move its head off the left-hand end of the tape, it remains on the same tape cell.

(d) No. Any Turing machine must contain two distinct states: q_accept and q_reject. So, a Turing machine contains at least two states.

Step-by-step solution

Turing machine.

A Turing Machine (TM) is a mathematical model which consists of an infinite length tape divided into cells on which input is given. It consists of a head which reads the input tape. A state register stores the state of the Turing machine.

A Turing machine consists of a tape of infinite length on which read and writes operation can be performed. The tape consists of infinite cells on which each cell either contains input symbol or a special symbol called blank. It also consists of a head pointer which points to cell currently being read and it can move in both directions.

Turing machine write in blank symbol on its tape.

a)

Yes. The tape alphabet $\mathrm{\Gamma }$contains.

A Turing machine can write any characters in$\mathrm{\Gamma }$ on its tape. Hence in each and every state diagram of a Turing machine it will definitely write in the blank symbol on its tape.

A Turing machine can write a $\mathrm{\Gamma }$, since t∈$\mathrm{\Gamma }$ and the transition function has type ,

$\mathrm{\delta }:\mathrm{Q}\times \mathrm{\Gamma }\to \mathrm{Q}\times \mathrm{\Gamma }\times \left\{\mathrm{L},\mathrm{R}\right\}$

The tape alphabet.

b)

The Turing machine is defined as,

$\mathrm{\delta }:\mathrm{Q}\times \mathrm{\Gamma }\to \mathrm{Q}\times \mathrm{\Gamma }\times \left\{\mathrm{L},\mathrm{R}\right\}$

No. $\sum$never contains , but $\mathrm{\Gamma }$always contains . So they cannot be equal.

The tape alphabet $\mathrm{\Gamma }$can never be equal to the input alphabet $\sum$, since$\mathrm{t}\in \mathrm{\Gamma }$

Whereas, $\mathrm{t}\notin \sum$

A Turing machine’s head in same location in two successive steps.

c)

Yes. If the Turing machine attempts to move its head off the left-hand end of the tape, then it remains on the same tape cell.

Turing machine consists of a tape of infinite length on which read and writes operation can be performed. The tape consists of infinite cells on which each cell either contains input symbol or a special symbol called blank. It also consists of a head pointer which points to cell currently being read and it can move in both directions.

And in the Turing machine the head of a Turing machine can stay on the same cell for two consecutive steps of a computation if the head is at the leftmost tape cell and the machine tries to move left.

A Turing machine contain just a single state.

d)

No. Any Turing machine must contain two distinct states these are:

q_accept and q_reject.

The Turing machine is defined as,

$\mathrm{\delta }:\mathrm{Q}\times \mathrm{\Gamma }\to \mathrm{Q}\times \mathrm{\Gamma }\times \left\{\mathrm{L},\mathrm{R}\right\}$.

So, a Turing machine contains at least two states in its state diagram.

Hence, The state set of a Turing machine will always contain at least two states, since q_accept and q_reject are different.