My Math Forum Non-computable Reals

 Number Theory Number Theory Math Forum

June 19th, 2017, 07:47 PM   #11
Senior Member

Joined: Aug 2012

Posts: 1,414
Thanks: 342

Quote:
 Originally Posted by AplanisTophet 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.
I didn't understand your second para, can you explain what you're trying to say? I didn't have the patience tonight to go back and sort out your notation. Did you understand my post? Are you agreeing or disagreeing with some aspect of it? Something seems to be missing from your notation. Are you saying you have a computable way to enumerate the computable reals?

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 07:52 PM.

June 19th, 2017, 09:02 PM   #12
Senior Member

Joined: Jun 2014
From: USA

Posts: 299
Thanks: 21

Quote:
 Originally Posted by Maschke I didn't understand your second para, can you explain what you're trying to say?
I started with a number $s$ in the OP and used its bits to create a sequence of binary strings $t_i$. Equivalently, let f($s$) = $t_1, t_2, t_3, \dots$. If I let $s$ be non-computable, then it's possible that f($s$) equals a sequence of all computable reals on the interval [0,1].

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 non-computable 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 anti-diagonal 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, 09:24 PM   #13
Senior Member

Joined: Aug 2012

Posts: 1,414
Thanks: 342

Quote:
 Originally Posted by AplanisTophet I started with a number $s$ in the OP and used its bits to create a sequence of binary strings $t_i$.
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, 05:51 PM #14 Senior Member   Joined: Aug 2012 Posts: 1,414 Thanks: 342 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 06:40 PM.
June 20th, 2017, 07:08 PM   #15
Senior Member

Joined: Jun 2014
From: USA

Posts: 299
Thanks: 21

Quote:
 Originally Posted by Maschke * 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. ... 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).
The computable reals are countable, so we can of course have a listing of them. If there is a listing, then we can go backwards from the listing to $s$. Therefore, your conclusion is wrong. In fact, in such a case, $s$ is not computable but the sequences $t_i$ (comprising all computable reals on the interval [0,1]) are all computable by definition. Again, compare $s$ in this case to Carl Mummert's function f(i, n) in the stackexchange thread where computing $s$ would be equivalent to computing the function f(i, n).

Where the sequences $t_i$ represent all computable reals on the interval [0,1], then the anti-diagonal $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 non-computable 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 non-computable real not in the list. If $x$ is not computable, then $s$ cannot be either because you've correctly assessed that...:

Quote:
 Originally Posted by Maschke Conclusion 4: If the input is computable then the antidiag must be.
... and likewise if $x$ is not computable then neither is $s$.

Otherwise, I believe we're on the same page and I agree with everything you've said.

June 20th, 2017, 07:37 PM   #16
Senior Member

Joined: Aug 2012

Posts: 1,414
Thanks: 342

Quote:
 Originally Posted by AplanisTophet The computable reals are countable, so we can of course have a listing of them. If there is a listing, then we can go backwards from the listing to $s$. Therefore, your conclusion is wrong.
I haven't got an answer yet (if I ever will) but I wanted to talk about the two cases where we have:

(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 inverse-zigzagify 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 inverse-zigzagification 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 ALL-computables case, there might be something wrong with my understanding of the SOME-computables case.

If I can figure this out I'll definitely learn something.

Last edited by Maschke; June 20th, 2017 at 07:42 PM.

June 20th, 2017, 07:46 PM   #17
Senior Member

Joined: Jun 2014
From: USA

Posts: 299
Thanks: 21

Quote:
 Originally Posted by Maschke If we're given an enumeration of the computables, that mean[s] we know for each row and column pair, what is the digit. So why can't I just apply the inverse zigzag function.

Quote:
 Originally Posted by Maschke 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.
...and I agree. To generate the list of all computable reals (in this case on the interval [0,1]), we rely on enumerating the well-formed 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 well-formed 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, 08:02 PM   #18
Senior Member

Joined: Aug 2012

Posts: 1,414
Thanks: 342

Quote:
 Originally Posted by AplanisTophet ...and I agree. To generate the list of all computable reals (in this case on the interval [0,1]), we rely on enumerating the well-formed 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 well-formed 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.
Yes I totally agree. But a moment ago you said I was wrong about something.

And what I THINK that YOU THINK I am wrong about is this:

If we are given a set-theoretic bijection between the computable reals and the naturals; then if I claim inverse-zigzagging 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 inverse-zigzag 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, 08:11 PM   #19
Senior Member

Joined: Jun 2014
From: USA

Posts: 299
Thanks: 21

Quote:
 Originally Posted by Maschke Yes I totally agree. But a moment ago you said I was wrong about something. And what I THINK that YOU THINK I am wrong about is this: If we are given a set-theoretic bijection between the computable reals and the naturals; then if I claim inverse-zigzagging 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 inverse-zigzag 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.
If $s$ is such that f($s$) is a desired listing of all computable reals on the interval [0,1], and $x$ is the anti-diagonal in (0,1) which cannot be on the list and therefore cannot be computable, then we've agreed that $s$ cannot be computable either, correct?

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...:

Quote:
 Originally Posted by AplanisTophet ...so I ended up with a proof that there is no computable way to enumerate the computable reals on the interval [0,1].

June 20th, 2017, 08:18 PM   #20
Senior Member

Joined: Aug 2012

Posts: 1,414
Thanks: 342

Quote:
 Originally Posted by AplanisTophet If $s$ is such that f($s$) is a desired listing of all computable reals on the interval [0,1], and $x$ is the anti-diagonal in (0,1) which cannot be on the list and therefore cannot be computable, then we've agreed that $s$ cannot be computable either, correct? 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...:
I simply asked if you agree that I am confused about what I think I'm confused about, and if you claim not to be confused. I'm looking for two one-word answers:

* 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 re-litigate 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 set-theoretic 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 08:27 PM.

 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 10:02 PM zylo Topology 2 July 2nd, 2016 05:05 PM mathbalarka Number Theory 1 May 9th, 2013 05:51 AM iclestu Applied Math 2 October 26th, 2011 11:40 AM cernlife Real Analysis 5 May 30th, 2011 08:37 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top