1
$\begingroup$

I've been wondering about this problem for a while:

Say we have L = { <M>, n | M has to halt for at least n Inputs} and multitapes are simulating various inputs bla bla

How do I count how many Simulations came to a halt?

My guess was to have another tape that has e.g. n zeros as Input and whenever a Simulation comes to a halt the counting tape pointer is incremented by 1 until it reaches blanks.

Is that even possible?? I hope I got the point across... I didnt really know how to put my thoughts into words so if you have trouble understanding just hmu :)

have a good day (^^)/

$\endgroup$
1
  • 1
    $\begingroup$ I think this problem is undecidable, even with $n = 1$ (see the last equivalent formulation of the halting problem). $\endgroup$
    – Nathaniel
    Nov 16, 2021 at 20:52

1 Answer 1

1
$\begingroup$

Yes, you can simulate several TMs on separate tapes and mark a separate tape with a 1 whenever one of your simulations halts. For TMs that are well behaved (like deciders), this approach will work and your approach will answer Yes correctly.

The immediate problem is that some TMs don't behave nicely—they will run forever without halting. No matter how many separate tapes you have, or how cleverly you divide up the simulation work, you will eventually encounter a TM that loops forever and uses up all of your tape resources. This means that your machine will not be able to say "No" because it is stuck waiting to find out.

The deeper problem is that the question "Does machine $M$ halt on at least $n$ different inputs?" is undecidable. If you had a subroutine that could decide it, you could solve the halting problem. (Proof below.) It's not just that your counting approach is flawed—no algorithm exists that decides this problem.


Proof that the problem is undecidable: Suppose you had a machine $f(M,n)$ which decides whether $M$ halts on at least $n$ different inputs. Here's an algorithm for solving the halting problem:

Given a machine $M$ and a word $w$, design a new machine $M^\prime$. The machine $M^\prime$ is a modified version of $M$. If you give $M^\prime$ the input $w$, it simulates $M(w)$ as usual and halts if $M$ halts. On any other input, $M^\prime$ loops forever.

You can now solve the halting problem by computing $f(M^\prime, 1)$, which will return YES if $M$ halts on input $w$, or NO if $M$ doesn't halt on input $w$. This is a contradiction, so the algorithm $f$ can't exist.

$\endgroup$

Your Answer

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

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