1
$\begingroup$

I am prety stuck over here:

prove or disprove that every $L$ got $L'$ s.t $L'\geq L$ and for every $L''\geq L$

$L''\ngeq L'$

basically it means L' is the hardest...

my intuition tells me that this is correct, but I cant prove why. I tried to prove using counting but got stuck:

  1. we got $\aleph_0$ pairs of functions that we can use in the reduction for both ways

  2. we got $\aleph$ languages so there must be a language that got a function to compute the redaction in one way and doesnt got a function for the reduction to the other way

Its feels terribly incorrect any help will be appreciated

EDIT: I just realized that I didn't write the question correctly please read it again.

Improve this question
$\endgroup$
0
2
$\begingroup$

The halting problem for a class of machines that can decide $L$ is always harder than $L$. You already know this when $L$ is computable and the proof of the more general result is essentially the same. For every $L$, you need to think of a class of machines that can decide $L$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I cant understand, if the language is not in $RE$ than how can I use the halting problem? $\endgroup$ – misha312 Feb 17 '18 at 13:24
  • $\begingroup$ Don't use the halting problem for ordinary Turing machines. You need to think of a class of machines that can decide the langauge you're working with. $\endgroup$ – David Richerby Feb 17 '18 at 13:26
  • $\begingroup$ you mean some-thing like $Ld$ ? $\endgroup$ – misha312 Feb 17 '18 at 13:29
  • $\begingroup$ I don't know what you mean by that. $\endgroup$ – David Richerby Feb 17 '18 at 13:44
  • $\begingroup$ all the TM machines that doesn't accept their encoding $\endgroup$ – misha312 Feb 17 '18 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.