Formulate Turing Machine.

Posted on 2011-04-27
Last Modified: 2012-06-27
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

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.
Question by:Mr_Lee
    LVL 37

    Expert Comment

    This shows the undecidability of the state entry problem

    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?

    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.
    LVL 37

    Accepted Solution

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

    Assisted Solution

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

    Featured Post

    Find Ransomware Secrets With All-Source Analysis

    Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

    Join & Write a Comment

    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 …

    745 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    17 Experts available now in Live!

    Get 1:1 Help Now