Re: questions on turing machine problem

[I'm not an expert in the field, so anyone please feel free to drop in and correct eventual mistakes/misunderstandings.]

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?

Let's assume that by "let M_1 and M_2 two turing machines" you imply that you know which list of transformation rules they are respectively made of.

Now, if you think of the 1-symbol alphabet, to which AFAIK any machine can be reduced to work upon, of course they'll write the *same* symbol as soon as they write *any* symbol.

So the problem becomes, will they write any symbol at all? That, I suppose, can be easily ascertained by confronting the rules to the given initial string.

BTW, I was given this kind of puzzle at a recent job interview, with a couple of rules and an initial string. That string was not producible at all given the rules, so I could straight answer "no", but my examiner was not happy at all. I still wander why...


is it undecidable? can somebody give an idea on how
can we reduce this
problem to an undecidable problem?

As I have tried to show, it should not be undecidable, but I might be wrong.


2) Can somebody direct me to an analysis of the Post
Correspondence
Problem when the alphabet of the dominos is a
1-character alphabet?

Sorry, I am not able to answer that.

Hope this can be a starting point.

-LV
.

Relevant Pages

  • Questions on turing machine problems
    ... turing machines with common input alphabet and a given string x. ... problem to an undecidable problem? ... Problem when the alphabet of the dominos is a 1-character alphabet? ...
    (comp.theory)
  • questions on turing machine problem
    ... turing machines with common input alphabet and a given string x. ... problem to an undecidable problem? ... Problem when the alphabet of the dominos is a 1-character alphabet? ...
    (sci.math)
  • Re: Questions on turing machine problems
    ... polymedes wrote: ... two turing machines with common input alphabet and a given string x. ...
    (comp.theory)
  • Re: Magic Excel function or UDF?
    ... When I entered this the word was in C5 and the alphabet string was in A18. ... Function GetIndex(sWord As String, sAlphabet As String) _ ... Dim i As Integer, iPos As Integer ...
    (microsoft.public.excel.programming)
  • Re: Getting a random letter.
    ... private string DoLameEncryption ... Dim RandomClass As New Random ... start with a random letter of the alphabet, ... having to loop through it all? ...
    (microsoft.public.dotnet.framework.aspnet)