Re: Some simple undecidable languages questions.



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
.