The post correspondence problem is, to my understanding, given two ordered collections of strings with the same cardinality, i.e., $\{t_1, t_2, \dots, t_n\}$ and $\{w_1, w_2, \dots, w_n\}$, does there exist a rearrangement of the terms such that $t_{i_1} t_{i_2} \dots t_{i_n} = w_{i_1} w_{i_2} \dots w_{i_n}$? Sipser's text has a proof that this problem is undecidable. This strikes me as counterintuitive: if our two sets are finite, there should only exist $n!$ different possible orderings of the strings. Why can a Turing machine not simply test all $n!$ cases and reject if none of these cases produce a match?
Why is the post correspondence problem undecidable
decidabilityturing-machines
Related Solutions
Your attempt to answer is a bit hard to read, but the key elements for the right answer are already there:
The DFA will always halt on the empty string as input (as on any other). Therefore also a simulation of this DFA by the Turing Machine will come to an end. So you can let the Turing Machine simulate the DFA in the input and then check, whether the DFA has accepted or not. Since the FA is deterministic there is only one computation to simulate and the answer is definite. For NFAs you would have to simulate all possible paths in the worst case.
This approach works for any string. As you have observed correctly in the comments, the empty string is accepted only if the start state is an accepting one. Thus in your case the simulation consists only in checking whether the DFA's start state is accepting. The technical details depend on the way in which the DFA is encoded on the TM-tape.
There is a helpful construction for this type of problems
This problem asks you to use this construction to show that AMBIGcfg is undecidable
Hopefully you can see that T generates a string from the upper strings and B generates a string from the lower strings
The terminals at the end encode the sequence of "dominos" used , so if T generates a string (assume that the alphabet for this PCP Instance is {a,b}) : aaab12 and B generates a string aaab12 , then a match was found , that is because we formed the match aaab using the same sequence of dominos 12 (here we use domino 2 then 1 think about it !) , this encoding guarantees that both T which uses the upper strings and B which uses the lower strings have used dominos in the same order when they formed the match
A further example to emphasis the idea , assume we use T --> t1 T a1 , then use T --> t2 a2 we generate the string t1 t2 a2 a1 , the string generated by dominos is t1 t2 and the sequence of dominos used is a1 then a2 , once again ,if B generates a string b1 b2 a2 a1, where b1 b2 = t1 t2 , then we found a match , since strings are the same with same sequence of dominos used , hopefully by now you understand how the construction works and are convinced that T and B generate the same string only if we have a match
In this problem , if both T and B generate the same string , the grammer is ambiguous and we accept , else we reject , deciding the PCP
Now can you tweek this construction for our problem ?
We replace S --> T|B by S -->TB , and replace every rule B --> bi B ai by B --> ai B bi , and replace every rule B --> bi ai by B --> ai bi ( reversing the strings on right side of rules which have B on left side )
If a match w exists , then T would generate w , and B would generate w^R , then TB is ww^R which is palindrome , ex : if w is aaab12 then T generates aaab12 and B generates 21baaa , so S is aaab1221baaa , which is a palindrome
I leave it you you to convince your self that the only way for a palindrome to exist is to have a match , if you consider that a match is represented in our grammer by the string followed by a unique sequence of dominos used for this string , then it should be easy to see how it works
So construct G with rules provided above , we assume that a decider R exists for L , we run L on < G> ,
If a match exists G generates some palindrome and L accepts
If a match doesn't exist , G generates no palindromes , and L rejects
Best Answer
The issue is with your description of the post correspondence problem: it's not a rearrangement of the ordered collections of strings, just a selection of indices $i_1, \ldots, i_m$, not necessarily comprehensive and possibly with repeats, and $m$ does not have to be $n$, such that $t_{i_1} t_{i_2} \cdots t_{i_m} = w_{i_1} w_{i_2} \cdots w_{i_m}$. So the algorithm you suggest can't work because there's no bound on the allowable value of $m$, so the search space is no longer finite.