Re: Questions on turing machine problems
- From: Tim Tyler <seemysig@xxxxxxxxxxxxxx>
- Date: Tue, 06 May 2008 20:27:20 +0100
polymedes wrote:
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_2These TMs will probably write the same symbol on the tape at
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?
/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@xxxxxxxxxxx Remove lock to reply.
.
- Follow-Ups:
- Re: Questions on turing machine problems
- From: polymedes
- Re: Questions on turing machine problems
- References:
- Questions on turing machine problems
- From: polymedes
- Re: Questions on turing machine problems
- From: Tim Tyler
- Re: Questions on turing machine problems
- From: polymedes
- 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
|
