This is one of my assignments. I am not able to comprehend how to reduce the Turing machine domain to Classical planning domain. My understanding is that we have to essentially perform complexity analysis of classical planning domain. So I have defined these two languages

a) PLAN-EXISTENCE(D) = {P : P is the statement of a planning problem that has a solution}

b) PLAN-LENGTH(D) = {(P,n) : P is the statement of a planning problem that has a solution that contains no more than n actions (length ≤ n) }

And then I proceed to prove that both these are decidable in classical planning domain.

Is this the correct approach? Please help me


In order to show that the computation of a Turing machine can be modeled as a planning problem, you can encode the tape symbols, the head position and state, and the execution of a transition using states:

symb(i,x)   : i-th cell of the tape contains symbol x
head(i,q)   : head is over cell i in state q
exec(i,q,x) : execute the transition at i-th cell in state q over symbol x
accept      : accept the input

At the beginning symb(i,x) are true/false according to tape content; head(1, q0) is true; and all other states are false. The goal G is {accept}.

Actions are built using the transition table of the Turing machine; suppose that you have the transition:

 a, q0 -> b, q1, Left

Then for every cell i of the tape you can add the actions:

 symb(i,a) AND head(i,q0) => !head(i,a) AND exec(i,q0,a)
 exec(i,q0,a) AND symb(i,a) => !symb(i,a) AND symb(i,b)
 exec(i,q0,a) AND symb(i,b) => !exec(i,q0,a) AND head(i+1,q1)

The actions for the transitions to accepting states are similar.

Note that actions with only 2 positive preconditions and two postconditions are enough to "simulate" the behaviour of a Turing machine.

| cite | improve this answer | |
  • $\begingroup$ Nice response! I voted it up! As a matter of fact, you can find in Tom Bylander, The Computational Complexity of Propositional STRIPS Planning a modelling which actually follows very closely Vor's recommendations $\endgroup$ – Carlos Linares López Feb 8 '13 at 12:34
  • $\begingroup$ @CarlosLinaresLópez: it is the same! I wrote the answer using some notes I wrote while reading Baylander's proof of the PSPACE-completeness of (2+/2), (* /1), (1/ *) STRIPS :-) ... indeed in the context of this question the three actions can be simplified as a single one (and there is no need of the exec(i,q,x) states). $\endgroup$ – Vor Feb 8 '13 at 13:29
  • $\begingroup$ I just used my memory and I thought your notation follows that because it really recalled me Bylander's notation. Thanks for letting me know they are actually the same $\endgroup$ – Carlos Linares López Feb 8 '13 at 14:39

You should show that every Turing machine could be molded as a planning problem and vise versa. As a hint consider that any Turing machine consists of very simple actions (using action tables) and complex action in planning problem could be done by simple Turing machine.

| cite | improve this answer | |

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.