Short Notes on PDA Variants, Turing Machines, and PCP

You asked for short notes on four topics from the theory of computation: deterministic vs. non-deterministic pushdown automata (PDA), the universal Turing machine, the non-deterministic Turing machine, and the Post correspondence problem (PCP).
Below are compact, exam-style notes with key definitions, contrasts, and the most important theoretical properties.

(i) Deterministic PDA vs. Non-deterministic PDA

A keywordPDA is a finite automaton equipped with a stack to recognize context-free languages. is called deterministic if, at every step, the machine has at most one possible move given the current state, input symbol, and top-of-stack symbol. It is non-deterministic if it may have two or more possible moves from the same configuration; then acceptance means some computation path leads to acceptance.

Key model components

• keywordA configuration describes current state, remaining input, and stack content.
• keywordThe transition relation specifies what move(s) are allowed from a configuration.
• keywordAcceptance criteria used for PDA computations.
• keywordA sequence of configurations produced by choosing transitions step-by-step.

Deterministic PDA (DPDA)

• At any configuration, the transition is unique (no branching).
• Computation is a single path (if you follow the unique moves).
• If the DPDA gets stuck, it rejects (depending on acceptance mode).

Non-deterministic PDA (NPDA)

• From a configuration, there may be multiple possible transitions.
• The machine branches into a computation tree.
• Acceptance occurs if at least one branch accepts (again depending on acceptance mode).

Power comparison (important)

• Both DPDA and NPDA recognize exactly the context-free languages.
• Non-determinism can simplify design (e.g., guessing matching structure), but it does not increase language-recognition power beyond CFLs.

(ii) Universal Turing Machine

A keywordUTM is a TM that can simulate any other TM given its description and input. is a single, fixed TM $U$ that can simulate an arbitrary TM $M$ on an input $w$ when provided with an encoding of $(M,w)$ (often written as $\langle M\rangle \# w$).

Core idea

• The “program” for the simulated machine is supplied as data to the universal machine.
• The universal TM interprets the encoded transition rules of $M$ and reproduces $M$’s behavior step-by-step.

Why UTMs matter

• They show that the notion “computation as program execution” is captured by Turing’s model.
• They establish that a finite fixed machine can emulate all computable functions (up to suitable encoding conventions).

Visual analogy

(iii) Non-deterministic Turing Machine (NDTM)

A keywordNDTM is a TM whose transition relation may allow multiple next moves from a configuration. differs from a deterministic TM because from the same configuration it may have multiple possible transitions.

Computation model

• Instead of one computation path, an NDTM generates a computation tree.
• Each node is a configuration; edges correspond to possible next transitions.
• Acceptance is typically defined as: if there exists at least one branch that reaches an accepting state (or halts and accepts), then the input is accepted.

Key terms

• keywordTree of all possible computation paths of an NDTM on an input.
• keywordAcceptance if at least one path accepts.
• keywordAcceptance if all paths accept (less common in standard NDTM definitions).
• keywordChoosing among multiple possible transitions produces multiple paths.

Relationship to DP (intuition)

• Although NDTMs can “guess” choices, deterministic simulation may incur overhead.
• Complexity-theoretically, many results compare classes like $P$ vs $NP$ via the power of nondeterminism (time-based definitions).

(iv) Post Correspondence Problem (PCP)

The keywordPCP asks whether there exists a sequence of tile indices that makes two concatenated strings equal. is a decision problem defined using “tiles” that each have a top string and a bottom string.

Formal definition (standard)

Given a finite list of pairs of strings (tiles):

• $(u_1, v_1), (u_2, v_2), \dots, (u_k, v_k)$
  The question is: does there exist a sequence of indices $i_1, i_2, \dots, i_n$ (with $n \ge 1$) such that

If such a sequence exists, it is called a solution to the PCP instance.

Why PCP is important

• PCP is a classic undecidable problem.
• It is often used as a stepping stone for reductions proving undecidability of other problems.
• Many undecidability proofs reduce from the halting problem or known undecidable systems to PCP.

Relationship with computation

PCP can encode the behavior of Turing machine computations by building sequences whose concatenations simulate tape evolution (via carefully constructed tiles). This gives the undecidability result.