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.

Improve this question
$\endgroup$
3
  • 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$ Commented Mar 9, 2019 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$ Commented Mar 10, 2019 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$ Commented Mar 10, 2019 at 11:05

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Can you answer now that it is well-defined? $\endgroup$ Commented Mar 10, 2019 at 11:49
  • $\begingroup$ @Oren, see updated answer. $\endgroup$ Commented Mar 11, 2019 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$ Commented Mar 11, 2019 at 11:13
  • $\begingroup$ @Oren, sounds good! That sounds like the best course of action to me too. $\endgroup$ Commented Mar 11, 2019 at 16:57

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.