1
$\begingroup$

That's a question from a home assignment by T. Zur:

Say that a Turing machine $M$ is monotone if it halts on every input, and if the length of $w$ is greater than the length of $w'$ then $M$ performs more steps on $w$ than on $w'$.

Prove that MON is undecidable.

My idea is to define a reduction from HALT to MON. We define $f(\langle M,w \rangle) = \langle M' \rangle$ so that $M'$ will erase its input, write $w$, and simulate $M$ on it. If $M$ halts then $M'$ accepts.

I feel like I'm missing just a bit but I can't get my head around it.

$\endgroup$
1
  • 1
    $\begingroup$ A Turing machine which ignores its input cannot be monotone. $\endgroup$ May 1 at 8:18

1 Answer 1

3
$\begingroup$

Your answer is correct

What might seem missing is that $M'$ erases any input, writes $w$ and simulates $M$ on $w$, so it might seem that for any input (say $x$ which we erase), $M'$ takes the same number of steps (simulating $w$), but $M'$ needs to take more steps on larger inputs!

The thing is when you erase the input, the larger the input the more steps you need to take, and so that's not a problem, if the machine can simply ignore the input without making steps, then we simply modify $M'$ to first make some arbitrary steps, the number of these would be the length of the input, then it can proceed by writing $w$ and simulating $M$.

If $\langle M,w \rangle \in \mathrm{HALT}$, $\langle M' \rangle \in \mathrm{MON}$ since whatever the input, $M'$ is simulated only on $w$ and so it halts on every input, also for any inputs $x_1,x_2$, where $\vert x_1 \vert > \vert x_2 \vert $, $M'$ takes more steps on $x_1$ than $x_2$ since deleting $x_1$ takes more steps (or $M'$ simply made $\vert x_1 \vert$ arbitrary steps on $x_1$) then $M'$ simulates $w$ in both cases.

If $\langle M,w \rangle \notin \mathrm{HALT}$, $\langle M' \rangle \notin \mathrm{MON}$, since $M'$, whatever the input, is simulated only on $w'$ (hence it won't halt at any input).

$\endgroup$

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.