0
$\begingroup$

Is it possible for a Turing machine with input of a DFA that accepts a finite language and a string to decide whether the string is in the language without "fully simulating" the DFA on the string?

More formally, Is there a TM $M$ with a constant $C_M$ that can decide $L$, where for every input it halts at most $C_M$ steps after reading $w$'s last bit where $L$ is given by:

$L=\{\langle D,w\rangle \mid D\text{ is a DFA that accepts a finite language and $D$ accepts $w$}\}$?

I was thinking it is not possible, though I am not sure because maybe one can deduce from the encoding of the DFA without simulating the DFA what is the language.

I can't see how this can be done but not sure how to prove it can't be done.

$\endgroup$
  • 1
    $\begingroup$ "Without fully simulating any string" is something that is far, far away from well-defined. Can you define it formally, i.e., using mathematical terms? I would bet, either you can, in which case the answer should become obvious or you cannot. In that sense, the first question should be "how to define 'without fully simulating any string'"? $\endgroup$ – Apass.Jack Mar 9 at 20:49
  • $\begingroup$ @Apass.Jack Thank you for the helpful comment, I have edited the question to be more well-defined, can you take a look? $\endgroup$ – Oren Mar 10 at 9:08
  • $\begingroup$ Do not put "edit" sections after your original question. Instead, modify the question so that it reads the way you think it should. $\endgroup$ – Andrej Bauer Mar 10 at 11:05
2
$\begingroup$

You ask two questions.

For your first question, about whether a TM can do this without fully simulating the DFA:

The problem statement is not well-defined. Given a TM, you can't tell whether it "fully simulates the DFA on a string" or not. (That's undecidable.) There are all sorts of ways that a TM might effectively "simulate", but in an obfuscated way that makes it hard for you to realize that's what it is effectively doing.

Your language $L$ is certainly decidable. It has the form $L=L_1 \cap L_2$ where $L_1$ and $L_2$ are both decidable, hence $L$ is decidable too.

For the second question, about whether a TM can do this using at most a constant number of steps after reading the last bit:

Sure. That's always possible, for any decidable language. After reading all but the last bit, the TM can decide what it will do if the last bit is 0 and what it will do if the last bit is 1 (doing as much computation as necessary to handle both cases). Then, when it reads the last bit, it will immediately be able to produce the correct output, using only a constant number of steps. This doesn't really have anything to do with whether the TM is or isn't simulating the DFA, though.

$\endgroup$
  • $\begingroup$ Can you answer now that it is well-defined? $\endgroup$ – Oren Mar 10 at 11:49
  • $\begingroup$ @Oren, see updated answer. $\endgroup$ – D.W. Mar 11 at 4:56
  • $\begingroup$ Thanks. This answers my question but it's actually not what i was trying to ask (my bad in defining the question badly). I thought it's best I organize my question better and open a new one. $\endgroup$ – Oren Mar 11 at 11:13
  • $\begingroup$ @Oren, sounds good! That sounds like the best course of action to me too. $\endgroup$ – D.W. Mar 11 at 16:57

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.