Solved

# Formulate Turing Machine.

Posted on 2011-04-27
430 Views
Given a Turing machine M a string w and a symbol x, determine whether M
writes symbol x on the tape during the computation on input string w. Hint: use a similar reduction as in the state-entry problem which we described in class.

My solution is:
L={<M>|M is a TM and M prints the symbol x on its tape}.
1) Assume that is decidable and R is the decider.
2) Then we can use R and construct a TM S to decide the halting
problem.

S="On input <M,w>, where M is a TM and w is a string:
1. Construct M1 such that M1 writes a special symbol on the tape,
say symbol #, if and only if the machine halts. We choose the special
symbol # to be different from any other symbol written on the tape.
We can easily construct machine M1 as follows. Machine M1 is
identical to machine M. The only difference is that in M1 we add
transitions from every halting state of M to a new state, and in
these transitions we write the symbol # on the tape.
2. Run R on <M1,w,#>.
3. If R accepts, accept; if it rejects, reject.

3) But the halting problem is not decidable therefore R cannot exists.

Is it a right proof? Thanks.
0
Question by:Mr_Lee

LVL 37

Expert Comment

This shows the undecidability of the state entry problem
www.cs.rpi.edu/~drinep/modcomp/class20.ppt

So you should reduce the halting problem to your problem. This appears to be what you tried to do, but why use # instead of x?
0

Author Comment

I thought that I can implicitly understand "symbol" x is anything, and # is one of the thing. I thought x can be @, or !, or so on.
0

LVL 37

Accepted Solution

Oh I see. I took it literally to mean x. Yes then. I agree with your proof.
0

LVL 37

Assisted Solution

I would use the same name x when writing the proof though so it's clear.
0

## Featured Post

### Suggested Solutions

This article is meant to give a basic understanding of how to use R Sweave as a way to merge LaTeX and R code seamlessly into one presentable document.
Displaying an arrayList in a listView using the default adapter is rarely the best solution. To get full control of your display data, and to be able to refresh it after editing, requires the use of a custom adapter.
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…
In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …