I am currently studying mapping reduction in computational theory and finding it hard to grasp the concept fully.

For reference, consider the following given WHILE-Prog sets:

A = { (p.d) | p doesn't halt on input d } = Complementary HALT set. B = { p | p halts on exactly one input (the input is unknown) }

Is A < B. meaning, is there a mapping reduction from A to B?

Can someone suggest a hint?

knowing that A belongs to coRE did not help much. B doesn't seem to belong to either RE nor coRE.

  • $\begingroup$ Try attacking the problem directly, i.e., constructing an instance of $B$ from an instance of $A$. $\endgroup$
    – John L.
    May 22 '19 at 23:51
  • $\begingroup$ @Apass.Jack, Thanks for the comment. $\endgroup$
    – Tom.A
    May 23 '19 at 5:37
  • $\begingroup$ @Apass.Jack , That's what I was trying to do, however, it seems to be very confusing. The mapping should behave as follows: 1. A -> B : it means that [p]d did not halt, so I should return a program q such that q halts on one particular input only. this is quite easy by returning a program that loopsforever on inputs different from nil. 2. not A -> not B: this is where I am mostly confused, as if [p]d halts, I should return q such that either one of the following occurs: 1. [q] doesn't halt on any input. 2. [q] halts on at least two inputs. $\endgroup$
    – Tom.A
    May 23 '19 at 5:45
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$
    – dkaeae
    May 23 '19 at 7:24
  • $\begingroup$ $A = \{ (p, d) \mid p \text{ doesn't halt on input }d \}$. What is $p$? Is it a Turing machine? Or a program? $\endgroup$
    – John L.
    May 23 '19 at 16:47

One basic idea is to observe that $B$ looks harder than $A$ since

  • we need to run a given Turing machine on one given input in order to find whether the pair is in $A$ but
  • we may need to run a given Turing machine on infinity many inputs in order to find whether it is in $B$.

That observation should motivate us to find a reduction from $A$ to $B$.

Suppose $(p,d)\in A$. Construct a machine that behaves as the following.

Upon an input string $s$, it checks whether $s$ is $d\sigma$, where $\sigma$ stand for a fixed letter in the alphabet.

  • If yes, it halts.
  • If no, it checks whether $s$ is $d$.
    • If no, it loops forever.
    • If yes, it simulate $p$ on $d$.

It should be routine to verify the construction above is indeed a reduction from $A$ to $B$.

  • $\begingroup$ Thank you for your answer. The course I am taking does not rely on a Turing machine even though it seems like the common way. As far as what I have learned thus far, the reduction should map instances from A TO B and from Complementary A to Complementary B. $\endgroup$
    – Tom.A
    May 23 '19 at 15:41
  • $\begingroup$ Can you explain what do you mean by comparing s to dσ ? never dealt with such inputs, just tree based inputs consisting of nil's e.g (nil.nil), ((nil.nil).nil), etc. $\endgroup$
    – Tom.A
    May 23 '19 at 15:44
  • $\begingroup$ Replace "Turing machine" and "machine" by program everywhere in the answer. $\endgroup$
    – John L.
    May 23 '19 at 16:58
  • $\begingroup$ $s$ is a string. $d\sigma$ means the string that is the string $d$ followed by the letter $\sigma$. "Checking whether $s$ is $d\sigma$" just means whether the string $s$ is equal to the string $d\sigma$, i.e., whether the first letter of $s$ and that of $d$ is the same, whether the second letter of $s$ and that of $d$ is the same, ..., whether the second last letter of $s$ and the last letter of $d$ is the same, and whether the last letter of $s$ is $\sigma$. (I assume, WLOG, every input is a string over some alphabet.) $\endgroup$
    – John L.
    May 23 '19 at 17:01
  • $\begingroup$ I got it! :) Thank you so much. A few things I would like to ask: 1. What guided you through the process? I am finding it hard to grasp how much it is possible to write a program that halts which relies on a program that doesn't. 2. Are there any relevant papers to review online for reference? Yet again, Thanks a lot! $\endgroup$
    – Tom.A
    May 23 '19 at 17:14

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.