“problematic” non-halting inputs for Turing machines

Question

Let us start this question out, by defining for a Turing machine, the set of words it doesn't halt on. Define: $P(M)=\{w\in\Sigma^*|M$ doesn't halt on $w \}$

We know that the $HALT$ problem is $RE\setminus R$ - thus every TM $M$ that computes $HALT$ has a word it doesn't halt on, i.e $P(M)\ne\emptyset$.

From this, arises the (simple) question:

$Q(1):$ "is a problem undecidable if and only if every TM that computes it has a non empty 'problematic' set $P(M)$?" $ ^{Q\space(1)}$

Moreover, let's note that for the $HALT$ problem we know that given $M$ that computes it, there are infinitely many inputs it will never halt on (I encourage to think why this is so, before proceeding in the post)

So, similarly we might want to ask ourselves the (slightly) harder version of the first question.

$Q(2):$ "is a problem undecidable iff every TM $M$ that computes it has $|P(M)|=\aleph_0$?" $ ^{Q\space(2)}$

Moreover - let's ask an even stronger question:

$Q(3):$ "if $L$ is undecidable, will we still be able to find a finite set of Turing machines $M_1,...,M_n$ that compute $L$ and have $\bigcap_{k\space=\space0}^nP(M_k)$ finite? what about an infinite set of Turing machines that satisfy that?" $ ^{Q\space(3)}$

And our final (and half-open) question will be:

$Q(4):$ "What else can we understand about Turing machines and their problematic sets?"

Answer 1

So, let's start tackling those problems. As a side note, I have arranged the questions such that each question uses the answer of the one before it (and this way, they almost seem too trivial to begin with $:$P).

$A(1):$ is pretty trivial from definition. If $L$ is undecidable then there is no Turing machine that computes it and always halts, thus all Turing machines that compute $L$ have $P(M)\ne\emptyset$. The other direction is also as simple as this one.

$A(2):$ let's assume $L$ is undecidable. If there was a Turing machine $M$ that computes $L$ and has a finite $P(M)$, then let us build a new machine $\hat M$ such that it will have $P(\hat M)=\emptyset$ as following (on input $w$):

• reject if $w \in P(M)$ (this is possible since $P(M)$ is finite)
• otherwise, return $M(w)$

this new machine, will halt for every $w\in P(M)$, but since for every $w\notin P(M)$ it will run $M$, and it's guaranteed that it will halt on it (since otherwise it would have been in $P(M)$), we have that the new $\hat M$ always halts, and accepts $L$ - thus contradicting the assumption. The other direction is simply derived from $A(1)$.

$A(3)$: for finite sets of Turing machines, $M_1,...M_n$ we will show that its impossible to have finite $\bigcap_{k\space=\space0}^nP(M_k)$ but undecidable $L$. lets assume towards contradiction this doesn't hold. Just at $A(2)$, we will build $\hat M$ - but now its enough to build it such that $P(\hat M)=\bigcap_{k\space=\space0}^nP(M_k):$

• Run $M_1(w), M_2(w), ...,M_n(w)$ in parallel
• Accept if any one of them accepted.

Now, it's obvious why $\hat M$ accepts $L$. Let $w\notin P(\hat M)$, then there is some $1\le k\le n$ such that $M_k(w)$ halted, thus $w\notin\bigcap_{k\space=\space0}^nP(M_k)$. let $w\in P(\hat M)$, then it didn't halt on any $M_k$, thus $w\in P(M_k)$ for all $k$. Concluding that $P(\hat M)=\bigcap_{k\space=\space0}^nP(M_k)$ is finite and therefore from $A(2)$ cannot exist.

Regarding infinite sets of Turing machines, this is definitely possible. Just define for each $w\in \Sigma^*$ the machine $M_w$ that accepts $L$ but also halts on $w$ (similarly to the build in $A(2)$). then $w\notin P(M_w)$ therefore $w\notin \bigcap_{\hat w} P(M_\hat w)$ and thus not only that $\bigcap_{\hat w} P(M_\hat w)$ is finite, its also empty.

$A(4):$ let $L$ is undecidable and $M_1,M_2...$ are Turing machines who accept $L$ and their intersection of the "problematic set" is finite. If we look at the function $f:\mathbb{N}\rightarrow\Sigma^*$ defined by $f(k)=\langle M_k\rangle$ , then it is not computable. This follows from $A(2)$ since if that function was computable, we would have been able to create a Turing machine $\hat M$ with $P(\hat M)=\bigcap_k P(M_k)$

Another idea i have started to think about is what happens when we talk about two languages or more, instead of one at a time. Let $M_1$ be a machine for $L_1$ and $M_2$ for $L_2$. then, we can define a machine $M$ for $L_1\bigcap L_2$ or $L_1\bigcup L_2$ with:

$P(M) = P(M_1)\bigcup P(M_2)$ (note this also can prove closure properties in $\mathcal R$)

or if $L_1\Delta L_2$ is finite, then we the problematic sets of machines for the languages are pretty much the same(for every machine $M$ in any one of them we can find machines $M'_1,M'_2$ for the other two languages with the same problematic set)

Although I have yet to write a formal proof of the above. (honestly, I don't have energy to write more proofs like that in this one big post) I still encourage you to try proving that at home!

Finally! I think (but still unsure) we can get similar results (but with more constraints) for time complexity analysis if we define $P(M, t)$ for time-constructible $t(n)\ge log(n)$ as the group of words $M$ doesn't halt on within $t(n)$ steps. In this definition there is the tricky problem of constants, so its harder to show theorems by defining new machines (as they might do just a little bit more constant work that will make some word enter the problematic set, and big-O notation here is somewhat meaningless for different constants)

If you think that something is incorrect, or just want to add more - I will be glad to make changes.