June 12th, 2017, 05:03 PM  #1 
Senior Member Joined: Jun 2014 From: USA Posts: 441 Thanks: 30  Noncomputable Reals Question 1: Can a noncomputable 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 1bit or a 0bit in the nth 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 antidiagonal, the antidiag 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:
Quote:
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:
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:
Yes that's the problem. We have a list of all the computable numbers, so the antidiag can't be computable. But if each row of the list contains digits cranked out by an algorithm, and the antidiag rule "choose something other than the nth digit of the nth row" is clearly an algorithm, so why isn't the antidiag 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:
Again, sorry, see my revised definition of $C^I$ so that I can ensure the antidiagonal 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:
Quote:
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:
Quote:
Sorry, I didn't realize you were still looking into this. You had already found the answer.  
June 19th, 2017, 09:28 AM  #9  
Senior Member Joined: Aug 2012 Posts: 2,134 Thanks: 621  Quote:
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:
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  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Reals  Lalitha183  Abstract Algebra  3  June 2nd, 2017 11:02 PM 
Power Set of the Reals is Countable  zylo  Topology  2  July 2nd, 2016 06:05 PM 
Independence of Reals  mathbalarka  Number Theory  1  May 9th, 2013 06:51 AM 
Computable completion  iclestu  Applied Math  2  October 26th, 2011 12:40 PM 
Integration over the reals? finding R(dx)  cernlife  Real Analysis  5  May 30th, 2011 09:37 PM 