Skip to main content
added 645 characters in body
Source Link

It's claim 1 from Bader Abu Radi's solution to this question.

My solution (have no idea how wrong it is):
$B$ finite $\Rightarrow$ $B\in R \Rightarrow$ exists TM $\langle M_B\rangle$ that halts $B$.

*Wrong from here
Let's define reduction $f$ from $A$ to $A \setminus B$, in the following way $f(\langle M_B\rangle , x)=\langle M_A\rangle$

When $M_A$ implemented on input $w$ like this:

  1. Run $M_B$ on $w$ and answer on the same way

$x\in B \Rightarrow M_B$ accept $x\Rightarrow M_A$ accept $x\Rightarrow x\in M_A$

$x\notin B \Rightarrow M_B$ reject $x\Rightarrow M_A$ reject $x\Rightarrow x\notin M_A$
till here

So the reduction $A \le_m A \setminus B$ true.

As I wrote early not sure how wrong is it, additionaly what're the changes that should be done to proof the second claim ($A \setminus B \le_m A$) from the same answer.

Edit

$f(x)=x'=x\setminus x_B$ (when $x_B$ is all the $x$ that accepted by $M_B$), because $M_B$ halts on $B$ the reduction is applicable and work for any $x$.
It's implemented in the following way:

  1. run $M_B$ on $x$ (halts), if $M_B$ accept, $x'$ reject
  2. otherwise return $x$

If $x\notin A \Rightarrow x'\notin A \setminus B$
If $x\in A$:
$x\in B \Rightarrow M_B$ accept $x \Rightarrow x'$ reject $\Rightarrow x'\notin A\setminus B$
$x\notin B \Rightarrow M_B$ reject $x \Rightarrow x'=x\Rightarrow x'\in A\setminus B$

Is this one correct? Should something be added to it?

It's claim 1 from Bader Abu Radi's solution to this question.

My solution (have no idea how wrong it is):
$B$ finite $\Rightarrow$ $B\in R \Rightarrow$ exists TM $\langle M_B\rangle$ that halts $B$.
Let's define reduction $f$ from $A$ to $A \setminus B$, in the following way $f(\langle M_B\rangle , x)=\langle M_A\rangle$

When $M_A$ implemented on input $w$ like this:

  1. Run $M_B$ on $w$ and answer on the same way

$x\in B \Rightarrow M_B$ accept $x\Rightarrow M_A$ accept $x\Rightarrow x\in M_A$

$x\notin B \Rightarrow M_B$ reject $x\Rightarrow M_A$ reject $x\Rightarrow x\notin M_A$

So the reduction $A \le_m A \setminus B$ true.

As I wrote early not sure how wrong is it, additionaly what're the changes that should be done to proof the second claim ($A \setminus B \le_m A$) from the same answer.

It's claim 1 from Bader Abu Radi's solution to this question.

My solution (have no idea how wrong it is):
$B$ finite $\Rightarrow$ $B\in R \Rightarrow$ exists TM $\langle M_B\rangle$ that halts $B$.

*Wrong from here
Let's define reduction $f$ from $A$ to $A \setminus B$, in the following way $f(\langle M_B\rangle , x)=\langle M_A\rangle$

When $M_A$ implemented on input $w$ like this:

  1. Run $M_B$ on $w$ and answer on the same way

$x\in B \Rightarrow M_B$ accept $x\Rightarrow M_A$ accept $x\Rightarrow x\in M_A$

$x\notin B \Rightarrow M_B$ reject $x\Rightarrow M_A$ reject $x\Rightarrow x\notin M_A$
till here

So the reduction $A \le_m A \setminus B$ true.

As I wrote early not sure how wrong is it, additionaly what're the changes that should be done to proof the second claim ($A \setminus B \le_m A$) from the same answer.

Edit

$f(x)=x'=x\setminus x_B$ (when $x_B$ is all the $x$ that accepted by $M_B$), because $M_B$ halts on $B$ the reduction is applicable and work for any $x$.
It's implemented in the following way:

  1. run $M_B$ on $x$ (halts), if $M_B$ accept, $x'$ reject
  2. otherwise return $x$

If $x\notin A \Rightarrow x'\notin A \setminus B$
If $x\in A$:
$x\in B \Rightarrow M_B$ accept $x \Rightarrow x'$ reject $\Rightarrow x'\notin A\setminus B$
$x\notin B \Rightarrow M_B$ reject $x \Rightarrow x'=x\Rightarrow x'\in A\setminus B$

