3
$\begingroup$

The following is a quote from Denis' answer in another thread where the context centers on creating a noncomputable real number. It's old and I'm new here so I can't comment on the answer itself, thus I'm asking the question here (note, you shouldn't have to read the other thread for this):

Are there any examples of non-computable real numbers?

"Any language can be turned into a number, by setting the $i^{th}$ decimal to 1 if the $i^{th}$ word is in the language, and to 0 otherwise. So we can build for instance the number $H$, which describes the halting problem and is therefore uncomputable."

I'm trying to grasp this example. I assume the language of course has an alphabet, like {a, b, c, ..., x, y, z}. We then have an enumeration of all combinations of letters (e.g., s1 = a, s2 = b, s3 = c, ... s27 = aa, s28 = ab, s29 = ac, ...). From there, we say each $s_i$ is either a word or it isn't, where then i = 1 or i = 0, respectively.

My question is, assuming the English language is used where the largest word will contain only a 'small' number of letters, wouldn't we just produce a number $H$ that has a trailing string of 0's? I assume $H$ must be in (0, 1) so as to not be an 'infinitely large' integer...

If $H$ is guaranteed to have a trailing string of 0's, then it will be a rational number, yes? And, aren't all rationals computable by definition?

Ok, so I'm clearly missing something because I assume the answer provided by Denis is correct. A clearer explanation is appreciated.

$\endgroup$
1
$\begingroup$

You're right that if the English language (or any other finite language) is used you get a computable number. Denis's example is not the English language, though: it's the language that encodes the halting problem. That is, this "language" consists of all words that are encodings of Turing machines that halt.

$\endgroup$
  • $\begingroup$ Ok, so he meant 'formal language' where a word represents a program that can be run by a Turing machine. That makes more sense. (slap face)... :) Thank you. $\endgroup$ – AplanisTophet Jun 14 '17 at 2:48

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.