My Math Forum Non-computable Reals

 Number Theory Number Theory Math Forum

 June 12th, 2017, 05:03 PM #1 Senior Member   Joined: Jun 2014 From: USA Posts: 441 Thanks: 30 Non-computable Reals Question 1: Can a non-computable real $x$ be created using the following method? Let $s \in ( \,0,1) \,$ be a computable number that is irrational. A turing machine can therefore encode the binary expansion of $s$ to any desired number of bits: $$s = s_1s_2s_3s_4\dots\text{, where each } s_i \in \{0, 1\}$$ Let $t_1, t_2, t_3, \dots$ be a listing of binary strings $t_i$ created using each bit in $s$ as follows: $$\begin{matrix} t_1 \text{ }| & t_{1,1} = s_1 & \longrightarrow & t_{1,2} = s_2 & \text{ } & t_{1,3} = s_6 & \longrightarrow & \dots \\ \text{ } & \text{ } & \swarrow & \text{ } & \nearrow & \text{ } & \swarrow\\ t_2 \text{ }| & t_{2,1} = s_3 & \text{ } & t_{2,2} = s_5 & \text{ } & t_{2,3} = s_8 & \text{ } & \dots \\ \text{ } & \downarrow & \nearrow & \text{ } & \swarrow & \text{ } & \nearrow \\ t_3 \text{ }| & t_{3,1} = s_4 & \text{ } & t_{3,2} = s_9 & \text{ } & t_{3,3} = s_{13} & \text{ } & \dots \\ \text{ } & \text{ } & \swarrow & \text{ } & \nearrow & \text{ } & \swarrow \\ t_4 \text{ }| & t_{4,1} = s_{10} & \text{ } & t_{4,2} = s_{12} & \text{ } & t_{4,3} = s_{19} & \text{ } & \dots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{matrix}$$ Let $x'$ be Cantor's diagonal sequence with respect to the listing of binary strings $t_i$: $$x' = x_1x_2x_3\dots \text{, where each } x_i = \begin{cases} 0 & \text{if } t_{i,i} = 1 \\ 1 & \text{if } t_{i,i} = 0 \end{cases}$$ Let $x \in ( \,0,1) \,$ be created using the bits $x_i$ of $x'$ as follows: $$x = 0.x_1x_2x_3\dots$$ Comments: Where $s$ is computable and $x$ is computed from $s$, I believe that we must consider $x$ to be computable as well. Perhaps I am mistaken, thus my initial question. Question 2: If $x$ is in fact computable because $s$ was computable, then is it not possible to find a suitable $s$ so as to compute any given $x$? That is, I am tempted to speculate that $s$ can be computed in a manner such that the bits of the diagonal $x'$ of the listed strings $t_i$ can in turn result in any given $x$. Where the computable numbers are countable, I believe my speculation must be incorrect, however. Trivially, any desired bit $x_i$ can result from a given $s$. Showing that a suitable $s$ exists to compute all desired bits $x_i$ for a given $x$ is not trivial, however. My initial thought was that a suitable $s$ for any given $x$ could be constructed from a computable sequence of computable numbers using the "interleaving" technique shown in the accepted answer to this stackexchange thread (that is, create $s$ by interleaving a computable sequence of computable numbers $y_1, y_2, y_3\dots$), but if doing that, we might as well just interleave the computable sequence of computable numbers to directly create $x$ itself, so I am stalled out at the moment: https://math.stackexchange.com/quest.../183383#183383 Chances are, I just need to step back from this for a little bit. Getting an answer to my initial question would be a nice start. Thank you.
 June 12th, 2017, 05:13 PM #2 Senior Member   Joined: Aug 2012 Posts: 2,134 Thanks: 621 I didn't work through your post yet but you can create a noncomputable real by choosing a programming language, enumerating all the programs (by program we mean the kind that either halts or not, as in Turing machines), and writing a 1-bit or a 0-bit in the n-th binary position depending on whether program n halts or not. This is definable but can't be computable else we could use the bitstring to solve the halting problem. This method is similar but not identical to Chaitin's Omega. ps -- I read through your post. Your method can't do what you think it does since you're claiming something false. However can you step back and agree or disagree that you understand why if we simply list all the computable reals (of which there are only countably many) and take the anti-diagonal, the anti-diag can NOT be computable. That will give us a common base of understanding here. And reading through your post a second time makes me think this is the heart of the matter. Let's just handle that case first, what do you think? Last edited by Maschke; June 12th, 2017 at 05:21 PM.
