How to do reduction?

Question

I want to perform the following reduction:

$H_{any} = \{ w\#x\#y | M \text{ described by } w \ \text{accepts} \ x \ \text{or} \ y\}$ to the Halting problem.

The definition of a reduction in my book is:

$A \in \Sigma^*$ $B \in \Gamma^*$ A can be reduced to B when there exists a function:

$f: \Sigma^* \rightarrow \Gamma^* \\ x \in A \iff f(x)\in B$

So my idea from the beginning is to find/encode $x\#y$ into a variable so that we can pass it to $H$ (the halting problem) such that we only have one (variable).

So our function $f$ maps $w\#x\#y \rightarrow w\#z$ where $z = x\#y$

That doesn't 'feel' right, because $H$ cannot comprehend any input past the delimiter and never considers $y$, but since the halting problem doest not considers n-tuples of inputs I dont know if I can call it a day here.

I thought about encoding a turing machine into another $TM \ M'$ that simulates $M$ s with input $x$ then $y$ but I don't know how I could embed that into my function.

Can someone clear this up for me and give me a hint or confirmation if my ansatz was correct ?

Answer 1

The outcome of the reduction does not have to start with $w\#$ -- you can construct a different Turing machine to give to your Halting oracle (based on all of $w,x, y$). Or, for that matter, you don't need to construct that machine each time; you can just choose a fixed Turing machine $m$ and reduce each $w\#x\#y$ to $m\#(w\#x\#y)$.

Can you find an $m$ such that $m$ halts on $(w\#x\#y)$ if and only if $w$ halts on $x$ or $w$ halts on $y$?

(You will need either dovetailing, or trying to run $w$ on $x$ and $y$ with longer and longer limits for how many steps to perform).

Answer 2

Your intuition is almost correct, a Turing machine $M$ could accept $1$ and runs infinitely on $0$, so we can not run it on $0$ and wait for an answer and if the answer is negative then run it on $1$.

The mental leap you have to make here is that reduction works in the following way.

Given a Turing machine $H_{any}$, assume it halts on every input and show that using that Turing machine you can build a new one $H_{halt}$ that solves that halting problem.

This is done like this, if we have a $(\langle M \rangle, x)$ and we want to know if $M$ halts on $x$, we will simply send to $H_{any}$ the following input: $M\#x\#x$.

We assumed that $H_{any}$ exists and stops on any input and therefore it will always stop (giving us an answer, positive or negative). Hence, we now know if $M$ stops on $x$ which means we solved the halting problem..

But wait? you probably proved the halting problem is undetermined, therefore you know that your assumption is not right and $H_{any}$ doesn't stop on any input.

Now given what we discussed, you can do the reverse reduction by building a Turing machine that runs concurrently on the two inputs and returns if and only if one of them return.