# A definition of Conway base-$13$ function

Can you give a definition of the Conway base-$13$ function better than the one actually presented on wikipedia, which isn't clear? Maybe with some examples?

• – falagar Jul 29 '10 at 12:07
• Can you say what's unclear about the definition on Wikipedia, so that it can be fixed? – ShreevatsaR Jul 29 '10 at 13:48
• @ShreevatsaR: For a start, it could explain the use of the weird .-+ notation – Casebash Jul 29 '10 at 13:59
• @Casebash: It does: "expand x […] in base 13 using the symbols 0,1,2,3,4,5,6,7,8,9,.,-,+". It also says "Note: Here the symbols "+", "-" and "." are used as symbols of base 13 decimal expansion, and do not have the usual meaning". What else could you write? (I didn't write it and am not trying to defend it; I just think it would be nice if the Wikipedia article got improved as a result of this question, and am trying to understand how it can be improved.) – ShreevatsaR Jul 29 '10 at 14:06
• needless to say, we could also work from the other side. Just write the infinite decimal number, then declare a number well-formed if its decimal expansion eventually contains digits from 0 to 6, preceded by a 7, then a finite number (but at least one) of digits from 0 to 6, then either a 8 or a 9. Now the value of the anti-Conway function is 0 for non well-formed numbers; for well formed numbers, throw away the leftmost part, substitute + for 8, - for 9 and . for 7, and read the resulting number as if it were in base 7. – mau Aug 1 '10 at 20:14

I understand why the Wikipedia article uses the notation it does, but I find it annoying. Here is a transliteration, with some elaboration.

1. Expand x ∈ (0,1) in base 13, using digits {0, 1, ... , 9, d, m, p} --- using the convention d = 10, m = 11, p = 12. N.B. for rational numbers whose most reduced expression a/b is such that b is a power of 13, there are two such expansions: a terminating expansion, and a non-terminating one ending in repeated p digits. In such a case, use the terminating expansion.

2. Let S ⊂ (0,1) be the set of reals whose expansion involves finitely many p, m, and d digits, such that the final d digit occurs after the final p digit and the final m digit. (We may require that there be at least one digit 0--9 between the final p or m digit and the final d digit, but this does not seem to be necessary.) Then, every x ∈ S has a base 13 expansion of the form

0.x1x2 ... xn [ p or m ] a1a2 ... ak [ d ] b1b2 ...

for some digits xj ∈ {0, ... , p} and where the digits aj and bj are limited to {0, ... , 9} for all j. The square brackets above are only intended for emphasis; and in particular the n+1st base-13 digit of x is the final occurance of either p or m in the expansion of x.

3. For x ∈ S, we define f(x) by transliterating the string format above. We ignore the digits x1 through xn , transliterate the p or m as a plus-sign or minus-sign, and the d as a decimal point. This yields a decimal expansion for a real number, either

+a1a2 ... ak . b1b2 ...

or

a1a2 ... ak . b1b2 ...

according to whether the n+1st base-13 digit of x is a p or an m respectively. For x ∈ S, we set f(x) to this number; for x ∉ S, we set f(x) = 0.

Note: this function is not computable, as there is no way that you can determine in advance whether the base-13 expansion of x ∈ (0,1) has only finitely many occurances of any of the digits p, m, or d; even if you are provided with a number which is promised to have only finitely many, in general you cannot know when you have found the last one. However, if you are provided with a number x ∈ (0,1) for which you know the location of the final p, m, and d digits, you can compute f(x) very straightforwardly.

• "and a non-terminating one ending in repeated p digits" -- this is analogous to the fact that 1/100 can be represented in base 10 as 0.01, or as 0.0099999..., correct? – MatrixFrog Jul 31 '10 at 6:01
• Precisely. An analogous thing happens in any base, for any terminating fraction. – Niel de Beaudrap Jul 31 '10 at 7:46
• Thank you very much! I find the usual notation very annoying too. – Matemáticos Chibchas Dec 22 '13 at 19:10
• I don't understand you argument that the function is not computable. You seem to be arguing there is no algorithmic procedure turning an expansion of the input base-13 into an expansion of the output base-10. But if that's your definition of computable, not even multiplication by 3 base-10 to base-10 is computable. – Marcel Besixdouze Nov 25 '15 at 6:03
• @MarcelT. Multiplication by 3 (of decimal expansions) is computable, in that for any approximation to the input $x$ which is accurate to precision $\epsilon$ (e.g. if you truncate the decimal expansion), I can produce a value which is within $3\epsilon$ of $x \times 3$. Therefore, any output precision is achievable. However, you cannot do this with $f$: because unless you provide me a promise on the distibution of $p$ and $m$ digits in the input $x$, I cannot know that all of the $p$s and $m$s in the input have been given. So, there is no way for me even to approximate $f(x)$. – Niel de Beaudrap Nov 25 '15 at 13:44

You just need to switch back and forth from the lexicographic meaning of the base-13 expansion of the number (think of having ABC instead of .-+) and the loaded meaning you give to the well-formed string as a base-10 number.

An example of a number for which Conway base-13 function is 0 is

0.12-34++1+2-34..11111111111...

where the leftmost . is the threedecimal point (that is, it has a semantic meaning), the three rightmost . mean that the base-13 representation has an infinite number of 1 (that is, they have a metameaning), and the other two . are "digits" of the number (that is, they have a syntactic meaning).
An example of a number for which Conway base-13 function is not 0 is

0.12-34++1+2-34.11111111111...

At that number, the function has value -34.11111111111... (in base 10)

The idea of the Conway base-13 number is to find a function that is not continuous, yet if f(a)<x<f(b), then there is some c between a and b with f(c)=x. This a counterexample to the converse of the intermediate value theorem.

The function is defined by encoding base-10 values in the tail (the digits left after skipping a finite number). We use +, -, . and the digits to represent an encoded number in the tail and require the encoded number to start with a + or -. In base 10, every number ending in an infinite number of 9s can be rewritten to end in an infinite number of 0s instead (ie. 0.999...=1.0). Similarly, we decide we will rewrite each Conway number ending in an infinite number of +, to ensure that each real number has a unique decimal representation.

Each number can have up to one base-10 encoded value, which is the result of applying Conway's Base 13 function if it exists. If no such encoding exists for x(ie. + occurring infinite times in the expansion), then we define f(x)=0.

We then show that for each a and b that we can find a c in between with an arbitrary encoded value. We first ensure the number being constructed is between a and b by copying enough digits from a and incrementing a digit that won't matter. This is easier because we have disallowed ending in an infinite number of +. We then concatenate the digits of the signed base-10 representation of the value we wish the function to have to those digits we have already fixed.

• I thought that the number must not end with an infinite sequence of + just because we need a unique representation. Since the numbers which have two possible representations are a countable set, we could work with either representation; the one in 00000... is just a bit more convenient. – mau Jul 29 '10 at 14:50
• @Mau: Good point – Casebash Jul 29 '10 at 20:58