Virtual Labs

Tools

Aim

Theory

Pretest

Procedure

Simulation

Posttest

References

Contributors

Feedback

Aim

Theory

Pretest

Procedure

Simulation

Posttest

References

Contributors

Feedback

Acceptance by Deterministic Turing Machine

Choose difficulty:

Beginner

Intermediate

Advanced

Which of the following best describes the tape of a Turing machine?

a: A finite sequence of cells Explanation

Explanation

b: An infinite sequence of cells with symbols Explanation

Explanation

c: A sequence of cells with only a fixed number of symbols Explanation

Explanation

d: A tape that can't be written on Explanation

Explanation

If a non-deterministic Turing machine (NDTM) has multiple possible transitions from a given state for a specific input, it:

a: Must choose the transition leading to a halt state Explanation

Explanation

b: Requires human intervention to choose the right transition Explanation

Explanation

c: Can proceed with all of them simultaneously Explanation

Explanation

d: Errors out and stops processing Explanation

Explanation

Which of the following statements is true about the languages accepted by deterministic Turing machines?

a: They can only accept regular languages Explanation

Explanation

b: They can accept any language, including non-computable ones Explanation

Explanation

c: They can accept any language that is Turing-decidable Explanation

Explanation

d: They can only accept context-free languages Explanation

Explanation

Community Links Sakshat Portal Outreach Portal FAQ: Virtual Labs

AGPL 3.0 & Creative Commons (CC BY-NC-SA 4.0)