# Show that the Turing Machine domain can be viewed as a classical planning domain

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.

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
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.

• 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.