# Recursive languages

I need to prove if the following languages are recursive:

1. $$A_1 \subseteq \{0, . . . , 9\}^∗$$ consists of all finite sequences of $$\pi$$ without the decimal point.

We may thus write $$A_1 = \{3,31,314,3141, 31415, 314159,... \}.$$ The idea is to apply the Turing machine and prove if it can recognize a given string or word belongs to the language or not.

1. $$A_2 \subseteq \{0, . . . , 9\}^∗$$ consists of the decimal representation of all natural numbers $$n \in \mathbb{N}$$ such that in the decimal represenation of $$\pi$$ there is a sequence of at least $$n$$ fives, i.e. 555...5.

Since we assume that $$n$$ is finite, $$n \in \mathbb{N}$$, we exclude sequences of infinity length. Here again, we may want to use Turing machines for deciding if an input string belongs or not to the language.

Can somebody provide some hints or a solution proposal? Many thanks.

• Please ask only one question per post. If you have multiple questions, you can post them separately as separate questions.
– D.W.
Jun 29 '21 at 20:43
• Please state the question in the title. People want to understand the question without opening this page. Jul 1 '21 at 14:54

For (1) you can take the length of the input. There are many algorithms to compute digits of $$\pi$$. Use any of them to compute the same number of digits as the input and compare.
For (2) we observe that when some $$n\in A_2$$, then all $$k also are in $$A_2$$. Therefore, either all $$n\in A_2$$ or there is a maximum $$n=n_0$$ that belongs to $$A_2$$. Therefore, either the machine that immediately halts or the machine that halts if and only if $$n\leq n_0$$ decides $$A_2$$. It is however, very hard to tell which machine is the right one.
• @user249018 I didn't mean that the length alone decides $A_1$. Let me rephrase it, if I didn't say it clearly. We compute the decimal representation of $\pi$ up to the length of the input using one of the many formulas available. Then we compare the result of that computation to the input. The machine accepts if and only if those two are the same. Jun 29 '21 at 21:37