0
$\begingroup$

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.

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

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<n$ 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.

$\endgroup$
2
  • $\begingroup$ @ Urtur. Thanks. I do not understand why the input length is sufficient for deciding if a string belongs or not to the language A1. Let's take the example 3142 which is not in A1 and yet it is 4 digits long just like 3141 which is in A1. So, how will the Turing machine decide if an input string is or not in A1 based on the input length ? I also do not understand why do we need to compute digits of π by some algorithm, i.e. shouldn't we assume that π is provided ? $\endgroup$
    – user249018
    Jun 29 '21 at 21:33
  • 1
    $\begingroup$ @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. $\endgroup$
    – Urtur
    Jun 29 '21 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.