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
.

Relevant Pages

  • Re: Are we moving for AK47?
    ... We've been shopping Odom for the longest time. ... We'd definitely have most teams beat in the languages ... department, esp. ...
    (alt.sports.basketball.nba.la-lakers)
  • Re: USB power off
    ... other languages (esp. ... German), can you restate your question in that ...
    (microsoft.public.development.device.drivers)
  • Re: Is JavaScript "completely unrelated" to Java?
    ... Chris Smith wrote: ... and an attempt at mangling Java. ... "portable across programming languages"? ... I even went to the trouble of clicking the "Rate ...
    (comp.lang.java.programmer)