questions on turing machine problem



1) I'm trying to understand the following problem: let M_1 and M_2 two
turing machines with common input alphabet and a given string x. Is
there a particular step in which the two machines will write the same
symbol on the tape?

is it undecidable? can somebody give an idea on how can we reduce this
problem to an undecidable problem?

2) Can somebody direct me to an analysis of the Post Correspondence
Problem when the alphabet of the dominos is a 1-character alphabet?

.


Quantcast