Re: Questions on turing machine problems

On May 6, 10:27 pm, Tim Tyler <seemy...@xxxxxxxxxxxxxx> wrote:
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_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...@xxxxxxxxxxx  Remove lock to reply.

This is a great answer! thanks for helping. Any ideas for the PCP?

.

Relevant Pages

  • Re: Ayre C-5xe Universal "Silver Disc" Player
    ... flute, on the disk, which has very fine piano sound. ... once before recording just to "loosen them up". ... Tapes were played on/recorded from a Teac 4070 tape ... moderate-quality tape machines like the Teac 4070 is well known among ...
    (rec.audio.opinion)
  • Re: Ayre C-5xe Universal "Silver Disc" Player
    ... tape, isn't 0.1 dB stable over the audio band. ... You are simply obfuscating Arny, ... tape when played by moderate-quality tape machines like ... Harry apparently lives in an imaginary universe where mid-fi analog tape ...
    (rec.audio.opinion)
  • Re: Ayre C-5xe Universal "Silver Disc" Player
    ... Your reference source, the Dolby ... Evaluating 16/44 using a third-rate analog tape machine and a consumer ... there's a strong random variable - the third-rate analog tape machine ... analog tape machines playing wide tracks at high speeds. ...
    (rec.audio.opinion)
  • Re: WANT TO TRADE: MAGNATONE CUSTOM 280 AMP FOR PAIR OF AMPEX 350 PREAMPS
    ... Look, if you want to fuck up some perfectly good tape machines, it's your ... Folks who work with machinery daily come to respect it, ... The modern paradigm (brother, can you spare a ...
    (rec.audio.pro)
  • Re: VHS Tracking Question...
    ... have a very narrow adjustment field whereas my old machines would track ... and forget about adjustable recording volume. ... that's when you saw the vhs machines get really ... released extra long tape which easily stretched once it was heated in the ...
    (rec.arts.tv)