Question $1$

a$)$ Draw a tape diagram for the state table below. $(10$ marks$)$

b$)$ Differentiate turing complete machine and turing incomplete machine. $(8$ marks$)$

c$)$ What is a regular language?

d$)$ Discuss the halting problem

e$)$ What is Computational complexity theory in theoretical computer science? $(6$

marks$)$

SECTION B $(60$ MARKS$)$

Nuestion $2$

a$)$ At any one time, the Turing machine has a head which is positioned over one of the squares

on the tape. Give three basic operations the machine can perform with this head and

demonstrate the operations with the symbols $"101"$ on a initially blank tape. $(10$ marks$)$

b$)$ Given the symbols $"101"$ printed on a tape

Explain and demonstrate what you understand by bit inversion.

Question $3$

a$)$ State the Church$-$Turing thesis

b$)$ According to the Church$-$Turing thesis, discuss the response of the Turing machine when

applied to a problem of its class?

Question $4$

a$)$ What do you understand by the term Decidability?

b$)$ Compare Semi$-$Decidable and Undecidable problem.

c$)$ What is an ambiguous CFG$?$

Question $5$

a$)$ Complexity clas$$es include:

$(5$ marks$)$

b$)$ Discuss any three of the above

SECTION A $14$ MARKS attempt all questions

Short aaswer questions. Answer each question in a few sentences.

$(14$ points: $2$ each$)$

a$)$ The diagram below show a hierarchy of the languager we learned, with respect to computability

Write the proper language next to the labels a$-$d in the dimgram below such that the lierarchy is

correct. The languages are: Turing$-$recogrizable, regular, decidable, context$-$ free.

b$)$ A finite automaton will run until its input is completely processed and then it will stop. This is not

true for a Turing machine. Explain why.

c$)$ A language is Turing$-$recognizable if some Turing machine recognizes it $($this is a definition$).$ But

what does it mean when we say that a TM recognizes a language? The answer can be quite simple

$($one sentence$)$ but please be precise.

d$)$ A language is Turing$-$decidable if some Turing machine decides it$.$ What does it mean for a Turing

machine to decide a language? Again, please be precise, but you can be relatively informal.

e$)$ We are given a problem and find out that it is undecidable. Could there be an algorithm to solve

it in polynomial time? Answer "yes" or $"$no$"$ and then explain$/$justify your answer.

Itell you that an algorithm runs in $O(2^{?})$ but yet is in $P.$ How can this be$?$