questions on turing machine problem
- From: polymedes <polymedes@xxxxxxxxx>
- Date: Tue, 6 May 2008 06:43:13 -0700 (PDT)
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?
2) Can somebody direct me to an analysis of the Post Correspondence
Problem when the alphabet of the dominos is a 1-character alphabet?
.
- Follow-Ups:
- Re: questions on turing machine problem
- From: Tim Little
- Re: questions on turing machine problem
- From: David Formosa (aka ? the Platypus)
- Re: questions on turing machine problem
- From: Julio Di Egidio
- Re: questions on turing machine problem
- Prev by Date: Re: Taylor and ODEs
- Next by Date: CHINA (www.overinstock.net) *** LV DUNK UGG BOOTS SHOES AT FACTORY PRICE
- Previous by thread: It's now or never。shopping in our company to get beijing2008 keepsake
- Next by thread: Re: questions on turing machine problem
- Index(es):