My Math Forum Non-computable Reals

 Number Theory Number Theory Math Forum

June 20th, 2017, 08:23 PM   #21
Senior Member

Joined: Jun 2014
From: USA

Posts: 299
Thanks: 21

Quote:
 Originally Posted by Maschke 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. That's two words, yes/no and yes/no. It doesn't help me for you to re-argue a technical point when I'm just trying to establish whether or not we are remotely on the same page.
My apologies. Yes, I agree that you appear to be stuck on the point of why $s$ isn't computable when the sequences $t_i$ are a listing of all computable reals (and only the computable reals) on the interval [0,1]. No, I don't think I'm confused on that point because to think $s$ is computable is to deny the validity of Cantor's diagonal argument.

Proving that $s$ is computable is to prove that $x$ is computable also, but if $x$ is computable then $x$ is in the list so Cantor's diagonal argument must be faulty. We can't say Cantor's diagonal argument is faulty, so we must accept that $s$ is not computable.

June 20th, 2017, 08:30 PM   #22
Senior Member

Joined: Jun 2014
From: USA

Posts: 299
Thanks: 21

Quote:
 Originally Posted by Maschke 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?
Given an enumeration $t_i$ of all the computable numbers, then we can work backwords ($f^{-1}$, or anti-zigzag to try use your terminology) to create the number $s$. There are uncountably many such numbers $s$, which is what I noted with my set A, because there uncountably many ways to rearrange the listing $t_i$.

June 20th, 2017, 08:34 PM   #23
Senior Member

Joined: Aug 2012

Posts: 1,414
Thanks: 342

Quote:
 Originally Posted by AplanisTophet My apologies. Yes, I agree that you appear to be stuck on the point of why $s$ isn't computable when the sequences $t_i$ are a listing of all computable reals (and only the computable reals) on the interval [0,1]. No, I don't think I'm confused on that point because to think $s$ is computable is to deny the validity of Cantor's diagonal argument. Proving that $s$ is computable is to prove that $x$ is computable also, but if $x$ is computable then $x$ is in the list so Cantor's diagonal argument must be faulty. We can't say Cantor's diagonal argument is faulty, so we must accept that $s$ is not computable.
Yes of course. We agree on that.

Which part of everything else that I'm writing are you not reading or not understanding or regarding as not coherent enough to merit a response?

Given an enumeration of the computable reals, we anti-zigzag it to work back to a computation of the enumeration.

Why doesn't this argument work? We KNOW it's wrong, we agree with that. But where exactly is the flaw?

I believe there is some understanding to be had in answering this question.

I can not quite visualize or grasp the corresponding situation in the inverse case. Given a set-theoretic enumeration, why can't I anti-zigzag to compute the enumeration?

You keep saying, "Because we know we can't." Right. Now ask yourself WHY the anti-zigzag argument fails.

Also I think there is confusion between:

* Why the antidiag of an enumeration of ALL computables can't be computable; and

* Why my anti-zigzag argument fails.

These two are related, essentially the same question, but we have not grokked exactly why they are the same question.

Last edited by Maschke; June 20th, 2017 at 08:38 PM.

June 20th, 2017, 08:36 PM   #24
Senior Member

Joined: Jun 2014
From: USA

Posts: 299
Thanks: 21

Quote:
 Originally Posted by Maschke Bonus question. Have you noticed that we could play the same game with columns(zigzag(s)) just as well? Is this interesting or trivial?
That was another of my original intents, but I didn't get that far.

Cantor provided only one anti-diagonal in his classic proof, but there are uncountably many ways to create anti-diagonals (where all that is needed to create an anti-diagonal in this sense is to ensure that at least one, but possibly more, bits of the anti-diagonal differ from some bits of each element of a listing). Demonstrating that there are uncountably many computable anti-diagonals should be impossible too. This is ultimately what I've been pondering since the start of this thread.

June 20th, 2017, 08:39 PM   #25
Senior Member

Joined: Aug 2012

Posts: 1,414
Thanks: 342

Quote:
 Originally Posted by AplanisTophet That was another of my original intents, but I didn't get that far. Added bonus: Cantor provided only one anti-diagonal in his classic proof, but there are uncountably many ways to create anti-diagonals (where all that is needed to create an anti-diagonal in this sense is to ensure that at least one, but possibly more, bits of the anti-diagonal differ from some bits of each element of a listing). Demonstrating that there are uncountably many computable anti-diagonals should be impossible too. This is ultimately what I've been pondering since the start of this thread.
You're changing the subject again?

This snapping back and forth isn't helping. I'm going to stop for a while. I'd like you to respond to the points I'm making if you are so inclined.

June 20th, 2017, 08:41 PM   #26
Senior Member

Joined: Jun 2014
From: USA

Posts: 299
Thanks: 21

Quote:
 Originally Posted by Maschke You keep saying, "Because we know we can't." Right. Now ask yourself WHY the anti-zigzag argument fails. Also I think there is confusion between: * Why the antidiag of an enumeration of ALL computables can't be computable; and * Why my anti-zigzag argument fails. These two are related, essentially the same question, but we have not grokked exactly why they are the same question.
Understood. I don't have the answer to that. I only have the classic proof using Cantor's diagonal, but Carl Mummert mentioned something:

"The diagonalization argument is actually the "standard" way to prove there is no f(i,n) with those properties."