Is this one correct? Should something be added to it?

deleted 30 characters in body
Source Link

It's claim 1 from Bader Abu Radi's solution to this question.

My solution (have no idea how wrong it is):
$B$ finite $\Rightarrow$ $B\in R \Rightarrow$ exists TM $\langle M_B\rangle$ that halts $B$.
Let's define reduction $f$ from $A$ to $A \setminus B$, in the following way $f(\langle M_B\rangle , x)=\langle M_A\rangle$

When $\langle M_A\rangle$$M_A$ implemented on input $w$ like this:

  1. Run $\langle M_B\rangle$$M_B$ on $w$ and answer on the same way

$x\in B \Rightarrow M_B$ accept $x\Rightarrow M_A$ accept $x\Rightarrow x\in M_A$

$x\notin B \Rightarrow M_B$ reject $x\Rightarrow M_A$ reject $x\Rightarrow x\notin M_A$

So the reduction $A \le_m A \setminus B$ true.

As I wrote early not sure how wrong is it, additionaly what're the changes that should be done to proof the second claim ($A \setminus B \le_m A$) from the same answer.

It's claim 1 from Bader Abu Radi's solution to this question.

My solution (have no idea how wrong it is):
$B$ finite $\Rightarrow$ $B\in R \Rightarrow$ exists TM $\langle M_B\rangle$ that halts $B$.
Let's define reduction $f$ from $A$ to $A \setminus B$, in the following way $f(\langle M_B\rangle , x)=\langle M_A\rangle$

When $\langle M_A\rangle$ implemented on input $w$ like this:

  1. Run $\langle M_B\rangle$ on $w$ and answer on the same way

$x\in B \Rightarrow M_B$ accept $x\Rightarrow M_A$ accept $x\Rightarrow x\in M_A$

$x\notin B \Rightarrow M_B$ reject $x\Rightarrow M_A$ reject $x\Rightarrow x\notin M_A$

So the reduction $A \le_m A \setminus B$ true.

As I wrote early not sure how wrong is it, additionaly what're the changes that should be done to proof the second claim ($A \setminus B \le_m A$) from the same answer.

It's claim 1 from Bader Abu Radi's solution to this question.

My solution (have no idea how wrong it is):
$B$ finite $\Rightarrow$ $B\in R \Rightarrow$ exists TM $\langle M_B\rangle$ that halts $B$.
Let's define reduction $f$ from $A$ to $A \setminus B$, in the following way $f(\langle M_B\rangle , x)=\langle M_A\rangle$

When $M_A$ implemented on input $w$ like this:

  1. Run $M_B$ on $w$ and answer on the same way

$x\in B \Rightarrow M_B$ accept $x\Rightarrow M_A$ accept $x\Rightarrow x\in M_A$

$x\notin B \Rightarrow M_B$ reject $x\Rightarrow M_A$ reject $x\Rightarrow x\notin M_A$

So the reduction $A \le_m A \setminus B$ true.

As I wrote early not sure how wrong is it, additionaly what're the changes that should be done to proof the second claim ($A \setminus B \le_m A$) from the same answer.

Source Link

For every non-trivial language $A$ and every finite strict subset $B \subsetneq A$, it's holds that $A \le_m A \setminus B$

It's claim 1 from Bader Abu Radi's solution to this question.

My solution (have no idea how wrong it is):
$B$ finite $\Rightarrow$ $B\in R \Rightarrow$ exists TM $\langle M_B\rangle$ that halts $B$.
Let's define reduction $f$ from $A$ to $A \setminus B$, in the following way $f(\langle M_B\rangle , x)=\langle M_A\rangle$

When $\langle M_A\rangle$ implemented on input $w$ like this:

  1. Run $\langle M_B\rangle$ on $w$ and answer on the same way

$x\in B \Rightarrow M_B$ accept $x\Rightarrow M_A$ accept $x\Rightarrow x\in M_A$

$x\notin B \Rightarrow M_B$ reject $x\Rightarrow M_A$ reject $x\Rightarrow x\notin M_A$

So the reduction $A \le_m A \setminus B$ true.

As I wrote early not sure how wrong is it, additionaly what're the changes that should be done to proof the second claim ($A \setminus B \le_m A$) from the same answer.