Computing $E(X \mid \sigma(min\{x, k\}))$

Consider $ \Omega = (0,\infty)$ , $ \mathcal F = B(\Omega)$ , and $ \lambda > 0$ . Let $ P$ be the probability measure on $ (\Omega, \mathcal F)$ satisfying $ P((a,b]) = e^{-\lambda a} – e^{-\lambda b}$ . Also set $ X(\omega) = \omega$ and $ Y(\omega) = \min \{ \omega, \kappa \}$ for $ \kappa > 0$ . Compute

  • $ E(X \mid \sigma (Y))$
  • $ E(e^{-\alpha X} \mid \sigma (Y)), \quad \alpha >0 $

I have no idea how to start here. I realise that the function $ Y(\omega)$ is a piecewise linear function on $ (0,\kappa)$ and $ [\kappa, \infty)$ . Hence the $ \sigma$ -algebra $ \sigma (Y)$ is given by the collection of sets

$ \varnothing, \Omega$ , $ \{ B : B \subseteq (0,\kappa)\}$ , $ \{B : B \subseteq [\kappa, \infty)\}$ ,

but apart from that I have no clue… Any one that can provide me with a hint?

Why is \{w \in \{0, 1\}^\ast \mid \exists x \in \{0, 1\}^\ast\colon M_w(x) \neq x\} not computable?

The language

$ $ L_1 = \{w \in \{0, 1\}^\ast \mid \exists x \in \{0, 1\}^\ast\colon M_w(x) = x\} $ $

($ w$ is an encoding of a DTM, $ M_w$ is the respective DTM.)

is not decidable, according to Rice’s theorem. However, it is recursively enumerable: an NTM simply chooses an $ x$ for which the condition is fulfilled non-deterministically.

Consider the very similar language

$ $ L_2 = \{w \in \{0, 1\}^\ast \mid \exists x \in \{0, 1\}^\ast\colon M_w(x) \neq x\} $ $

Rice’s theorem argues that this is undecidable, but neither is it semi-decidable according to my sources.

Why can’t we argue for $ L_2$ as we did for $ L_1$ , stating that an NTM chooses the input $ x$ non-deterministically, the condition is fulfilled, $ L_2 \in \mathsf{RE}$ ?

The proof that $ L_2 \not\in \mathsf{RE}$ performs the reduction $ \overline H \leq L_2$ , where $ H$ is the halting problem. I understand this proof by reduction, but to me, it seems contradictory to the argument for recursive enumerability I give above.

Space and time complexity of $L = \{a^nb^{n^2} \mid n≥1\}$

Consider the following language: $ $ L = \{a^nb^{n^2} \mid n≥1\}\,$ $

When it comes to determining time and space complexity of a multi-tape TM, we can use two memory tapes, the first one to count $ n$ , and the second one to repeat $ n$ times the count of $ n$ . Thus, because of the way we’re using the second tape, it should have a $ \Theta(n^2)$ space complexity, and I would say the same concerning the time one. I thought it was correct, but the solution is $ TM(x)=|x|+n+2$ , where, $ x$ is, supposedly, the length of the string, hence $ \Theta(|x|)$ . It seems correct to me, so is my reasoning completely wrong, or just a different way to express it?

Could we have reasoned about it differently, and say, for example, for every $ a$ we write down a symbol on the first tape, and then count the $ b$ ‘s, by scanning the symbols back and forth $ n$ times? This time, the space complexity should just be $ \Theta(n)$ , while the time complexity should remain unchanged. What would change if we had a single-tape TM?

About a “modification” of the diagonal language $\{w_i \mid \text{Every turing machine } M_1 \ldots M_i \text{ reject } w_i\}$

I have given the seeming modification of the diagonal language $ \{w_i \mid \text{Every turing machine } M_1 \ldots M_i \text{ rejects } w_i\}$ , yet I can’t prove that it is undecidable.

My thoughts so far:

  • This language is intuitively undecidable, but it might trick you into thinking that it is, and it is in fact decidable: At last there exists an $ i$ from which $ M_i = M^*$ where $ M^*$ rejects every word $ w$

  • I can’t directly reduce this to the diagonal language

  • I can’t build a halting problem solving machine on this if I can’t define my enumeration of $ w_i$ and $ M_i$ freely, which I can’t (and is that even right?).

A nice tip would be helpful. Thanks 🙂