Questions on turing machine problems
in [Theory]
|
Prev: domains for typed lambda calculi
Next: Another approach to decide on existence of a real root for Univariate Polynomials with Integer Coefficients, and a possible Multivariate extension for 3-SAT
From: Tim Tyler on 6 May 2008 14:26 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/ tim(a)tt1lock.org Remove lock to reply.
From: Harri Haanpaa on 6 May 2008 15:25 On 2008-05-06, polymedes <polymedes(a)gmail.com> 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? > is it undecidable? can somebody give an idea on how can we reduce > this > problem to an undecidable problem? Well *surely* it must be undecidable. You have not only one but *two* Turing machines that can be arbitrarily messy. And *one* messy Turing machine is usually enough to make a problem undecidable, isn't it. I'm absolutely convinced that there are really simple M_1 for which this problem remains undecidable... Harri H.
From: Tim Tyler on 6 May 2008 15:27 polymedes wrote: > 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. > > 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? If the machines are different, then the problem of whether they write the same symbol at the same time can be transformed into a halting problem - e.g. consider a third machine that simulates the first two machines and halts iff the simulated machines output the same symbol on their tapes at the same time. -- __________ |im |yler http://timtyler.org/ tim(a)tt1lock.org Remove lock to reply.
From: polymedes on 6 May 2008 15:58 On May 6, 10:27 pm, Tim Tyler <seemy...(a)googlemail.com> wrote: > polymedes wrote: > > 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. > > > 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? > > If the machines are different, then the problem of whether they > write the same symbol at the same time can be transformed into > a halting problem - e.g. consider a third machine that simulates > the first two machines and halts iff the simulated machines > output the same symbol on their tapes at the same time. > -- > __________ > |im |yler http://timtyler.org/ t...(a)tt1lock.org Remove lock to reply. This is a great answer! thanks for helping. Any ideas for the PCP?
From: polymedes on 6 May 2008 16:00
On May 6, 10:25 pm, Harri Haanpaa <har...(a)yahoo.com> wrote: > On 2008-05-06, polymedes <polyme...(a)gmail.com> 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? > > is it undecidable? can somebody give an idea on how can we reduce > > this > > problem to an undecidable problem? > > Well *surely* it must be undecidable. You have not only one but > *two* Turing machines that can be arbitrarily messy. And *one* messy > Turing machine is usually enough to make a problem undecidable, > isn't it. I'm absolutely convinced that there are really simple M_1 > for which this problem remains undecidable... > > Harri H. You cannot be absolutely convinced, unless you provide a proof. See above the one provider by Tim Tyler. Anyway, thanks for you time. |