World's most popular travel blog for travel bloggers.

Recovering the transition function of a Turing machine with a known number of states

, , No Comments
Problem Detail: 

Suppose we have a Turing Machine and know how many states it has as well as bound on its running time, but do not initially know its transition function. Is it possible to determine its transition function (up to a relabeling of its states and disregard for inaccessible states) by noting its behavior on only finitely many strings? (By behavior I mean a record of its computation histories leaving out the information of which state it is in at any particular step.)

On the one hand, there are only finitely many Turing machines with a set number of states, so we could definitely run them on all of the finitely many given strings to determine if a given transition function is not a candidate. However, I realize that Rice's Theorem might prevent us from determining the behavior on all inputs given only its behavior on inputs up to a given length. Even if it is not possible for Turing machines to recover its transition function, is it possible for simpler computation models like DFA's and PDA's? Thanks for your help.

Asked By : Ari

Answered By : D.W.

Yes, this is possible. This is not really a question about Turing machines so much as a question about learning DFAs given membership queries (you provide an input to the DFA and learn whether it accepts or not, and in the case of a finite-state transducer, the output it produces). Therefore, decidability doesn't really enter into it.

If you know the number of states in the FSM of the Turing machine, yes, observing its behavior on finitely many strings is enough. You can use Biermann's algorithm to infer a FSM that is consistent with the observed behavior.

You can think of Biermann's algorithm as basically just using SAT, where for each string $u$, you have a variable $s_u$ to represent the state the FSM is in after reading string $u$. If the FSM has $n$ states, then each $s_u$ must be one of $n$ possible values. You can use the outputs to deduce some relationships on these variables: e.g., the FSM's behavior on input sequence $u$ differs from its behavior on input sequence $v$, then we obtain the constraint $s_u \ne s_v$. Also, you get some additional relationships due to the fact that this is a FSM: $s_u = s_v \implies s_{uw} = s_{vw}$ for all $u,v,w$.

Biermann's algorithm yields an (exponential-time) algorithm for finding a FSM that is consistent with all of the observations, if one exists. Learning a FSM given just membership queries is NP-hard, so you can't expect a more efficient solution in this model.

Biermann's algorithm only promises to give you a FSM that is consistent with all of the observations. How do we know whether this will match the FSM of the Turing machine? In general, we don't, but in this case we can use our knowledge of the number of states of the FSM to solve this. In particular, suppose we know there are $n$ states in the FSA of the Turing machine (after it has been minimized). We apply Biermann's algorithm to check whether there exists a FSM that's consistent with all the observations and uses $n$ states, and use Biermann's algorithm to check whether there exists a FSM that's consistent with all the observations and uses $n-1$ states. If the answers are yes and no, respectively, we are done. If the answers are yes and yes, then we generate more observations until we're done (this can be done systematically in a way that will terminate, by using knowledge of the candidate FSM with $n-1$ states).

I am assuming by "observe its behavior" you mean "observe each step of the execution of the Turing machine on some input". This lets you treat the FSM as a finite-state transducer and observe the output of the FSM for any desired sequence of inputs, by providing an appropriate input to the Turing machine.

If you don't know the number of states in the FSM, it's easy to prove that you can never know when you have the full thing (this is an easy adversary argument).

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback