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
.
 FollowUps:
 Re: Some simple undecidable languages questions.
 From: cooldavid
 Re: Some simple undecidable languages questions.
 References:
 Some simple undecidable languages questions.
 From: cooldavid
 Some simple undecidable languages questions.
 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):
Relevant Pages
