Undecidability: Reductions, Rice, PCP
Decision problems as languages of encodings, the acceptance and halting problems and why they are recognisable but undecidable, diagonalisation shown as a table, mapping reductions with their direction and what they transfer (decidability, recognisability), the standard reduction chain, Rice's theorem with its conditions and the cases it does not cover, its extension showing non-recognisability, the Post correspondence problem in brief, and the solved 2014 question on CFG decision problems.
