[Solved]: Show that the Turing Machine domain can be viewed as a classical planning domain

Problem Detail: 

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

Asked By : Kom kom

Answered By : Vor

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9573