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.
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.
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.
Thank you for a really great exposition.
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.
You are a professor in which college currently and in which country???
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?
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.
Why can’t you move it to it’s lowest state and computer it moving right
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.
I’m wondering if this is using the chain rule