June 12th, 2017, 07:20 PM   #3
Senior Member

Joined: Jun 2014
From: USA

Posts: 441
Thanks: 30

Quote:
 Originally Posted by Maschke ps -- I read through your post. Your method can't do what you think it does since you're claiming something false.
What do I think my method does? I speculated that $x$ is computable because some 'simple' tweaks to a program for $s$ would seemingly spit out $x$ instead. I'm literally asking though, so I don't think my method does anything at this point quite frankly.

Quote:
 Originally Posted by Maschke However can you step back and agree or disagree that you understand why if we simply list all the computable reals (of which there are only countably many) and take the anti-diagonal, the anti-diag can NOT be computable. That will give us a common base of understanding here. And reading through your post a second time makes me think this is the heart of the matter. Let's just handle that case first, what do you think?
I agree. Namely, if $C$ is a listing of all computable reals, Cantor's diagonal would produce a real not in the list, so such an anti-diagonal could not be computable. I think this next question highlights my (mis)understanding if you'll put up with one more quick definition so I can ask it:

If $C^I = c_1, c_2, c_3\dots$ is a listing of all computable reals in (0, 1) that are irrational, then there exists a real number $s^C \in ( \,0,1) \,$ such that the binary sequences $t_i$ produced using my above method would correlate with $C^I$ such that:

$c_1 = 0.t_{1,1}t_{1,2}t_{1,3}\dots$
$c_2 = 0.t_{2,1}t_{2,2}t_{2,3} \dots$
$c_3 = 0.t_{3,1}t_{3,2}t_{3,3}\dots$
.
.
.

In this case, $s^C$ cannot be computable either, right? I say this because I am still speculating that "$s$ is computable implies $x$ is computable" and similarly "$s^C$ is computable implies $x^C$ is computable" too. But, by definition of the list, $x^C$ could not be computable because $x^C$ is not in the list, so $s^C$ cannot be computable either.

June 12th, 2017, 09:22 PM   #4
Senior Member

Joined: Jun 2014
From: USA

Posts: 441
Thanks: 30

Quote:
 Originally Posted by AplanisTophet If $C^I = c_1, c_2, c_3\dots$ is a listing of all computable reals in (0, 1) that are irrational
Should just be "If $C^I = c_1, c_2, c_3\dots$ is a listing of all computable reals in [0, 1]." No need to restrict to irrationals, but infinite binary expansions should be used in the case of dyadic rationals where also 1 should be interpreted as 0.111... and 0 should be interpreted as 0.000..., otherwise there's nothing to stop $x^C$ from being equal to 0 or 1 and therefore both computable and not in the list.

Sorry.

Last edited by AplanisTophet; June 12th, 2017 at 09:39 PM.

June 12th, 2017, 09:40 PM   #5
Senior Member

Joined: Aug 2012

Posts: 2,134
Thanks: 621

Quote:
 Originally Posted by AplanisTophet I agree. Namely, if $C$ is a listing of all computable reals, Cantor's diagonal would produce a real not in the list, so such an anti-diagonal could not be computable.
Didn't work through your argument yet, just trying to sort this out myself.

Yes that's the problem. We have a list of all the computable numbers, so the anti-diag can't be computable. But if each row of the list contains digits cranked out by an algorithm, and the anti-diag rule "choose something other than the n-th digit of the n-th row" is clearly an algorithm, so why isn't the anti-diag computable?

The answer seems to be that the enumeration itself is not computable. I found this stackexchange thread. See Carl Mummert's answer. I still find this a bit murky -- more murky than I remember it being. I want to give this some more thought. I seem to recall understanding this at one point in the past but now it seems elusive. It's getting late, I'll sort this out tomorrow.

In any event, does this have any bearing on your original question? You mentioned Cantor diagonalization.

June 12th, 2017, 09:47 PM   #6
Senior Member

Joined: Jun 2014
From: USA

Posts: 441
Thanks: 30

Quote:
 Originally Posted by Maschke Didn't work through your argument yet, just trying to sort this out myself. Yes that's the problem. We have a list of all the computable numbers, so the anti-diag can't be computable. But if each row of the list contains digits cranked out by an algorithm, and the anti-diag rule "choose something other than the n-th digit of the n-th row" is clearly an algorithm, so why isn't the anti-diag computable? The answer seems to be that the enumeration itself is not computable. I found this stackexchange thread. See Carl Mummert's answer. I still find this a bit murky -- more murky than I remember it being. I want to give this some more thought. I seem to recall understanding this at one point in the past but now it seems elusive. It's getting late, I'll sort this out tomorrow. In any event, does this have any bearing on your original question? You mentioned Cantor diagonalization.
