Lecture 10: Computation History Method

Om kurset

Description: Quickly reviewed last lecture. Defined configurations and computation histories. Gave the computation history method to prove undecidability. Showed that \(A_\bf{LBA}\) is decidable; \(E_\bf{LBA}\), \(PCP\), and \(ALL_\bf{CFG}\) are undecidable. Instructor: Prof. Michael Sipser