If the diagonalization argument is merely the "standard" way then this implies there are other "known" ways.

June 20th, 2017, 08:49 PM   #27
Senior Member

Joined: Aug 2012

Posts: 1,414
Thanks: 342

Quote:
 Originally Posted by AplanisTophet Understood. If the diagonalization argument is merely the "standard" way then this implies there are other "known" ways.
Yes. I'm trying to get intuitive understanding of why the antidiag isn't computable. I can see the forward direction but I can't see why the inverse zigzag idea doesn't work. I'm missing something in my understanding.

In fact I pretty much understand it completely in my head, but my formal writeup is just stuck somewhere. I'm trying to get some understanding. At this point it's glib to invoke diagonalization. That's a proof that imparts no understanding. And it doesn't explain the seeming paradox of reverse zigzagging.

Here's something that bothers me.

* You claim that given an enumeration of the computables there's an s such that rows(zigzag(s)) outputs exactly that enumeration; and

* I have expressed doubt that there is in general such an s, and challenged you to argue that there is such an s; and

* So far you have not engaged this point.

This may or not be the central point, but it's one of the points that's bothering me and I'd like to draw your attention to it.

Last edited by Maschke; June 20th, 2017 at 08:52 PM.

 June 20th, 2017, 08:51 PM #28 Senior Member   Joined: Jun 2014 From: USA Posts: 299 Thanks: 21 PS - You keep saying "given" an enumeration of the computable reals. Once we are given that, we can of course anti-zigzag to compute $s$. We can't just be given that enumeration because your question rests on why we can't compute that enumeration (to which I cited your relation to the halting problem issue). We know the enumeration exists in a set-theoretic sense based on axioms. Distinguishing between that which exists via set theoretic axioms and that which is computable is the heart of the issue. Agreed?
June 20th, 2017, 08:59 PM   #29
Senior Member

Joined: Aug 2012

Posts: 1,414
Thanks: 342

Quote:
 Originally Posted by AplanisTophet PS - You keep saying "given" an enumeration of the computable reals. Once we are given that, we can of course anti-zigzag to compute $s$.
But we ARE given a set-theoretic enumeration of the computable reals. They're a countable set. There's a bijection between them an the natural numbers; and we can induce an enumeration via the standard order on the naturals. Every bijection is invertible. So given a bijection we list the computable numbers in rows, as in your table. Then we anti-zigzag.

THIS IS THE POINT! We ARE given an enumeration of the reals. Why doesn't anti-zigzagging work????

Quote:
 Originally Posted by AplanisTophet We can't just be given that enumeration
Why not? We can enumerate any countable set. That's basic set theory. We can enumerate the computable reals as $c_1, c_2, \dots$. Nobody should look twice at that statement. Normally nobody would.

Quote:
 Originally Posted by AplanisTophet because your question rests on why we can't compute that enumeration (to which I cited your relation to the halting problem issue).
Yes we already know the enumeration isn't computable. So what EXACTLY is wrong with the anti-zigzag argument? You haven't told me that yet.

Quote:
 Originally Posted by AplanisTophet We know the enumeration exists in a set-theoretic sense based on axioms. Distinguishing between that which exists via set theoretic axioms and that which is computable is the heart of the issue. Agreed?
Yes. So what exactly is the flaw in the anti-zigzag argument?

We DO have an enumeration, which is a mapping from the naturals to the computables, along with the inverse map from the computables to the naturals. Simply via the induced order of the naturals.

So now we have some enumeration. Maybe we think we have no way to compute it. But we seemingly CAN compute it via inverse zigzagging.

What is wrong with that argument?????? Specifically

I'm not saying this is particularly obvious. I believe that by the time I can answer this question to my own satisfaction I'll have learned something more about computablity theory. I think there's some insight to be had here.

By the way I think your zigzagging idea is very insightful. It sparks a lot of really good questions.

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

June 21st, 2017, 06:14 AM   #30
Senior Member

Joined: Jun 2014
From: USA

Posts: 299
Thanks: 21

Quote:
 Originally Posted by Maschke So now we have some enumeration. Maybe we think we have no way to compute it. But we seemingly CAN compute it via inverse zigzagging. What is wrong with that argument?????? Specifically
I think walking through the process of creating the enumeration helps.

1) Let B be an enumeration of the well-formed formulas of a formal language capable of expressing the computable reals.

2) ‘Compute’ a listing C of those formulas for computable reals. In set theory, we rely on the axiom schema of specification generally, where we are guaranteed an axiom saying “this subset of B exists” for each formula in the language of, for example, ZFC. While such a formula $f$ exists in ZFC by reason of an axiom (simply, where the formula $f$ is equivalent to saying “let C = { x in B : x is a formula for a computable real }”), it may not, or in fact cannot, exist in the formal language used to compute the computable reals. Namely, computing the formula for determining which elements of B are formulas for computable reals is different than simply asserting a set containing only those formulas exists by relying on the axiom schema of specification.

3) Inverse zigzag to compute $s$, meaning $f^{-1}( \,C) \, = s$.

The problem obviously arises in step 2. I still don’t think I’ve fully answered your question, but hopefully it’s extremely apparent why computing the formula is different than simply saying “let this subset exist” based on the axiom schema.

Last edited by AplanisTophet; June 21st, 2017 at 06:33 AM.

 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