I found en excercise asking this question. I know that for proving the equivalence of NFAs and DFAs we can use the conversion through subsets, and that for proving the equivalence of nondeterministic TMs and deterministic ones we can build a 3-tape deterministic TM M which emulates the steps of a given nondeterministic one, let's call it N, proceeding this way:

  1. It copies the input string of N on the first tape
  2. On the 2nd tape, for each $i$th step of computation of N it produces a maximum of $d^i$ strings of length $i$ consisting of sequences of numbers between $i$ and $d$ representing the possible nondeterministic computations of N where $d$ is the nondeterminism degree of N
  3. For each of the above strings, it copies the content of the 1st tape on the 3rd tape and it tries every nondeterministic choice represened by its symbols, one by one

Basically M does a breadth first search on the tree of the computations of N, so if N has an accepting configuration on a computation path, surely M will find it because it will travel that path sooner or later.

So, for answering the question, I thought that the main reason is that a Turing Machines has a tape whereas a finite state automaton not so we can't use the same procedure used for converting a NFA into a DFA. Is it a sufficient answer? Should I mention that a Turing Machine isn't guaranteed to halt on any input too? How would you answer? Thanks in advance.

  • $\begingroup$ The question isn't well-defined and is very subjective. I'm not even sure I agree with the premise. $\endgroup$ – Yuval Filmus Sep 17 '19 at 10:34
  • $\begingroup$ Are you asking whether halting DTMs are equivalent to halting NTMs? $\endgroup$ – xskxzr Sep 17 '19 at 12:02
  • $\begingroup$ @YuvalFilmus I took the question from an exam assignment. $\endgroup$ – Fabio Nardelli Sep 17 '19 at 17:06
  • $\begingroup$ @xskxzr no, I know that nondeterministic Turing machines are equivalent to deterministic ones. I'm asking (well, my professor really) why can't we use the same approach used to show the equivalence of NFAs and DFAs $\endgroup$ – Fabio Nardelli Sep 17 '19 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.