Which of the following statement(s) is/are TRUE regarding the Halting Problem?
Statements (A), (B), and (C) are all mathematically true regarding the Halting Problem and its complement.
Modified Post Correspondence Problem (MPCP) requires the match sequence to start with:
MPCP forces the tile sequence to start with index 1, making it easier to reduce from Turing Machine acceptance proofs.
If a language L is Recursive, its complement L':
Since Recursive languages are closed under complementation, L' is Recursive, which implies it is also Recursively Enumerable and Decidable.
What is the tape movement capability of a standard 1-tape Turing Machine?
A TM read/write head moves 1 cell Left or Right (or optional Stay) per transition step.
Which language class is accepted by a Pushdown Automaton with TWO STACKS?
A 2-stack PDA can simulate a Turing machine tape (one stack for tape left of head, second stack for tape right of head).