# Re: Some simple undecidable languages questions.

*From*: Chris Smith <cdsmith@xxxxxxx>*Date*: Tue, 6 Feb 2007 15:48:58 -0700

cooldavid <vmvictorvm@xxxxxxxxx> wrote:

Let S = natural numbers

L = {< M > | M is a TM over S, M accepts "8000"}

L is undecidable(not recursive), but recognizable(recursively

enumerable).

Are the languages below same(undecidable, recognizable) as L above?:

Where did you get these from?

Let S = natural numbers

L2 = {< M > | M is a TM over S, M accepts "8000", otherwise rejects}

This doesn't make sense to me. Is this asking about the language of all

deciders for { "8000" }? Do you understand the question yourself?

L3 = {w | w is a natural number, and w = 8000}

This one should be obvious.

L4 = {< M,w > | M is a TM, w is a natural number. M accepts if w =

"8000"}

Try a reduction to and from L.

L5 = {< M,w > | M is a TM, w is a natural number. For some w, M(w)

outputs "8000"}

This can be solved with reasoning similar to what establishes the given

properties for L.

And for some reasons, I can?t really tell much difference between the

above languages and L.

Can you explain more? Some of them, esp. L3, seem radically different

from L.

--

Chris Smith

.

**Follow-Ups**:**Re: Some simple undecidable languages questions.***From:*cooldavid

**References**:**Some simple undecidable languages questions.***From:*cooldavid

- Prev by Date:
**Some simple undecidable languages questions.** - Next by Date:
**Re: Some simple undecidable languages questions.** - Previous by thread:
**Some simple undecidable languages questions.** - Next by thread:
**Re: Some simple undecidable languages questions.** - Index(es):