Undecidable Language

Posted on 2011-04-27
Last Modified: 2012-05-11
This is a practice problem. I have a Turing Machine M, determine if L(M) = {you, are, very, welcome}. Formulate this as a language and show that it is undecidable (hint: using reduction which is similar to Empty, Regular, and Size-2 language problems).
Question by:Mr_Lee
    LVL 37

    Expert Comment

    It doesn't look undecidable yet to me. Is there more to the problem definition than that?

    Author Comment

    That's all. However, I restate the hint: use a similar reduction as in the Empty, Regular, and Size-2 language problems.
    LVL 37

    Expert Comment

    Oh, I get it. The language accepts 4 strings. I'll refine the hint. Size-2 says that a language that acceps 2 strings is undecidable. So what about 4 strings?

    Also, since regular languages are undecidable, you could just show (without any reductions) that L(M) is regular.

    Author Comment

    So 4-strings will be the union of the two size-2's. And regular language is closed under union. I did not get your last statement? L(M) is regular itself. You mean I have to show it is regular?
    LVL 37

    Accepted Solution

    All I was saying was that you can choose which idea to use.
    You have three good options for how to prove this.

    1. You can reduce the size-2 to a size-4.

    2. You can look up the proof for size-2 and modify it for size-4

    3. Since regular languages are already undecidable, you could just proof that your language is regular.

    You only need to do one of the above. Pick whichever is easiest and you understand the most.

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Course: HTML5 Specialist

    HTML5 development skills are critical to all developers. HTML5 is the foundation to almost any development process. That's why business, design studios, development shops and other organizations need HTML5 developers. Get your foot in the door as a HTML5 specialist.

    Suggested Solutions

    Title # Comments Views Activity
    Excel object stays open 19 56
    countX 22 50
    algorithm 15 51
    countAbc challenge 9 35
    Introduction Many of the most common information processing tasks require sorting data sets.  For example, you may want to find the largest or smallest value in a collection.  Or you may want to order the data set in numeric or alphabetical order. …
    This is about my first experience with programming Arduino.
    Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
    In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

    737 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

    22 Experts available now in Live!

    Get 1:1 Help Now