Is cardinality of the set of real number between 0 and 1 that doesn’t have some specific digit string in some specific base decidable

algorithmscomputational mathematicsdecidabilityset-theorysoft-question

Originally, I get this idea when I try to create intermediate cardinality set between the integers and the real numbers to disprove the continuum hypothesis when I read the normal number definition.
However, once I found it that continuum hypothesis is unproveable, at first, I am about to abandon it but then I come up with another question about it instead.

I call it simply "the no specific digit string number".

For here, I will use (10) as 10th digit symbol instead of A, (11) as 10th digit symbol instead of B, and so on.
That mean (11)1 is string of 1 "(11) digit" and 1 "1 digit" (or B1 in normal base number writing).

"the no specific digit string number" is any set of number that

  • That is real number between 0 and 1 (but not equal to 0 and 1)
  • When write those number in B(n) base when $B(n) ∈ B \text{ & } B ⊆ I^{+}$, it doesn't contain any digit string that is member of set A(n) when $A(n) ∈ A$
    • A(n) and B(n) refer to $n^{th}$ memeber of set A and B.
    • A is the set that contain many smaller set A(n).
    • The cardinality of the set A and B must be same.
    • A and B can be infinite but must be countable set.
    • All digit string that is member of set A(n) must be possible to be appear B(n) base.
      • Note : It doesn't make any different for such a set of number that doesn't contain string 34 when write in base 2 because base 2 never contain string 34.
    • The digit string that is member of set A(n) can be infinite string as long as it can appaear in B(n) base for example digit string of $\pi$ in base 2 when B(n) = 5.
    • A(n) and B(n) must be computable. There must be exist computable algorithm function to generate each digit string that is member of set A(n) and the number in B(n).
      • Note : If they are uncomputable, they will make the "the no specific digit string number" obviously undecidable.

Note that the 0 before the "." doesn't count. For example, "0.1" doesn't have 0 digit string here because it can be write as ".1"

The definition of set A(n) is pretty complicate. I am sorry if I might miss something about A(n). I will fix it as much as I can.

For example,

  • B = {10,17,31} & A = {{5},{4,56},{7,(11),23(14)}} mean the set of any real number between 0 and 1 that
    • Doesn't contain string 5 when write in base 10
    • Doesn't contain string 4 and 56 when write in base 17
    • Doesn't contain string 7,(11) and 23(14) when write in base 31
  • B = {$x^{2}|x∈I^{+},x>1$} & A = {the set of string "a" that write in base 10 and $\lfloor \frac{B(n)}{2} \rfloor < a < B(n)$} mean the set of any real number between 0 and 1 that
    • Doesn't contain string 3 when write in base 4
    • Doesn't contain string 5,6,7,8 when write in base 9
    • Doesn't contain string 9,10,11,12,13,14,15 when write in base 16
    • …
    • Doesn't contain digit $\lfloor \frac{B(n)}{2} \rfloor$,$\lfloor \frac{B(n)}{2} \rfloor$+1,…,$n^2-2$,$n^2-1$ when write in base $n^2$
  • B = {prime number that is larget than 4} & A = {the set of string "a" that write in base 2 and $a = n$} mean the set of any real number between 0 and 1 that
    • Doesn't contain string 1 when write in base 5
    • Doesn't contain string 10 when write in base 7
    • Doesn't contain string 11 when write in base 11
    • Doesn't contain string 100 when write in base 13
    • Doesn't contain string 101 when write in base 17
    • …
    • Doesn't contain string of n when write in base 2 when write in base the prime number $p_{n+2}$

With some specific set A and B, I can create empty set, finite set, infinite countable set or uncountable set. For example,

  • B = {3} & A = {{0,1,2}} : I will get empty set because there is no number that doesn't contain string 0,1,2 when write in base 3
  • B = {3} & A = {{0,1,2222}} : I will get finite set that is {0.2,0.22,0.222}
  • B = {3} & A = {{0,1}} : I will get infinite countable set that is {0.2,0.22,0.222,0.2222,…}
  • B = {3} & A = {{0}} : I will get uncountable countable set that is {0.1,0.12,0.21,0.121,…,0.12112111211112…,…}

Back to the original question, is cardinality of my "the no specific digit string number" decidable ?
Is it possible to construct an algorithm that always tell whether "the no specific digit string number" is empty set, finite set, infinite countable set or uncountable set when giving any A(n) and B(n) that follow th rule above ?

I know that my "the no specific digit string number" is very broad and can create many varity of set. But for I think it can divide into these case

  • (1.) A and B is finite. All A(n) is finite.
  • (2.) A and B is finite. Some A(n) is infinite.
  • (3.) A and B is finite. All A(n) is infinite.
  • (4.) A and B is infinite. All A(n) is finite.
  • (5.) A and B is infinite. Some A(n) is infinite.
  • (6.) A and B is infinite. All A(n) is infinite.

I think (1.) is decidable and (6.) is undecidable but I am not sure for other case.

Best Answer

It's undecidable even in (1). For Turing machine $M$, let $B = \{2\}$, and $A_M = \{\{00, 11, x_M\}\}$ where $x_M[k]$ is $0$ if $M$ stops in at most $k$ steps, and $k \pmod 2$ otherwise - so $x_M$ is $010101\ldots$ if $M$ never stops, and $0101\ldots 0000\ldots$ otherwise.

Forbidding $00$ and $11$ means that we allow only numbers $010101\ldots$ and $101010\ldots$. If $M$ never stops, $x_M$ also forbids them, and we get an empty set. If $M$ does stop, we allow them and get two-element set. So, checking if we have empty set or finite set is the same as solving halting problem for $M$.

If you forbid infinite strings, then (1) is decidable, but the rest are still not.

Note that finite number of finite restrictions in base $b$ can be transformed to finite number of finite restrictions in base $b\cdot k$. So, if we have finite number of finite restrictions in finite number of bases, we can transform them to the same base. Now, we have finite number of finite restrictions in one base. We can transform this restrictions to minimal DFA, and string is in the set iff it doesn't reach forbidding state in the DFA. Now, from this DFA we can check:

  1. If there is no cycle (except from forbidding state), then set is empty.
  2. If there is a cycle, but no vertex in any cycle is reachable from vertex in a different cycle, then set is finite.
  3. If there is a cycle reachable from a different cycle, but no intersecting cycles, then set is countable infinite.
  4. If there are two intersecting cycles, the set has cardinality continuum.

The rest are undecidable. If you allow infinite number of restrictions for some base, let $B = \{2\}$ and $A_M = \{\{00, 11, x_M^1, x_M^2, \ldots\}\}$ where $x_M^i = 0^i$ if $M$ doesn't stop in exactly $i$ steps, and $x_M^i = 1$ if $M$ stops in exactly $i$ steps. If you allow infinite number of bases, let $B(n) = n + 1$, $A_M(n) = \varnothing$ if $M$ doesn't stop in exaclty $n$ steps, and $A_M(n) = \{0, 1, \ldots, (n-1)\}$ if it does.

Related Question