Virtual Labs

Acceptance by Deterministic Turing Machine

What is the main difference between a Pushdown Automaton (PDA) and a Turing Machine?

a: PDA has a stack while Turing Machine has a tape Explanation

Explanation

b: PDA is deterministic while Turing Machine is non-deterministic Explanation

Explanation

c: PDA can only read input while Turing Machine can read and write Explanation

Explanation

d: PDA has finite states while Turing Machine has infinite states Explanation

Explanation

What does the Church-Turing thesis state?

a: All computers are equivalent to Turing machines Explanation

Explanation

b: Any computation that can be algorithmically performed can be computed by a Turing machine Explanation

Explanation

c: Turing machines are the fastest computational model Explanation

Explanation

d: All programming languages are Turing complete Explanation

Explanation

How many components are in the formal definition of a Turing Machine?

a: 5 Explanation

Explanation

b: 6 Explanation

Explanation

c: 7 Explanation

Explanation

d: 8 Explanation

Explanation

What does the symbol Γ (Gamma) represent in a Turing Machine?

a: The input alphabet Explanation

Explanation

b: The tape alphabet Explanation

Explanation

c: The set of states Explanation

Explanation

d: The transition function Explanation

Explanation

What is the key characteristic of a Deterministic Turing Machine (DTM)?

a: It has multiple tapes Explanation

Explanation

b: It can move in both directions on the tape Explanation

Explanation

c: For any state-symbol combination, there is exactly one possible transition Explanation

Explanation

d: It always halts Explanation

Explanation

What does it mean for a system to be 'Turing complete'?

a: It can solve any problem in polynomial time Explanation

Explanation

b: It has the computational power to simulate a Turing machine Explanation

Explanation

c: It can only solve decidable problems Explanation

Explanation

d: It is faster than a Turing machine Explanation

Explanation

What is the Halting Problem?

a: A problem about when to stop a Turing machine manually Explanation

Explanation

b: A decidable problem that determines if a program will terminate Explanation

Explanation

c: An undecidable problem about whether a program will halt on given input Explanation

Explanation

d: A problem about optimizing program execution time Explanation

Explanation

Which class of languages can Turing Machines recognize?

a: Regular languages only Explanation

Explanation

b: Context-free languages only Explanation

Explanation

c: Context-sensitive languages only Explanation

Explanation

d: Recursively enumerable languages Explanation

Explanation

What happens when a Turing Machine reaches an accept state?

a: It continues processing the input Explanation

Explanation

b: It rejects the input Explanation

Explanation

c: It accepts the input and halts Explanation

Explanation

d: It moves to the reject state Explanation

Explanation

Why are two stacks equivalent to a Turing machine tape?

a: Two stacks provide more memory than one stack Explanation

Explanation

b: Two stacks allow access to any middle element by transferring between stacks Explanation

Explanation

c: Two stacks are faster than one tape Explanation

Explanation

d: Two stacks can store more symbols Explanation

Explanation

What is the transition function δ (delta) in a Turing Machine?

a: A function that determines the initial state Explanation

Explanation

b: A function that maps current state and tape symbol to next state, write symbol, and head movement Explanation

Explanation

c: A function that determines if the input is accepted Explanation

Explanation

d: A function that counts the number of steps Explanation

Explanation

What is computability in the context of Turing machines?

a: The speed at which a Turing machine operates Explanation

Explanation

b: Whether a problem can be solved by following a finite sequence of well-defined steps Explanation

Explanation

c: The amount of memory a Turing machine uses Explanation

Explanation

d: The number of states in a Turing machine Explanation

Explanation