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

Q. Which among the following is not true for 2-way infinte TM?

View solution