Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer
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 – Carlos Linares López Feb 8 '13 at 12:34
@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). – Vor Feb 8 '13 at 13:29
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 – 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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