Bsc CSIT Semester 4 – Theory of Computation – Unit VI: Turing Machines (10 Hrs.)

Define a Turing machine. Construct a TM that accept L = {wcwR | w∈(0, 1) and c is ε or 0 or 1. Show that string 0110 is accepted by this TM with sequence of Instantaneous Description (ID).

Describe the Turing machines with multiple tape, multiple track and storage in state.

Define complexity of a Turing machine. Explain about big Oh, big Omega and big Theta notation used for complexity measurement.

What do you mean by tractable and Intractable problems? Explain with reference to TM.

Construct a Turing Machine that accepts the language of odd length strings over alphabet {a, b}. Give the complete encoding for this TM as well as its input string w = abb in binary alphabet that is recognized by Universal Turing Machine.

Define Turing Machine and explain its different variations.

Whar do you mean by computational Complexity? Explian about the time and space complexity of a Turing machine.

Construct a Turing machine that accepts the language, L = { a b | n≥0}

Define Turing machine and its roles.

How does Turing machine accept a string? Design a Turing Machine over the alphabet {0,1,a} that processes the string defined by L = {a01a,a10a,a0101a}. Show both transition diagram and table. Show acceptance of a0101a.

Design a Turing machine that computes a function f(n)=0.

How Turing Machine is used as a computing function? Construct a TM for simulating a function f(x) = 2x for x = {1}. Itetrate the TM for input 11 and generate the output 1111.

Define Turing machine as enumerators of strings of a language. Encode the Turing machine

TM = ({q0, q1, q2} , {a, b}, {a, b, B}, δ, q2, B, F) with input w = ba

and δ is defined as follows:

δ(q0, b) → (q1, b, R), δ(q1, a) → (q2, a, R), δ(q2, a) → (q1, a, R), δ(q2, b) → (q2, b, L)

For the following Turing Machine, test whether the string “( ) ) )” is accepted or rejected and represent it in transition diagram.