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

Question 1

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).

Marks: 10

Year: 2076 Final TU

Section A: Turing Machine Definition: Turing Machine (TM) A (deterministic) Turing Machine is a 7-tuple \(M = (Q, \Sigma, \Gamma, \delta, q0, B, F)\) where: - \(Q\) is a finite set of states. - \(\Si

Question 2

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

Marks: 5

Year: 2076 Final TU

1. Multi-tape Turing Machine A multi-tape Turing machine is like the standard single-tape TM but has several (k ≥ 1) tapes, each with its own head. Formally, a k-tape TM is a 7-tuple M = (Q, Σ, Γ, δ,

Question 3

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

Marks: 5

Year: 2076 Final TU

Complexity of a Turing Machine: It is a measure of the computational resources required by a TM to solve a problem as a function of input size n. Two main types: - Time complexity (T(n)) – number

Question 4

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

Marks: 5

Year: 2076 Final TU

Tractable problem: A decision problem is called tractable if there exists a deterministic Turing machine that decides it in polynomial time, i.e. time \(T(n)=O(n^k)\) for some constant \(k\). - In

Question 5

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 r

Marks: 10

Year: 2078 Final TU

TURING MACHINE FOR ODD LENGTH STRINGS OVER {a, b} TM Definition: M = (Q, Σ, Γ, δ, q₀, B, F) - Q = {q₀, q₁, q₂, q₃, q₄} - Σ = {a, b} - Γ = {a, b, X, Y, B} - q₀ = start state - B = blank symbol - F =

Question 6

Define Turing Machine and explain its different variations.

Marks: 5

Year: 2078 Final TU

Turing Machine and Its Variations Definition of Turing Machine A Turing Machine (TM) is a mathematical model of computation that consists of a finite state machine, an infinite tape, and a read/write

Question 7

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

Marks: 5

Year: 2078 Final TU

Computational Complexity Definition Computational Complexity is a branch of computer science that studies the resources required to solve computational problems, focusing on time and space requiremen

Question 8

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

Marks: 5

Year: 2079 Final TU

Idea (one line) Repeatedly match the leftmost unmarked a with the leftmost unmarked b to its right: mark matched a as X and matched b as Y. If all symbols are matched (or the input is empty) accept; i

Question 9

Define Turing machine and its roles.

Marks: 5

Year: 2079 Final TU

Definition of Turing Machine A Turing Machine (TM) is a mathematical model of computation proposed by Alan Turing. It is a theoretical machine used to define and study what can be computed. A Turi

Question 10

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 acc

Marks: 10

Year: 2080 Final TU

1. How does a Turing Machine accept a string? (short) A Turing Machine (TM) accepts a string if, when started in the initial state with the string on the tape and the head at the leftmost symbol, it e

Question 11

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

Marks: 5

Year: 2080 Final TU

Turing Machine that computes the constant function \(f(n)=0\) Goal: For any input that encodes a number \(n\) (here we assume unary input 1^n but the machine works for any input over {1}), the TM repl

Question 12

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.

Marks: 10

Year: 2080 Final TU

Turing Machine as a Computing Function & TM for \(f(x)=2x\) (unary input) Chapter: Unit VI — Turing Machines Idea: When input is given in unary as a string of 1's (i.e. 1^n), we want the TM to produce