0
$\begingroup$

I know that set of all deciders is countable. I am wondering whether it is infinite.In other words can we prove that the set of recursive languages is infinite ?

Edit : The above question has small mistake as pointed out in one of the comments .. Since every recursive language has infinitely many deciders .. the two questions are indeed not equivalent . For people who are wondering why there are infintely many deciders , take a decider D and keep on adding some useless states, transitions, tape symbols so that you get new decider with a larger description than D and since you can continue this process indefinitely , there exists infinitely many deciders for a recursive language.

$\endgroup$
  • 3
    $\begingroup$ All finite languages are recursive. Is the number of finite languages finite or infinite? $\endgroup$ – gnasher729 Sep 14 '16 at 8:06
  • $\begingroup$ It is infinite .. since it contains an infinite subset , it must be infinite .. thanks for the idea $\endgroup$ – MysticForce Sep 14 '16 at 8:08
  • 2
    $\begingroup$ "In other words" -- since every decidable language has infinitely many deciders, the two questions are indeed not equivalent per se. $\endgroup$ – Raphael Sep 14 '16 at 8:29
  • $\begingroup$ @gnasher729 Post as an answer? $\endgroup$ – Raphael Sep 14 '16 at 16:18
2
$\begingroup$

What we want to prove is that there are infinitely many recursive languages. Consider the languages ( over $\{0,1\}$ ) $L_i=\{w\;|\text{ if } w \text{ has } i \text{ ones } \}$. Now each of the languages $L_i$ for $i \ge 0$ is decidable. And the set containing languages $L_i$'s is infinite ( though countable ). As the set of recursive languages contains all $L_i$, it is also infinite.

$\endgroup$
2
$\begingroup$
  • The language {0}.
  • The language {00}.
  • The language {000}.
  • The language {0000}.
  • The language {00000}.
  • The language {000000}.
  • The language {0000000}.
  • The language {00000000}.
  • The language {000000000}.
  • The language {0000000000}.
  • The language {00000000000}.
  • The language {000000000000}.
  • The language {0000000000000}.
  • The language {00000000000000}.
  • The language {000000000000000}.
  • The language {0000000000000000}.
  • The language {00000000000000000}.
  • The language {000000000000000000}.
  • The language {0000000000000000000}.
  • The language {00000000000000000000}.
  • The language {000000000000000000000}.
  • The language {0000000000000000000000}.
  • The language {00000000000000000000000}.
  • The language {000000000000000000000000}.
  • The language {0000000000000000000000000}.
  • The language {00000000000000000000000000}.
  • The language {000000000000000000000000000}.
  • The language {0000000000000000000000000000}.
  • The language {00000000000000000000000000000}.
  • The language {000000000000000000000000000000}.
  • The language {0000000000000000000000000000000}.
  • The language {00000000000000000000000000000000}.
  • The language {000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • The language {0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}.
  • Which leads to the idea that we should consider the infinitely many languages of the form $\{0^n\}$ where $n \in \mathbb{N}$.
$\endgroup$
  • 1
    $\begingroup$ Maybe I lack the specific blend of humor at work here, but the use of the length of this answer evades me. It would be funny if it would actually provide the required proof, but it doesn't, really. $\endgroup$ – Raphael Sep 14 '16 at 16:18
  • $\begingroup$ Good idea. I provided a (hint of a) proof (after some experimentation). $\endgroup$ – Andrej Bauer Sep 14 '16 at 16:45
  • $\begingroup$ Okay, now it's only a gigantic waste of space. ;) Mobile-users will hate you. $\endgroup$ – Raphael Sep 14 '16 at 17:52
  • $\begingroup$ Indeed ! I am one of them .. $\endgroup$ – MysticForce Sep 14 '16 at 18:10
  • $\begingroup$ There is an image on this page whose size is 34 kB, whereas my answer is measly 30 kB. The mobile users will hate me only because they'll have to scroll down, but on that front they're equal to the static users. $\endgroup$ – Andrej Bauer Sep 14 '16 at 19:05

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.