Questions on turing machine problems
in [Theory]
|
Prev: QuickSort (worst-cases... special data)
Next: Calls for Papers: International Conference on Communications Systems and Technologies (ICCST 2008)
From: polymedes on 6 May 2008 11:42 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?
From: polymedes on 6 May 2008 15:11
On May 6, 9:26 pm, Tim Tyler <seemy...(a)googlemail.com> wrote: > polymedes wrote: > > 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? > > These TMs will probably write the same symbol on the tape at > /every/ step - unless you explain in what way they differ. > -- > __________ > |im |yler http://timtyler.org/ t...(a)tt1lock.org Remove lock to reply. in general, they are not the same TM. but the problem is to _decide_ if there is a (i.e. at least one) natural number n for which the two (different) TMs will write the same symbol on the tape on step n. In other words,let L = {<M,N,w> | There is n such that M and N (with input w) write the same symbol on tape on step n} Is L decidable? |