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.
