0
$\begingroup$

This is a problem that I think is a reduction from the halting problem. I have on two separate practice exams statements that,

Given a Turing machine T and a string w, to determine whether T will halt when started on input w.

and

Given a Turing machine T and a string w, to determine whether T will halt when started on a blank tape.

The answer key states that these problems are both partially decidable, which is astonishing to me given that they are reductions from the halting problem, which is undecidable.

If there was a Turing maching M, that would halt if it's input was another Turing machine T that also halted on an arbitrary string, would that not violate the halting problem? Why are the two above statements considered to be partially decidable?

$\endgroup$
4
$\begingroup$

The halting problem is not decidable, but it is still partially decidable (other terms for this are "recursively enumerable" and "Turing recognizable"). So, you are right that both of these problems are equivalent to the halting problem. That is why they are undecidable, but still partially decidable.

You may want to review the definition of "partially decidable" in your textbook or notes.

$\endgroup$
1
$\begingroup$

A problem $P$ is said to be partially decidable (or semidecidable, or recursively enumerable, or ... (too many other names for the same notion)) when there is a TM that can take any instance $x$ of the problem and:

  1. if $x\in P$, the TM eventually accepts
  2. if $x \not\in P$, the TM diverges

If we had rejection instead of divergence, we would have that $P$ is decided by such TM. However, the TM above does only "half" of the deciding: it recognizes all the $x$ to be accepted, but computes forever on those which should be rejected.

The halting problem falls into this case. It is easy to accept a halting TM: simulate it, and after it halts, accept. However, if this procedure is run on a diverging TM, the simulation diverges. So, this procedure is only semideciding the halting problem.

$\endgroup$
0
$\begingroup$

The above questions are semi-decidable because we can design a Turing Machine to "semi-decide" each of them. This means that the Turing Machine must only halt for strings that are in its language.

For the blank-tape halting problem, let's call our Turing Machine B. On input , where M is a Turing Machine, B simply simulates M on a blank tape. B halts and accepts if and only if M halts. We could design a similar Turing Machine to recognize the other language you gave.

$\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.