Q. State true or false:
Statement: Inorder to show something is Turing complete, it is enough to demonstrate that it can be used to simulate some Turing complete system.

View solution

Q. Which of the following can be used to simulate any turing machine?

View solution

Q. Which of the following remarks the given statement?
Statement: Any function whose values can be computed by an algorithm, can be computed by a Turing machine.

View solution

Q. Let two machines be P and Q. The state in which P can simulate Q and Q can simulate P is called:

View solution

Q. Give a classic example of the concept of turing complete.

View solution

Q. Fill in the blank with an appropriate option.
In automata theory, ___________ is said to be Computationally Universal if can be used to simulate any single taped Turing Machine.

View solution

Q. For a basic turing machine, there exists an equivalent :

View solution

Q. A two-way infinite tape turing machine is ________ superior than the basic model of the turing machine in terms of power.

View solution

Q. Which among the following options are correct?
Statement 1: TMs can accept languages that are not accepted by any PDA with one stack.

Statement 2: But PDA with two stacks can accept any language that a TM can accept.

View solution

Q. Which of the following is true with reference to semi-infinite tape using a two track tape?

View solution

Q. State true or false:
Statement: Using a two track tape, we can use a semi infinite tape to simulate an infinte tape.

View solution

Q. Linear Bounded Automaton is a:

View solution

Q. Which of the following parameters cannot be used to restrict a turing machine?

View solution

Q. Instantaneous description of a counter machine can be described using:

View solution

Q. A ___________ is a multi tape turing machine whose input tape is read only.

View solution

Q. Can a single tape turing machine be simulated using deterministic 2-stack turing machine?

View solution

Q. Complete the following statement:
Statement : A language is turing recognizable if an only if ___________

View solution

Q. For the following language, an enumerator will print:
L={a^nb^n|n>=0}

View solution

Q. Enumerator is a turing machine with __________

View solution

Q. Can a turing machine act like a transducer?

View solution