## Is $\{w~|~\forall x \in T(M_v):|w|>|x|~\}$ decidable?

I want to ask if $$\{w|\forall x\in T(M_v):|w|>|x|\}$$ is decidable if v is a Index of a random but fixed Turing Machine with $$|T(M_v)|<\infty$$.

My idea: It is co-semi-decidable since as soon as i find an $$x\in T(M_v)$$ with $$|x|\geq |w|$$ I have shown that this sepcific w is not in the set. I think it aint semi-decidable, since there can always be an $$x\in T(M_v)$$ which is longer than w. Therefor i also think the problem ist undecidable.

Do i oversee something ?

## Union of every language within group of decidable languages is also decidable?

So I was trying to solve following exercise:

Let $$(L_{i})_{i \in \mathbb{N}}$$ be a family of decidable languages – this means that every $$L_{i}$$ is decidable. Then $$\cup_{i \in \mathbb{N}}L_{i}$$ is also decidable. Right or wrong?

The solution states, that this statement is wrong because we can set $$L_{i}:=\{f(i)\}$$ with $$f : \mathbb{N} \rightarrow H_{0}$$ and will therefore receive $$\cup_{i \in \mathbb{N}}L_{i} = H_{0}$$. At the same time $$L_{i}$$ languages are still decidable, for every $$i \in \mathbb{N}$$ because they are finite.

However I still struggle to understand how exactly a language can be decidable with $$f : \mathbb{N} \rightarrow H_{0}$$, because I thought that $$H_{0}$$ was not decidable.

## Is the problem that determines whenever the word member $\in$ L(M) decidable or not?

Given a Turing machine M on alphabet {m,e,b,r} we’re asked to determine if member $$\in$$ L(M). You must realize that M is not one specific machine and can be any turing Machine with the same alphabet. My goal is to determine whenever this problem is decidable or not.

My idea was to use mapping reducibility. The goal was to see if we can translate all problems from $$A_{TM}$$ which is known to be undecidable into our current problem. This would make our current problem undecidable by contagion. However I’m struggling in doing so because I’m not sure if it’s possible. $$A_{TM}$$ is defined as a Turing machine M that accepts the word w.

Any help to get unstuck would be appreciated.

## Is the language Sol decidable or not?

I define the language Sol as a turing machine M with alphabet{s,o,l} and we want to decide if sol $$\in$$ L(M).

Is this decidable? How can I prove it? It seems that three case could occur either sol $$\in L(M)$$ or sol $$\notin$$ L(M) or the Turing machine M would loop. Is trying to use mapping reducibility with the language $$A_{TM}$$ defined as a Tm M that accepts w a good idea? If possible this would prove that Sol is undecidable because $$A_{TM}$$ undecidable.

## Is L = {: M accepts a word whose length is at most 200} decidable?

I have a language consisting of all Turing machines that only accept words "σ" with |σ| ≤ 200 and I need to determine if it is decidable, but it doesn’t look like any problem I have solved before. Any ideas?

## Is checking if regular languages are equivalent decidable?

Is this problem algorithmically decidable?

L1 and L2 are both regular languages with alphabet $$\Sigma$$. Does L1 = L2?

I think that it is decidable because you can write regular expressions for each language and see if they are the same. But I’m not sure how to prove it since I see that you prove something is decidable by showing a Turing Machine

## Why is the Halting problem decidable for Goto languages limited on the highest value of constants and variables?

This is taken from an old exam of my university that I am using to prepare myself for the coming exam:

Given is a language $$\text{Goto}_{17}^c \subseteq \text{Goto}$$. This language contains exactly those $$\text{Goto}$$ programs in which no constant is ever above $$17$$ nor any variable ever above $$c$$.

$$Goto$$ here describes the set of all programs written in the $$Goto$$ language made up of the following elements:

With variables $$v_i \in \mathbb{N}$$ and constants $$c \in \mathbb{N}$$
Assignment: $$x_i := c, x_i := x_i \pm c$$
Conditional Jump: if(Comparison) goto $$L_i$$
Haltcommand: halt

I am currently struggling with the formalization of a proof, but this is what I have come to so far, phrased very casually: For any given program in this set we know that it is finite. A finite program contains a finite amount of variables and a finite amount of states, or lines to be in. As such, there is a finite amount of configurations in which this process can be. If we let this program run, we can keep a list of all configurations we have seen. That is, the combination of all used variable-values and the state of the program. If we let the program run, there must be one of two things that happens eventually: The program halts. In this case, we return YES and have decided that it halts. The program reaches a configuration that has been recorded before. As the language is deterministic, this means that we must have gone a full loop which will exactly repeat now.

