Which statement about DPDA equivalence is correct?
Equivalence of deterministic pushdown automata is decidable, although the algorithm is nontrivial.
What is the role of an oracle for the halting problem?
An oracle for an undecidable set gives an oracle machine power beyond ordinary TMs.
Which statement about multi-track TMs is correct?
Multiple tracks can be encoded on a standard tape.
Which statement about two-dimensional-tape TMs is correct?
A 2D tape can be encoded on a 1D tape, preserving computability power.
What does a TM transition function typically specify besides the next state?
A transition determines the written symbol, movement direction, and next state.