Re: Questions on turing machine problems

On 2008-05-06, polymedes <polymedes@xxxxxxxxx> wrote:
On May 6, 10:25 pm, Harri Haanpaa <har...@xxxxxxxxx> wrote:
On 2008-05-06, polymedes <polyme...@xxxxxxxxx> 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.

*I* can be absolutely convinced having worked out a proof. *I* do
not need to provide *you* a proof to be convinced. *You* cannot
convince *yourself* without being served a proof. To me this looked
like a homework problem, so I only wanted to provide a hint.

It's fairly easy to show that your problem remains undecidable even
if M_1 is a TM that only keeps outputting the same character in
every computation step and never terminates.

BTW, I'm not entirely convinced by Tim's argument; his simulating
machine has a very special form and sometimes the halting problem
may be decidable for machines that have a special form. Suppose,
for example, that we would be restricted to TM's that only have a
single character in their tape alphabet, that is, they *always*
output the character c in every step of the computation. Wouldn't
Tim's argument, exactly as it is, suggest that this problem too
would be undecidable?

Harri

.

Relevant Pages