No other case can exist as that would mean that we keep running forever on finite code without repeating a configuration. This means after every step, among our list of infinite steps, there is a new configuration. This would mean that there are infinite configurations, which is a contradiction.

Is this correct? Furthermore, how would a more formal proof look if it is? If not, how would a correct proof look?

## CFG that generates $1^*$ is decidable

I read somewhere that the problem which asks whether or not a $$CFG$$ $$G$$ generates $$1^*$$ is decidable. The proof goes like this:

$$1^* \cap G$$ is context free since it is the intersection of a regular language and a $$CFG$$, therefore we can test if $$1^* \cap G$$ is empty since it is decidable to check if a $$CFG$$ is empty. If $$1^* \cap G$$ is empty, reject, otherwise, accept

I have doubts however with this proof since it only shows that some string in $$1^*$$ is generated by $$G$$, but not whether $$G$$ generates all strings in $$1^*$$.

Moreover, if this proof is correct, we can use the same proof outline under the alphabet $$\Sigma=\{0,1\}$$ to show that $$G$$ generates $$\Sigma^*$$, or that $$\Sigma^* \subseteq G$$. However, it is known that it is undecidable whether $$R \subseteq G$$, where $$R$$ is a regular language, and $$G$$ is a $$CFG$$ (by setting $$R=\Sigma^*$$, and $$\Sigma=\{0,1\}$$.

But to show that a $$CFG$$ generates $$1^*$$ is decidable, the only way I can think of is to use something similar to the proof that it is decidable for a $$PCP$$ instance to generate some string in $$1^*$$ (i.e., $$w=v$$, where $$w,v \in 1^*$$), i.e. we can check if the $$CFG$$ has rule $$S \rightarrow S1$$, then accept. O.w. if it has rules of the form $$S \rightarrow 1^aS1^b$$ such that $$a > b$$, and rules of the form $$S \rightarrow 1^cS1^d$$ such that $$c < d$$, then accept… But is there a simpler way to solve this problem ?

## Every decidable lanugage $L$ has an infinite decidable subset $S \subset L$ such that $L \setminus S$ is infinite

Given an infinite decidable language $$L$$, then if $$S \subset L$$ such that $$L \setminus S$$ is finite, then $$S$$ must be decidable. This is true since given a decider of $$L$$ we contruct a decider for $$S$$:

Simulate the decider of $$L$$ on the input, if it accepts, go over $$L \setminus S$$ and check if it is there, if it is, reject. If it isn’t accept. If the decider of $$L$$ rejects – reject.

Another point is if $$S \subset L$$ is finite then $$S$$ also must be decidable, this is immediate that every finite language is decidable.

Now we have the last case where $$S$$ is infinite and $$L \setminus S$$ is infinite. We know that there must be some subsets $$S$$ corresponding to this case that are undecidable. This is since there are $$\aleph$$ such $$S$$ but only $$\aleph_0$$ deciders. Denote $$D(L) = \{ S \subset L : |S|= |L \setminus S|=\infty \wedge S \text{ is decidable} \}$$

Is it true that for all infinite decidable languages $$L$$ we have $$D(L) \neq \phi$$?

If this is true then as a conclusion we will have for all infinite decidable languages $$L$$ a sequence of decidable languages $$L_n$$ such that $$L_0=L$$ and $$L_{n+1} \subset L_n$$ and $$|L_n \setminus L_{n+1}| = \infty$$

We will also have a limit-set $$L_\infty = \{ e \in L : \forall n \in \mathbb{N} \text{ } e \in L_n \}$$ and can dicuss if it is empty/finite/infinite and decicable or not.

This seems like a nice way to study decidable languages, and curious to know if this direction is indeed interesting and whether there are articles published regarding these questions

Thanks for any help

## Is the emptiness of intersection of two CFLs decidable?

Consider $$L = \{\langle L_1, L_2\rangle\mid L_1, L_2 \in \text{CFL} \text{ and } L_1 \cap L_2 = \emptyset \}$$. How to prove that $$L \notin R$$?

$$L_1, L_2$$ encoded in chomsky-normal-form.