# Prove disprove an existence of mapping reduction between 2 sets

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.

• Try attacking the problem directly, i.e., constructing an instance of $B$ from an instance of $A$. – John L. May 22 '19 at 23:51
• @Apass.Jack, Thanks for the comment. – Tom.A May 23 '19 at 5:37
• @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. – Tom.A May 23 '19 at 5:45
• 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. – dkaeae May 23 '19 at 7:24
• $A = \{ (p, d) \mid p \text{ doesn't halt on input }d \}$. What is $p$? Is it a Turing machine? Or a program? – 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$$.

• 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. – Tom.A May 23 '19 at 15:41
• 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. – Tom.A May 23 '19 at 15:44
• Replace "Turing machine" and "machine" by program everywhere in the answer. – John L. May 23 '19 at 16:58
• $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.) – John L. May 23 '19 at 17:01
• 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! – Tom.A May 23 '19 at 17:14