June 19th, 2017, 08:47 PM  #11  
Senior Member Joined: Aug 2012 Posts: 1,678 Thanks: 436  Quote:
Not disagreeing with you about anything, just trying to understand your second para without having to work through your idea, which I don't much understand the point of. Last edited by Maschke; June 19th, 2017 at 08:52 PM.  
June 19th, 2017, 10:02 PM  #12  
Senior Member Joined: Jun 2014 From: USA Posts: 320 Thanks: 23  Quote:
Let A = { x in (0,1) : f(x) is a sequence containing all computable reals in [0,1] }. My second paragraph was to acknowledge that each element of A is a noncomputable real in (0,1). Further, A must be uncountable given the uncountably many ways to rearrange a sequence of order type $\omega$. I am not disagreeing with anything you've said. I am interested in what you come up with. No, of course I do not have a computable way to enumerate the computable reals, as we've already acknowledged that's impossible. The point of my idea was originally to contemplate whether we could come up with a computable $s$ so as to derive any given $x$. If $s$ produces all computable reals in the interval [0,1], however, then we know $x$ (the antidiagonal of f(s)) is not computable. If $x$ is not computable, then $s$ must not be either, so I ended up with a proof that there is no computable way to enumerate the computable reals on the interval [0,1].  
June 19th, 2017, 10:24 PM  #13 
Senior Member Joined: Aug 2012 Posts: 1,678 Thanks: 436  Ok I see what you're doing now. Let me percolate a while. The $t$'s are a computable function of $x$, right? If you wanted you could work out exactly where each bit position of $x$ ends up. Now that I see what you're doing I'll work through the rest of your idea.

