Skip to main content
1 of 2
Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k

The quotient of one language $L$ by another $R$ is the set of strings $x$ such that $xy\in L$ for some $y\in R$.

If both $L$ and $R$ are computably enumerable (what you call RE), then the quotient is clearly enumerable, since we can simply search for all strings $x$ and $y$ such that $xy\in L$ and $y\in R$, and when found, output $x$. This will enumerate the quotient $L/R$.

But in the case of decidable sets (what you call R), it is not true that the quotient is necessarily decidable. To see this, let $L$ be the sets of strings consisting of strings of the form $xy$, where $x$ codes a Turing machine program $p$ and input $n$ (with a suitable end-of-code marker) and $y$ codes the halting computation of $p$ on $n$, provided that it does halt. And let $R$ be the string with just the strings $y$ coding the halting computations. These are each decidable, since we can look at a string and easily decide if it codes the information or not.

But the quotient $L/R$ will consist of strings coding the halting TM program and input pairs that halt. That is, it is the halting problem, and this is not decidable.

Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k