• Status: Solved
• Priority: Medium
• Security: Public
• Views: 414

# Undecidable Language

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).
0
Mr_Lee
• 3
• 2
1 Solution

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

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

Commented:
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.
0

Author Commented:
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?
0

Commented:
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.
0

## Featured Post

• 3
• 2
Tackle projects and never again get stuck behind a technical roadblock.