1
$\begingroup$

Say you generated a language by looking at the output of a lexicographic enumerator and flipping a coin for each string, adding it to the language on heads. What would be the chance of this language being Turing-recognizable?

$\endgroup$
3
$\begingroup$

Yes, in fact one can show that there are uncountably many languages (say by representing a language as a sequence of the form $\{0, 1\}^\mathbb N$ which can be interpreted as the binary form of some real number in $[0, 1]$) while there are only countably many TMs (as any TM can be represented by a finite string), so almost all languages are undecidable, i.e. assuming we draw a language from an uniform distribution the probability of it being decidable would be 0.

$\endgroup$
2
  • $\begingroup$ I presume the chance of it being recognizable would also be 0 then? $\endgroup$ – burningbagel Oct 26 '20 at 17:44
  • $\begingroup$ Yes, this follows as well as every TM recognizes one language. $\endgroup$ – Watercrystal Oct 26 '20 at 18:02

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.