Re:MIT 18.404J – Theory of Computation [video]
by unobatbayar on Sunday October 10, 2021 @11:33PM
(#28824368)
If you study for the exam, wouldn't that make it deterministic?
Re:MIT 18.404J – Theory of Computation [video]
by remexre on Monday October 11, 2021 @01:52AM
(#28825165)
A non-deterministic Turing machine has the ability to choose "correctly" from a finite set of options. (This corresponds to search, which gives a nice intuitive notion that search can't do better than exponential time without knowledge of the search space unless P=NP.)
[Lecture 2, 40:26 minutes: https://youtu.be/oNsscmUwjMU?t=2426 ]