Re: Questions on turing machine problems
- From: polymedes <polymedes@xxxxxxxxx>
- Date: Tue, 6 May 2008 12:11:50 -0700 (PDT)
On May 6, 9:26 pm, Tim Tyler <seemy...@xxxxxxxxxxxxxx> 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...@xxxxxxxxxxx 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?
.
- Follow-Ups:
- Re: Questions on turing machine problems
- From: Tim Tyler
- Re: Questions on turing machine problems
- References:
- Questions on turing machine problems
- From: polymedes
- Re: Questions on turing machine problems
- From: Tim Tyler
- Questions on turing machine problems
- Prev by Date: Re: Questions on turing machine problems
- Next by Date: Re: Questions on turing machine problems
- Previous by thread: Re: Questions on turing machine problems
- Next by thread: Re: Questions on turing machine problems
- Index(es):
Relevant Pages
|
