My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree1Thanks
Reply
 
LinkBack Thread Tools Display Modes
June 12th, 2017, 05:03 PM   #1
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 315
Thanks: 21

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.
AplanisTophet is offline  
 
June 12th, 2017, 05:13 PM   #2
Senior Member
 
Joined: Aug 2012

Posts: 1,641
Thanks: 415

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.
Maschke is online now  
June 12th, 2017, 07:20 PM   #3
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 315
Thanks: 21

Quote:
Originally Posted by Maschke View Post
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 View Post
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.
AplanisTophet is offline  
June 12th, 2017, 09:22 PM   #4
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 315
Thanks: 21

Quote:
Originally Posted by AplanisTophet View Post
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.
AplanisTophet is offline  
June 12th, 2017, 09:40 PM   #5
Senior Member
 
Joined: Aug 2012

Posts: 1,641
Thanks: 415

Quote:
Originally Posted by AplanisTophet View Post


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.
Maschke is online now  
June 12th, 2017, 09:47 PM   #6
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 315
Thanks: 21

Quote:
Originally Posted by Maschke View Post
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.
AplanisTophet is offline  
June 18th, 2017, 10:07 PM   #7
Senior Member
 
Joined: Aug 2012

Posts: 1,641
Thanks: 415

Quote:
Originally Posted by AplanisTophet View Post
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 View Post
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.
Maschke is online now  
June 18th, 2017, 11:26 PM   #8
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 315
Thanks: 21

Quote:
Originally Posted by Maschke View Post
I don't see how that works at all. To produce a noncomputable zigzag you have to start with a noncomputable $s$.
It doesn't. You had already pointed me in the right direction.

Quote:
Originally Posted by AplanisTophet View Post
...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$.

Sorry, I didn't realize you were still looking into this. You had already found the answer.
AplanisTophet is offline  
June 19th, 2017, 09:28 AM   #9
Senior Member
 
Joined: Aug 2012

Posts: 1,641
Thanks: 415

Quote:
Originally Posted by AplanisTophet View Post
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.
Maschke is online now  
June 19th, 2017, 08:32 PM   #10
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 315
Thanks: 21

Quote:
Originally Posted by Maschke View Post
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.
AplanisTophet is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2017 My Math Forum. All rights reserved.