Question:

Church’s Thesis supports

A.

a turing machine as a general-purpose computer system

B.

a turing machine an algorithm and an algorithm as a turing machine

C.

both tm is an general-purpose computer and tm is an algorithm and vice-versa are correct

D.

none of them is correct

Answer» c. both tm is an general-purpose computer and tm is an algorithm and vice-versa are correct

Question:

In which of the stated below is the following statement true?“For every non-deterministic machine M1, there exists as equivalent deterministic machine M2 recognizing the same language.”

A.

m1 is a non-deterministic finite automata

B.

m1 is a non-deterministic push-down automata

C.

m1 is a non-deterministic turing machine

D.

for no machine m1 use the above statement true

Answer» c. m1 is a non-deterministic turing machine

Question:

A random access machine (RAM) and truing machine are different in

A.

power

B.

accessing

C.

storage

D.

both accessing and storage are correct

Answer» d. both accessing and storage are correct

Question:

Which of the following conversion is not possible (algorithmically)?

A.

regular grammar to context-free grammar

B.

non-deterministic finite state automata to deterministic finite state automata

C.

non-deterministic pushdown automata to deterministic pushdown automata

D.

none deterministic turing machine to deterministic turing machine

Answer» b. non-deterministic finite state automata to deterministic finite state automata