3. Given input to ATM, construct an instance of Post Correspondence Problem. That is, create a...

 

Transcribed Image Text:

3. Given input to ATM, construct an instance of Post Correspondence Problem. That is, create a collection of tiles such that, if you can find a solution to this PCP instance, then you have found an accepting computation history. Show the computation history. Say that w is the string 121 and that the start state of M is 90. qo 1-1, R 2-1, R 92 91 93 1 0, L 1 3. Given input to ATM, construct an instance of Post Correspondence Problem. That is, create a collection of tiles such that, if you can find a solution to this PCP instance, then you have found an accepting computation history. Show the computation history. Say that w is the string 121 and that the start state of M is 90. qo 1-1, R 2-1, R 92 91 93 1 0, L 1