Show that the Turing Machine domain can be viewed as a 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
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 -&gt; b, q1, Left


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

 symb(i,a) AND head(i,q0) =&gt; !head(i,a) AND exec(i,q0,a)
 exec(i,q0,a) AND symb(i,a) =&gt; !symb(i,a) AND symb(i,b)
 exec(i,q0,a) AND symb(i,b) =&gt; !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.