June 20th, 2017, 06:51 PM  #14 
Senior Member Joined: Aug 2012 Posts: 1,678 Thanks: 436 
I think I have this sorted out. First note the tremendous regularity of your zigzag pattern. Just writing the indices we have $$\begin{matrix} \begin{matrix} 1 & \to & 2 & ~~ & 6 & \to & 7 & ~~ & 15 & \to & 16 & ~~ & 28 & \to & 29 \\ ~~ &\swarrow & ~~ & \nearrow &~~ &\swarrow & ~~ & \nearrow & ~~ &\swarrow & ~~ & \nearrow & ~~ & \swarrow \\ 3 & ~~ & 5 & ~~ & 8 & ~~ & 14 & ~~ & 17 & ~~ & 27 & ~~ & 30 \\ \downarrow & \nearrow & ~~ & \swarrow &~~ &\nearrow & ~~ & \swarrow & ~~ &\nearrow & ~~ & \swarrow \\ 4 & ~~ & 9 & ~~ & 13 & ~~ & 18 & ~~ & 26 & ~~ & 31 \\ ~~ &\swarrow & ~~ & \nearrow &~~ &\swarrow & ~~ & \nearrow & ~~ &\swarrow \\ 10 & ~~ & 12 & ~~ & 19 & ~~ & 25 & ~~ & 32 \\ \downarrow &\nearrow & ~~ & \swarrow &~~ &\nearrow & ~~ & \swarrow \\ 11 & ~~ & 20 & ~~ & 24 & ~~ & 33 \\ ~~ & \swarrow & ~~ & \nearrow &~~ &\swarrow \\ 21 & ~~ & 23 & ~~ & 34 \\ \downarrow & \nearrow & ~~ & \swarrow \\ 22 & ~~ & 35 \\ ~~ &\swarrow \\ 36 \end{matrix} \end{matrix}$$ In the top row we have pairs $1 \to 2$, $6 \to 7$, $15 \to 16$, etc. The intervals between the pairs are $4, 8, 12, 16, \dots$. Similar patterns are evident in each row and column. With sufficient motivation we could write out an explicit formula to map each index $n$ to its corresponding row and column in the table, and vice versa; and that any specific mapping (in either direction) can be programmatically determined in finitely many steps. I haven't bothered to work out the details but I hope this is perfectly agreeable. It would be something along the lines of the Cantor pairing function. Therefore your zigzag mapping is computable in both directions. That is, given bit position $n$ I can determine its (column, row) coordinates in the table, and vice versa. It follows that: Conclusion 1: If $s$ (the input real) is computable, then so is every row of the table. Conclusion 2: Conversely if every row of the table is computable, so is $s$. This I believe was your main question. It's certainly true that there are uncountably many different sequences of computable reals. But they can only output countably many distinct rows. Each row is generated by uncountably many distinct input values. In particular your set $A$ consisting of all the inputs whose tabular output consists entirely of computable rows must consist only of computable reals. [It seems likely that it contains all the computable reals, but I didn't try to prove that yet]. It's interesting to consider what happens when $s$ is noncomputable. For example let $s$ be noncomputable and replace digit positions $1, 2, 6, 7, 15, 16, 28, 29, \dots$ with zero. Then t_0 is a sequence of all zeros, which is computable. Therefore: * Conclusion 3: A noncomputable input may produce one or more computable rows. The only thing we know for sure (by conclusion 2) is that a noncomputable real can't output a table with all computable rows. At least one row must be noncomputable. I note in passing that this analysis applies to any method of computably splitting a sequence into countably many subsequences. For example we could take all the even digit positions as your $t_1$, all the multiples of $3$ (ignoring the ones that are already multiples of $2$) as $t_2$, then the multiples of $5$, etc., one $t$row for each prime. Everything would be the same. Is this sensible? I didn't spend any time on your antidiagonal question. Is it still relevant? ps  Offhand (haven't thought about it much) if the input is computable there's no reason the antidiag can't be as well. The list consists of computables but not ALL computables, so there's no contradiction in the antidiag being computable as well. In fact it must be, since in this case the enumeration is computable. In fact: Conclusion 4: If the input is computable then the antidiag must be. As a corollary, no computable input can generate ALL the noncomputables as rows. Question: Do we think some noncomputable input might generate all the computables as rows? It couldn't produce ONLY computable rows but it might perhaps produce every computable along with a noncomputable or two (or infinitely many). Last edited by Maschke; June 20th, 2017 at 07:40 PM. 
June 20th, 2017, 08:08 PM  #15  
Senior Member Joined: Jun 2014 From: USA Posts: 320 Thanks: 23  Quote:
Where the sequences $t_i$ represent all computable reals on the interval [0,1], then the antidiagonal $x$ is also, of course, not computable. My set A above... A = { x in (0,1) : f(x) is a listing of all computable reals in [0,1] } ... is an uncountable set containing only noncomputable reals. This is because there are uncountably many ways to rearrange a listing of order type $\omega$ and it's not possible for a computable $s$ to result in a listing of all computable reals on the interval [0,1]. The reason no computable $s$ exists where f(s) results in a listing $t_i$ of all computable reals on the interval [0,1] is that Cantor's diagonal $x$ can be used to generate a noncomputable real not in the list. If $x$ is not computable, then $s$ cannot be either because you've correctly assessed that...: Quote:
Otherwise, I believe we're on the same page and I agree with everything you've said.  
June 20th, 2017, 08:37 PM  #16  
Senior Member Joined: Aug 2012 Posts: 1,678 Thanks: 436  Quote:
(a) A listing (or enumeration) of computable numbers; and (b) A listing or enumeration of ALL the computable real numbers. Suppose we have (a). We have a sequence of computable numbers that is infinite but is still missing some computable numbers. In this case: * The antidiagonal may well be computable. After all we can show the antidiag is not on the list; but why should it be? We just found one of the computables that weren't on our list. No contradiction. * Then we can inversezigzagify to obtain a computable real number that generated the list .[I hope the terminology was obvious. We create your zigzag table and take the inverse function, which is also computable. [Do we agree on this? I think it's an important assumption on my part]. On the other hand suppose we have an enumeration of ALL the computables. We already know it's not on the list hence it can't be computable; hence the enumeration itself can not be computable. So ... what happens when you apply inversezigzagification to the table? You get some number but it can't be computable. I agree with you. This happens to be the EXACT point I was stuck on a few days ago (and still am) in my effort to understand the fundamental reason why the antidiag of an enumeration of all the computables can't be computable. If we're given an enumeration of the computables, that mean we know for each row and column pair, what is the digit. So why can't I just apply the inverse zigzag function. I agree that I am totally stuck on this point. There are a couple of stackexchange threads on the subject of inverses of computable functions, and now I'll have to go read them. And if there's something wrong with my understanding of the ALLcomputables case, there might be something wrong with my understanding of the SOMEcomputables case. If I can figure this out I'll definitely learn something. Last edited by Maschke; June 20th, 2017 at 08:42 PM.  
June 20th, 2017, 08:46 PM  #17  
Senior Member Joined: Jun 2014 From: USA Posts: 320 Thanks: 23  Quote:
...and I agree. To generate the list of all computable reals (in this case on the interval [0,1]), we rely on enumerating the wellformed formulas of some formal language capable of expressing all the computable reals. The halting problem clarifies that we cannot have a formula to determine which wellformed formulas will halt. If we can't even determine which ones halt, how are we supposed to determine which are formulas for computable reals? I think we can't, thus I accepted your own answer to your own question.  
June 20th, 2017, 09:02 PM  #18  
Senior Member Joined: Aug 2012 Posts: 1,678 Thanks: 436  Quote:
And what I THINK that YOU THINK I am wrong about is this: If we are given a settheoretic bijection between the computable reals and the naturals; then if I claim inversezigzagging is computable, then I can compute the enumeration. So WHAT IS THE ANSWER to this puzzler? Do you agree that I am stuck on this point? If I am stuck on this point, are you stuck on this point too? Or do you have the answer? It's not enough to say well there's no computable enumeration so the inversezigzag doesn't work. But why doesn't it? What's wrong with my argument? Do you agree with what I wrote? About trying to describe what I am confused about, and asking if you think I am confused about the same thing, and if so, do you claim to not be confused? Now I'm really confused. I may have to go percolate a while.  
June 20th, 2017, 09:11 PM  #19  
Senior Member Joined: Jun 2014 From: USA Posts: 320 Thanks: 23  Quote:
The formula for generating the list is $s$ itself (think of $s$ as not only a number, but also the formula for generating the sequences $t_i$ that it is). We conclude $s$ is not computable because we know $x$ cannot be computable. Likewise, if $x$ were computable then $s$ must be computable. If there is another way to prove that $s$ is not computable, then I'm not sure what it is. I too originally thought that if all the sequences $t_i$ were computable then $s$ should be too, but I was wrong apparently...:  
June 20th, 2017, 09:18 PM  #20  
Senior Member Joined: Aug 2012 Posts: 1,678 Thanks: 436  Quote:
* Do you agree that I am confused about what you think I'm confused about; and * If so, do you yourself claim to be confused or not confused? It is counterproductive at this moment (from my perspective) for you to relitigate a technical argument when I am not certain we're even on the same page. By the way I will make one technical point. I agree that there is a settheoretic enumeration of the computable reals. I do NOT stipulate at this moment that there is some s such that zigzag(s) is a complete enumeration of the ALL the computable reals. That may well turn out to be a critical issue. Can you convnce me that there is such an s? Computable or not. Why should there be? In fact didn't I ask this very question earlier? Given an enumeration of all the computable numbers, how do we know there's a single s such that rows(zigzag(s)) produces exactly that enumeration? Bonus question. Have you noticed that we could play the same game with columns(zigzag(s)) just as well? Is this interesting or trivial? Last edited by Maschke; June 20th, 2017 at 09:27 PM.  

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 