1
$\begingroup$

Crank disclaimer: I don't doubt the undecidability of the halting problem, but one proof confuses me.

We have seen this folklore proof of the halting problem on several occasions.

Assume a HALTING SOLVER ($HS$) exists with argument program $P$ and it returns true iff $P$ halts.

Let SMART PROGRAM ($SP$) do the following: call $HS$ with argument its source and do the opposite of the answer, i.e. if $HS(SP)=True$, $SP$ returns immediately, contradicting the correctness of the $HS$.

We believe this proof if false, because it doesn't need infinite tape of the turing machine and the halting problem with finite tape is decidable.

Attack on the folklore proof.

Apply the proof to a machine with finite tape, it implies the problem is undecidable, but it is known that the HP problem for finite tape is decidable and we have contradiction.

Q What is wrong with this contradiction?

In the real world, antivirus programs try to recognize computer viruses and some of the viruses try to circumvent being analyzed, e.g. if they are run in a debugger or a virtual machine they exit, not showing malicious behavior.

$\endgroup$
1
  • 1
    $\begingroup$ Why do you say that (the Turing machine implementing) $SP$ only uses a finite a mount of space? Note that $SP$ needs to simulate a Turing machine for $HS$. $\endgroup$
    – Steven
    Feb 8 at 13:53

1 Answer 1

2
$\begingroup$

Your confusion comes from not being careful enough with the quantifiers regarding the tape bound.

Let's keep track of memory requirements in the construction. Let's assume that $HS$ uses up to $M(s)$ many cells of the tape for inputs of size $s$, and moreover, let us assume that the code of $HS$ has size $h$. Then $SP$ uses about $M(h)$ cells (which doesn't depend on its input), and $HP$ gets it wrong.

This tells us the following: For every potential Halting decider $H$ there is a TM $M$ using constant memory $C$ (ie not depending on $M$'s input, but depending on $H$!) such that $H$ is wrong on input $M$.

On the other hand, decidability of the bounded Halting problem is the following: For every memory bound $C$ there is a potential Halting decider $H$ that gets all inputs correct which use no more than $C$ cells of the tape.

The first statement has the logical form $\forall H \ \exists C \ \neg \Psi(H,C)$, the second has the logical form $\forall C \ \exists H \ \Psi(H,C)$. There is no contradiction here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.