# A turing machine L takes a machine <M> which has to halt at for least n Inputs

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 (^^)/

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

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.