Re: Questions on turing machine problems
- From: polymedes <polymedes@xxxxxxxxx>
- Date: Tue, 6 May 2008 13:00:45 -0700 (PDT)
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.
.
- Follow-Ups:
- Re: Questions on turing machine problems
- From: Harri Haanpaa
- Re: Questions on turing machine problems
- References:
- Questions on turing machine problems
- From: polymedes
- Re: Questions on turing machine problems
- From: Harri Haanpaa
- 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
|
