## 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?

## Unrestricted grammar which generates $\{ a^1\#a^2\#a^3\#\dots \#a^k \mid k >0 \}$

I am looking for an unrestricted grammar which generates the following language:

$$\{ a^1\#a^2\#a^3\# \dots \#a^k \mid k >0 \}$$

That is, words like $$a\#aa\#aaa\#aaaa\# \dots \# \text{ k times ‘ a ‘}$$.

## Two integers $a$ and $b$ are coprime, is it possible that $a \mid b$?

Let $$a$$ and $$b$$ be coprime integers. Is it possible that $$a \mid b$$?

My thinking is that if $$a \mid b$$ then $$a$$ and $$b$$ share a factor besides $$\pm 1$$ ($$a$$ itself) and so are not coprime. Thus, $$a \nmid b$$.

This is probably very simple, but I’m still unsure.

## Find the CFG of $\{a^ib^jc^k \mid i,j,k>=0 , \text{if} \quad j=1 \quad \text{then} \quad i=k\}$

`I’ve tried but I can’t figure out any solution. Is there any hint for me to solve the question?

## Proving non-regularity of $\{a^p \mid p \in \text{Prime} \}$ without pumping lemma

I was wondering whether it is possible to prove $$\{a^p \mid p \in \text{Prime} \}$$ is a non-regular language without using the pumping lemma. I’m having trouble choosing an alphabet that completes the proof using Myhill-Nerode and figuring out other methods to use generally.

## Simple way to prove $\left \{ 0^{n}1^{m} \mid (n-m) \bmod 5=0 \right \}$ is regular?

Prove: $$\left \{ 0^{n}1^{m} \mid (n-m) \bmod 5=0 \right \}$$ is regular.

Is it reasonable to get a DFA with at least 30 states for this language? is there an easier way to prove it is regular?

## 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.

## Verifying equality $(a \times b)^2 = \mid a \times b \mid ^2$

I’m trying to verify the equality $$(a \times b)^2 = \mid a \times b \mid ^2$$ in Mathematica. How can I do it?

## 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 🙂