Show that for each TMM there is a TM M'which computes the same partial

function as M, but which never moves left of the initially scanned square of

any initial tape?

Honeslty, I don't get what the question is asking me.

Printable View

- Apr 4th 2011, 06:17 PMikurwae89Turing Machine ProblemShow that for each TMM there is a TM M'which computes the same partial

function as M, but which never moves left of the initially scanned square of

any initial tape?

Honeslty, I don't get what the question is asking me.

- Apr 5th 2011, 05:16 AMemakarov
I think the question is pretty clear. Be sure to read the description of Turing machines used in your course.

Basically, a TM with a two-way infinite tape can be simulated by a TM with two tapes that are infinite only to the right. The portion of the original TM's tape from the initial square to the left is modeled by one tape, and the portion from the initial square to the right is modeled by the second tape. In turn, a two-tape machine can be simulated by a one-tape machine. This should be described in most books about the subject, for example, in Elements of the Theory of Computation by Lewis and Papadimitriou.

If you still have questions about the formulation of the problem, please specify which terms or concepts are not clear. - Apr 6th 2011, 06:15 PMikurwae89
Can you show me an example? Also how do I set out an answer?

My understanding of the question goes like this, There is a TM M, which computes a partial funtion, but what we want is a TM M' which computes the same partial function BUT never moves left of the initially scanned square.

How would I set out my answer?

Can I make an example?

Thanks - Apr 7th 2011, 12:14 PMemakarov
When proving something about Turing Machines, it is often almost impossible to write down all the details because constructing TMs for complicated computations is extremely laborious and tedious. Besides, writing a concrete TM adds little to intuitive understanding of what is going on. As a result, most proofs about TMs are hand-waving, though good proofs are still able to convince others who had enough experience with such hand-waving. This reminds me somewhat of religious traditions that are not precisely written down the way scriptures are (and, some claim, cannot be written down precisely), so that the only way to master them is to practice them under the supervision of experts.

I'll PM you a text describing how a two-way infinite TM can be simulated first by a one-way infinite TM with two tapes and then by a one-way infinite TM with one tape.