Nondeterministic Turing Machines (NTMs), what are they?

[@lowerbound4803]

Thank you for a really great exposition.

[@christiansinger2497]

Great video ! I was stuck on the proof of the equivalence of deterministic and nondeterministic turing nachines in Michael Sipsers book and this video really helped with grasping it.

[@rithik32]

You are a professor in which college currently and in which country???

[@ruizhenliu9544]

how do we keep track of the addresses using a multitape turing machine? Obviously there should be a tape whose alphabet is {0,1,...,d-1}^L, but then?

[@zhangeluo3947]

You can convert the mutitape machine into single tape ones (taking those multitapes along with all auxiliary and main alphabets and states as a whole node in the computation tree), then doing BFS the same way as mentioned in the video.

[@brendawilliams8062]

Why can’t you move it to it’s lowest state and computer it moving right

[@orlandomoreno6168]

It doesn't seem like a nondeterministic decider can be always translated to a deterministic decider. A nondeterminstic decider could for example have three states P, Q, R such that R rejects, P can only go to Q and Q can go back to P or go to R. This would create a new rejecting path every two steps. But if you enumerate this machine with that algorithm, it never ends. The corresponding deterministic machine wouln't be a decider.

[@brendawilliams8062]

I’m wondering if this is using the chain rule