Skip to main content
deleted 1 character in body
Source Link
Bader Abu Radi
  • 4.9k
  • 1
  • 11
  • 38

From your attempt, I see that you got the intuition, but you need to define the reduction formally, and then prove that it works. In your solution, it is not clear how $M'$ is defined, and what is $M_{regular}$ -- for me, I just saw your thoughts/attempts, not a proof.

Here, I showed a slightly more general resultclaim, specifically, every non-trivial language is $R$-hard (harder than every language in $R$). Since $L\in R$, and $HP$ is non-trivial, then what you're asking for follows immediately. Try to prove that the reduction there is computable (there is a TM that computes it), and that it is correct.

The idea essentially is as follows. Since we can decide $L$, then we can define a reduction that checks whether its input is in $L$, and then outputs a word inside or outside $HP$, accordingly. So languages in $R$ are too easy, w.r.t mapping reductions, in the sense that we (the reduction) can solve/decide them, and then output whatever we want.

From your attempt, I see that you got the intuition, but you need to define the reduction formally, and then prove that it works. In your solution, it is not clear how $M'$ is defined, and what is $M_{regular}$ -- for me, I just saw your thoughts/attempts, not a proof.

Here, I showed a slightly more general result, specifically, every non-trivial language is $R$-hard (harder than every language in $R$). Since $L\in R$, and $HP$ is non-trivial, what you're asking follows immediately. Try to prove that the reduction there is computable (there is a TM that computes it), and that it is correct.

The idea essentially is as follows. Since we can decide $L$, then we can define a reduction that checks whether its input is in $L$, and then outputs a word inside or outside $HP$, accordingly. So languages in $R$ are too easy, w.r.t mapping reductions, in the sense that we (the reduction) can solve/decide them, and then output whatever we want.

From your attempt, I see that you got the intuition, but you need to define the reduction formally, and then prove that it works. In your solution, it is not clear how $M'$ is defined, and what is $M_{regular}$ -- for me, I just saw your thoughts/attempts, not a proof.

Here, I showed a slightly more general claim, specifically, every non-trivial language is $R$-hard (harder than every language in $R$). Since $L\in R$, and $HP$ is non-trivial, then what you're asking for follows immediately. Try to prove that the reduction there is computable (there is a TM that computes it), and that it is correct.

The idea essentially is as follows. Since we can decide $L$, then we can define a reduction that checks whether its input is in $L$, and then outputs a word inside or outside $HP$, accordingly. So languages in $R$ are too easy, w.r.t mapping reductions, in the sense that we (the reduction) can solve/decide them, and then output whatever we want.

added 24 characters in body
Source Link
Bader Abu Radi
  • 4.9k
  • 1
  • 11
  • 38

From your attempt, I see that you got the intuition, but you need to define the reduction formally, and then prove that it works. In your solution, it is not clear how $M'$ is defined, and what is $M_{regular}$ -- for me, I just saw your thoughts/attempts, not a proof.

Here, I showed thata slightly more general result, specifically, every non-trivial language is $R$-hard, that is, harder (harder than every language in $R$). Since $L\in R$, and $HP$ is non-trivial, what you're asking follows immediately. Try to prove that the reduction there is computable (there is a TM that computes it), and that it is correct.

The idea essentially is as follows. Since we can decide $L$, then we can define a reduction that checks whether its input is in $L$, and then outputs a word inside or outside $HP$, accordingly. So languages in $R$ are too easy, w.r.t mapping reductions, in the sense that we (the reduction) can solve/decide them, and then output whatever we want.

From your attempt, I see that you got the intuition, but you need to define the reduction formally, and then prove that it works. In your solution, it is not clear how $M'$ is defined, and what is $M_{regular}$ -- for me, I just saw your thoughts/attempts, not a proof.

Here, I showed that every non-trivial language is $R$-hard, that is, harder than every language in $R$. Since $L\in R$, and $HP$ is non-trivial, what you're asking follows immediately. Try to prove that the reduction there is computable (there is a TM that computes it), and that it is correct.

The idea essentially is as follows. Since we can decide $L$, then we can define a reduction that checks whether its input is in $L$, and then outputs a word inside or outside $HP$, accordingly.

From your attempt, I see that you got the intuition, but you need to define the reduction formally, and then prove that it works. In your solution, it is not clear how $M'$ is defined, and what is $M_{regular}$ -- for me, I just saw your thoughts/attempts, not a proof.

Here, I showed a slightly more general result, specifically, every non-trivial language is $R$-hard (harder than every language in $R$). Since $L\in R$, and $HP$ is non-trivial, what you're asking follows immediately. Try to prove that the reduction there is computable (there is a TM that computes it), and that it is correct.

The idea essentially is as follows. Since we can decide $L$, then we can define a reduction that checks whether its input is in $L$, and then outputs a word inside or outside $HP$, accordingly. So languages in $R$ are too easy, w.r.t mapping reductions, in the sense that we (the reduction) can solve/decide them, and then output whatever we want.

Source Link
Bader Abu Radi
  • 4.9k
  • 1
  • 11
  • 38

From your attempt, I see that you got the intuition, but you need to define the reduction formally, and then prove that it works. In your solution, it is not clear how $M'$ is defined, and what is $M_{regular}$ -- for me, I just saw your thoughts/attempts, not a proof.

Here, I showed that every non-trivial language is $R$-hard, that is, harder than every language in $R$. Since $L\in R$, and $HP$ is non-trivial, what you're asking follows immediately. Try to prove that the reduction there is computable (there is a TM that computes it), and that it is correct.

The idea essentially is as follows. Since we can decide $L$, then we can define a reduction that checks whether its input is in $L$, and then outputs a word inside or outside $HP$, accordingly.