Lecture 10: Computation History Method

Name: Lecture 10: Computation History Method
Uploaded: 2021-10-06T12:44:33Z
Duration: 1 h 21 min 41 s
Description: 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

1:21:41

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