What tape boundary markers are placed on a Linear Bounded Automaton's tape to enclose the input string w?
Special end-markers ¢ and $ enclose input string w, preventing the LBA read/write head from moving beyond designated input boundaries.
How does a Multi-Track Turing Machine differ from a Multi-Tape Turing Machine?
Multi-track TMs move one head across stacked symbol tracks on a single tape; multi-tape TMs control independent heads across independent tapes.
If a Multi-Tape Turing Machine solves a problem in T(n) steps, what is the maximum time bound required for an equivalent Single-Tape TM to simulate it?
Hartmanis and Stearns proved that simulating a k-tape TM step-by-step on a single-tape TM incurs at most quadratic time slowdown O(T(n)^2).
In a Non-Deterministic Turing Machine (NDTM), what is the signature of the transition function $\delta$?
In an NDTM, $\delta maps (state, tape symbol)$ to a SET of possible next moves (state, write symbol, direction) in $2^{Q$ $\times Γ \times {L, R}}$.
If an NDTM accepts a language L in time T(n), what is the worst-case time required for a Deterministic TM (DTM) to simulate it via Breadth-First Search?
Simulating all parallel computation paths of an NDTM deterministically via BFS takes exponential time O($b^{T}(n))$ in the depth of computation tree.