What is the Post Correspondence Problem (PCP)?
PCP, introduced by Emil Post in 1946, asks whether a sequence of string pairs can be concatenated in the same index order to yield identical strings; it is undecidable.
Which of the following problems is UNDECIDABLE?
PCP, the Halting Problem, and TM Equivalence are all classic UNDECIDABLE problems.
A Linear Bounded Automaton (LBA) is a restricted Turing Machine whose tape head:
An LBA is a non-deterministic TM whose tape memory is bounded linearly by the length of the input string, recognizing Context-Sensitive Languages.
Which computational complexity class contains problems solvable by a deterministic Turing machine in polynomial time?
Class P consists of all decision problems solvable by a Deterministic Turing Machine in O(n^k) polynomial time.
Which computational complexity class contains decision problems whose solution can be VERIFIED by a deterministic Turing machine in polynomial time?
Class NP (Nondeterministic Polynomial time) consists of problems verifiable in polynomial time by a DTM, or solvable in polynomial time by an NDTM.