Thank you.

Again, sorry, see my revised definition of $C^I$ so that I can ensure the anti-diagonal isn't in the list. This is perhaps easier with binary sequences instead of the reals because of potentially tripping over the two different expansions for dyadic rationals. I think I patched it up, but essentially, that's what I arrive at is that $s^C$ cannot be computable again assuming if it were to be, then $x^C$ must be also which is impossible.

June 18th, 2017, 10:07 PM   #7
Senior Member

Joined: Aug 2012

Posts: 2,134
Thanks: 621

Quote:
 Originally Posted by AplanisTophet Comments: Where $s$ is computable and $x$ is computed from $s$, I believe that we must consider $x$ to be computable as well. Perhaps I am mistaken, thus my initial question.
Yes of course. Now that I've looked at this, the zigzag is a computable function of the digits of $s$. If $s$ is computable so is the zigzag and vice versa.

Quote:
 Originally Posted by AplanisTophet If $x$ is in fact computable because $s$ was computable, then is it not possible to find a suitable $s$ so as to compute any given $x$? That is, I am tempted to speculate that $s$ can be computed in a manner such that the bits of the diagonal $x'$ of the listed strings $t_i$ can in turn result in any given $x$. Where the computable numbers are countable, I believe my speculation must be incorrect, however.
I don't see how that works at all. To produce a noncomputable zigzag you have to start with a noncomputable $s$.

Last edited by Maschke; June 18th, 2017 at 10:14 PM.

June 18th, 2017, 11:26 PM   #8
Senior Member

Joined: Jun 2014
From: USA

Posts: 441
Thanks: 30

Quote:
 Originally Posted by Maschke I don't see how that works at all. To produce a noncomputable zigzag you have to start with a noncomputable $s$.

Quote:
 Originally Posted by AplanisTophet ...but essentially, that's what I arrive at is that $s^C$ cannot be computable again assuming if it were to be, then $x^C$ must be also which is impossible.
In other words, we can of course find a $s$ for any given $x$, but where we can prove that $x$ is not computable, then $s$ cannot be either. In this case, we can compare $s$ to the function $f( \,i,n) \,$ in Carl Mummert's answer (as shown in the stackexchange thread you found here https://math.stackexchange.com/quest...utable-numbers ). The function $f$ is not computable in that answer, just as I cannot find my computable $s$.

June 19th, 2017, 09:28 AM   #9
Senior Member

Joined: Aug 2012

Posts: 2,134
Thanks: 621

Quote:
 Originally Posted by AplanisTophet Sorry, I didn't realize you were still looking into this. You had already found the answer.
I've been trying to understand the fundamental reason that an enumeration of computable reals must itself be noncomputable. It's because a computable enumeration would violate the noncomputability of the halting problem. If you had a computable function that returns a halting algorithm for each input $n$, that would amount to knowing which algorithms halt, which is impossible.

However I have a couple of questions in my mind that I'm still working through.

In any event, this gives us a constructive Cantor proof in a sense. A constructivist who denies the existence of anything that's not computable would not regard the computable numbers as being countable, because there is no computable enumeration. Meaning (to a constructivist) that there is no enumeration at all.

Last edited by Maschke; June 19th, 2017 at 09:40 AM.

June 19th, 2017, 08:32 PM   #10
Senior Member

Joined: Jun 2014
From: USA

Posts: 441
Thanks: 30

Quote:
 Originally Posted by Maschke I've been trying to understand the fundamental reason that an enumeration of computable reals must itself be noncomputable.
I assume you mean an enumeration of all computable reals. If $s$ is computable, then $\{t_i\}, i \in \mathbb{N}$ is computable using my method from the OP. If $s$ is not computable, then $\{t_i\}, i \in \mathbb{N}$ is not computable either.

We do have $\{ x \in ( \,0,1) \, : \text{the sequence }\{0.t_i\}, i \in \mathbb{N} \text{ lists all computable reals in } [ \,0,1] \, \}$. I find that somewhat interesting, noting that each $x$ in the set is not computable.

 Tags noncomputable, reals

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Lalitha183 Abstract Algebra 3 June 2nd, 2017 11:02 PM zylo Topology 2 July 2nd, 2016 06:05 PM mathbalarka Number Theory 1 May 9th, 2013 06:51 AM iclestu Applied Math 2 October 26th, 2011 12:40 PM cernlife Real Analysis 5 May 30th, 2011 09:37 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top