The Computable Reals (alpha version)

On Aug 27, 7:36 pm, ju...@diegidio.name wrote:
> On 28 Aug, 03:27, Mariano Suárez-Alvarez
>
> <mariano.suarezalva...@gmail.com> wrote:
>
> > It would not hurt you to read up a bit on
> > the convergence of series...
>
> I second that.
>
> Good night, Mariano.

sounds like a great topic

in particular
there is a well-known theorem in this theory
which states

oo
---
\
if the terms a of the series / (-1) a
j --- j
j=0

converge monotonically to 0
then the series converges

this is even true constructively

basically
this is because the error of the jth partial sum
is bounded by the jth term
(the >= order implies positive differences)

the limit is bounded to a closed interval

;&e:
> ^^$@:
> > Suppose we look for the first place '9' appears in pi, then
> > '99', '999', '9999', '999999', '9999999', etc.

> > first '9': 3.14159 : position number 5
> > first '99': position number 44
> > first '999': position 762 counting from
> > the first digit after the decimal point.
> > " " '9999': 762
> > --- '99999': 762
> > --- '999999' : 762
> > --- '9999999': position 1,722,776
> > and so on
> > source:http://www.angio.net/pi/bigpi.cgi

> > now we form the series:
> > 1/sqrt(5) - 1/sqrt(44) + 1/sqrt(762) - 1/sqrt(762) + 1/sqrt(762)
> > - 1/sqrt(762) + 1/sqrt(1722776) - .. + .........

> > It's a good bet that this alternating series converges, but
> > no one has been able to prove it. Too little is known about the
> > pseudo-randomness quality of the digits of pi.

> I'm afraid I still don't get it. Aren't the terms of that sum
> obviously decreasing, so that our sum surely can be approximated
> within the bounds of any given epsilon, provided that we just consider
> enough terms?

so the challenge is to prove that the terms

1
a = -------
j '\/ p
j

p = the 1st location ~~
j in _decimal_representation_ of pi (||)
of the finite _decimal_representation_
of j
10 - 1

satisfy the conditions necessary
for a convergent alternating series


it's clear that if position j has a string of k '9's
then for all j < k

p < p
j = k

because even if j '9's have not yet occurred
they are inherent in the larger string

conditional existence is proven

if p exists
k

p exists
j

but the actual proof of the existence of any such term
is not handled by such methods
(what if 23 '9's never show up in the expansion of pi?)

so
much of the trick in this challenge
is in proving this existence question

this is a question on infinite string representations
with given finite substrings

the key problem is:
describe the collection of substrings S of some
(most likely finitely specified)
infinite string L

can such a description be made recursive?

there are many easy theorems about the rationals

only certain repeating patterns are available
so the space of substrings can be quite constrained

(the infinite singly repeated symbol
giving a minimax constraint of (1/10)^n
of all substrings of length n
(ie. 1)

length and complexity of patterns can be measured
using these properties of rationals repeating representations

but the questions get much harder
when irrationals are looked at

what coverage does a given irrational do?
even that simple question
becomes difficult

and pi is transcendental

does that mean anything here?

but
bringing back the topic
after this long meander

pi is representable by the series

oo
---
\ j 1
4 / (-1) ------
--- 2j + 1
j=0


(which
due to an illness of late
i must kindly point is a multisection
of an even more famous series)

does this representation
have anything to say about the challenge at hand?

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
galathaea: prankster, fablist, magician, liar

Mariano Suárez-Alvarez a écrit :
> On Aug 27, 9:59 pm, ju...@diegidio.name wrote:
>> On 27 Aug, 19:09, David Bernier <david...@earth.sol> wrote:
>>
>>
>>
>>> ju...@diegidio.name wrote:
>>>> On 27 Aug, 10:17, David Bernier <david...@earth.sol> wrote:
>>>>> ju...@diegidio.name wrote:
>>>>>> On 26 Aug, 06:24, David Bernier <david...@videotron.ca> wrote:
>>>>>>> By restricting to primitive recursive sequences, some reals are
>>>>>>> not definable. Basically, you have to go back to Ackerman
>>>>>>> around 1920s or 1930s for people to realize that some
>>>>>>> computable functions f: N -> N are not primitive recursive.
>>>>>> So, are they really *computable* if we are not guaranteed (we have not
>>>>>> proved) that the loop terminates? In that, they are non-halting TMs,
>>>>>> which to me is contradicting their supposed "computability".
>>>>> Turing's 1936 paper and explanations citing Turing (1936) are
>>>>> the best places to look. Say a computer program (idealized what
>>>>> with being eternal, etc) prints better and better approximations
>>>>> to a computable real in Turing's sense. If it's based on
>>>>> unconditional loops [ while( such_and_such == True) { ... }; ] ,
>>>>> then it could happen that we humans couldn't see that it
>>>>> will print approximations forever, IOW we might wonder:
>>>>> ``could it get stuck in an infinite loop some time and never get
>>>>> to 10^100 printed approximations?", and we'd be stuck.
>>>> I am aware abaout Minsky/Turing's definition of computables, it's on
>>>> Wikipedia:http://en.wikipedia.org/wiki/Computable_number
>>>> The point remains, though I might be putting it more or less
>>>> improperly: if there is no proof that the loop will terminate (if we
>>>> are not "guaranteed" the loop terminates) it is *not* a "halting
>>>> machine" in the first place, and, in particular, it *cannot* be a
>>>> machine that outputs a computable number, by those very definitions.
>>>> Indeed, in production, a loop that is not guaranteed to terminate
>>>> would simply not pass peer review.
>>> [ I'll pass on this for now ... ]
>> But I'd still be interested in a comment, as this is were I am stuck.
>>
>>
>>
>>>>> But on the other hand, even if we knew a program prints rationals
>>>>> forever, it's a different and more complicated question to
>>>>> figure out if it actually converges. Sometimes, it might
>>>>> indeed converge, but we wouldn't know it.
>>>> On this I have a basic doubt: let's take our TM that can output in
>>>> succession the digits of a computable number; then each digit is less
>>>> significant than the preceeding, so even in the case of non-periodic
>>>> expansions, still we always get a "convergent" sequence, at least in
>>>> the sense that we can always get a (rational) number that differs from
>>>> the ideal complete expansion by less than any given error.
>>> Suppose we look for the first place '9' appears in pi, then
>>> '99', '999', '9999', '999999', '9999999', etc.
>>> first '9': 3.14159 : position number 5
>>> first '99': position number 44
>>> first '999': position 762 counting from
>>> the first digit after the decimal point.
>>> " " '9999': 762
>>> --- '99999': 762
>>> --- '999999' : 762
>>> --- '9999999': position 1,722,776
>>> and so on
>>> source:http://www.angio.net/pi/bigpi.cgi
>>> now we form the series:
>>> 1/sqrt(5) - 1/sqrt(44) + 1/sqrt(762) - 1/sqrt(762) + 1/sqrt(762)
>>> - 1/sqrt(762) + 1/sqrt(1722776) - .. + .........
>>> It's a good bet that this alternating series converges, but
>>> no one has been able to prove it. Too little is known about the
>>> pseudo-randomness quality of the digits of pi.
>> I'm afraid I still don't get it. Aren't the terms of that sum
>> obviously decreasing, so that our sum surely can be approximated
>> within the bounds of any given epsilon, provided that we just consider
>> enough terms?
>
> It would not hurt you to read up a bit on
> the convergence of series...

Good idea. Note that * every* alternating series with termsd dfecreasing
towards 0 converges...
>
> -- m

On 28 Aug, 02:47, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> ju...@diegidio.name writes:
>
> >[*]This has to do with the Church-Turing Thesis: is really a TM
> > equivalent to a Lambda and viceversa? I'm inclined to think TMs are
> > rather a subset of Lambdas, where Lambdas allow treatment of
> > uncomputable entities w.r.t. TMs.
>
> TMs are equivalent to the lambda calculus and vice versa. This is a
> basic proof in the theory of computation. The Church-Turing Thesis is
> something else and is rather more vague.

Pardon me, which proof is it? A link might be just perfect.

-LV

On 25 Aug, 02:43, ju...@diegidio.name wrote:
> The Computable Reals (beta)
> ---------------------------
> Julio Di Egidio (LV)
> julio at diegidio dot name
> (c)2008 LV on behalf of sci.math, sci.logic, comp.theory
> All right reserved.
> alpha:http://groups.google.co.uk/group/sci...487daf70efed0e

I have published a revised and working code here:

http://julio.diegidio.name/Sandbox/C...Reals.beta.htm

It is fairly undocumented and very essential, but should be very clear
to those who have followed the discussion and know what to look for.

At the moment, it shows first a bunch of random strings with their
corresponding index. Then it goes through few iterations of the
inductive construction for the list of binary expansions, using the
very list entries to build sample strings whose index is given aside.
Hit reload to generate another series of the random samples. The
source code is available, just do a view-source: all should be there,
but please feel free to ask for clarifications if needed.

-LV

On 28 Aug, 14:45, ju...@diegidio.name wrote:
> On 25 Aug, 02:43, ju...@diegidio.name wrote:
>
> > The Computable Reals (beta)
> > ---------------------------
> > Julio Di Egidio (LV)
> > julio at diegidio dot name
> > (c)2008 LV on behalf of sci.math, sci.logic, comp.theory
> > All right reserved.
> > alpha:http://groups.google.co.uk/group/sci...487daf70efed0e
>
> I have published a revised and working code here:
>
> http://julio.diegidio.name/Sandbox/C...Reals.beta.htm
>
> It is fairly undocumented and very essential, but should be very clear
> to those who have followed the discussion and know what to look for.
>
> At the moment, it shows first a bunch of random strings with their
> corresponding index. Then it goes through few iterations of the
> inductive construction for the list of binary expansions, using the
> very list entries to build sample strings whose index is given aside.
> Hit reload to generate another series of the random samples. The
> source code is available, just do a view-source: all should be there,
> but please feel free to ask for clarifications if needed.

P.S. All fractions are shown reduced to their minimal terms. This
behaviour, as all the rest for the sake, can be changed in the source
code... for this one there is a flag at least...

-LV

On 28 Aug, 04:58, galathaea <galath...@gmail.com> wrote:
> On Aug 27, 7:36 pm, ju...@diegidio.name wrote:
> > On 28 Aug, 03:27, Mariano Suárez-Alvarez
> > <mariano.suarezalva...@gmail.com> wrote:
>
> > > It would not hurt you to read up a bit on
> > > the convergence of series...
>
> > I second that.
>
> > Good night, Mariano.
>
> sounds like a great topic
>
> in particular
> * there is a well-known theorem in this theory
> which states
>
> * * * * * * * * * * * * * * * * oo
> * * * * * * * * * * * * * * * *---
> * * * * * * * * * * * * * * * *\
> * if the terms a of the series / * (-1) a
> * * * * * * * * j * * * * * * *--- * * * j
> * * * * * * * * * * * * * * * *j=0
>
> * * converge monotonically to 0
> * then the series converges

I take you mean (-1)^j here.

> this is even true constructively
>
> basically
> * this is because the error of the jth partial sum
> is bounded by the jth term
> (the >= order implies positive differences)
>
> the limit is bounded to a closed interval
>
> ;&e:
>
> > ^^$@:
> > > Suppose we look for the first place '9' appears in pi, then
> > > '99', '999', '9999', '999999', *'9999999', *etc.
> > > first '9': *3.14159 : *position number 5
> > > first '99': position number 44
> > > first '999': position 762 counting from
> > > * * * * * * * the first digit after the decimal point.
> > > " *" *'9999': *762
> > > --- *'99999': *762
> > > --- *'999999' : 762
> > > --- *'9999999': *position 1,722,776
> > > and so on
> > > source:http://www.angio.net/pi/bigpi.cgi
> > > now we form the series:
> > > 1/sqrt(5) *- *1/sqrt(44) *+ 1/sqrt(762) - 1/sqrt(762) + 1/sqrt(762)
> > > *- 1/sqrt(762) + 1/sqrt(1722776) *- *.. + .........
> > > It's a good bet that this alternating series converges, but
> > > no one has been able to prove it. *Too little is known about the
> > > pseudo-randomness quality of the digits of pi.
> > I'm afraid I still don't get it. Aren't the terms of that sum
> > obviously decreasing, so that our sum surely can be approximated
> > within the bounds of any given epsilon, provided that we just consider
> > enough terms?
>
> so the challenge is to prove that the terms
>
> * * * * * *1
> * a *= *-------
> * *j * *'\/ p
> * * * * * * *j
>
> * p *= the 1st location * * * * * * * * * * ~~
> * *j * * in _decimal_representation_ of pi (||)
> * * * *of the finite _decimal_representation_
> * * * * *of * * * j
> * * * * * * * * 10 *- 1
>
> satisfy the conditions necessary
> for a convergent alternating series
>
> it's clear that if position j has a string of k '9's
> then for all j < k
>
> * p *< p
> * *j = *k
>
> because even if j '9's have not yet occurred
> * they are inherent in the larger string
>
> conditional existence is proven
>
> if p *exists
> * * k
>
> * p *exists
> * *j
>
> but the actual proof of the existence of any such term
> * is not handled by such methods
> (what if 23 '9's never show up in the expansion of pi?)
>
> so
> * much of the trick in this challenge
> is in proving this existence question
>
> this is a question on infinite string representations
> with given finite substrings
>
> the key problem is:
> * describe the collection of substrings S of some
> * * (most likely finitely specified)
> * infinite string L
>
> can such a description be made recursive?
>
> there are many easy theorems about the rationals
>
> only certain repeating patterns are available
> * so the space of substrings can be quite constrained
>
> (the infinite singly repeated symbol
> * *giving a minimax constraint of (1/10)^n
> of all substrings of length n
> (ie. 1)
>
> length and complexity of patterns can be measured
> * using these properties of rationals repeating representations
>
> but the questions get much harder
> * when irrationals are looked at
>
> what coverage does a given irrational do?
> even that simple question
> * becomes difficult

Mine is not an answer, but still my construction I'd say "strongly
suggests" that irrational expansions *must* cover all possible
combinations of digits, that's the only chance, at least for
computable numbers. Surely just a very rough idea by now, but I could
try to elaborate a little bit.

> and pi is transcendental
>
> does that mean anything here?

Good question! I for one have no idea. What's the bearing on Turing
Machines?

> but
> * bringing back the topic
> after this long meander
>
> pi is representable by the series
>
> * * oo
> * *---
> * *\ * * * *j * * 1
> 4 */ * *(-1) * ------
> * *--- * * * * 2j + 1
> * *j=0
>
> (which
> * due to an illness of late
> *i must kindly point is a multisection
> *of an even more famous series)
>
> does this representation
> * have anything to say about the challenge at hand?

I'm the student here, so I'll say: that's the proof!

-LV

On Aug 27, 5:57 pm, ju...@diegidio.name wrote:
> On 27 Aug, 12:15, Alan Smaill <sma...@SPAMinf.ed.ac.uk> wrote:
>
>
>
> > ju...@diegidio.name writes:
>
> > > This comment of yours is interesting. For as much as I
> > > think of it, I can't see what more really could be said even if we
> > > take the (computable) irrationals into account. So a direct question
> > > comes to mind: what would you or anyone think is really needed to show
> > > that we have in fact "exhausted the computables"? A bit more properly:
> > > how to show we have them and all of them already, and that such domain
> > > we have defined is in fact closed to all operations? (We need "formal
> > > proof", in the constructive sense though! So really a chain of
> > > definitions. Still how to "validate" all this?)
>
> > or even, how to verify it?
>
> > yes, you should try to come up with a proof;
> > there are standard definitions out there of computable real,
> > just prove that you have got all of them.
>
> Could you please be a little bit more specific maybe?
>
> Take the presentation on Wikipedia:
>
> << In the following, Minsky defines the numbers to be computed in a
> manner similar to those defined by Alan Turing in 1936, i.e. as
> "sequences of digits interpreted as decimal fractions" between 0 and
> 1:
>
> "A computable number [is] one for which there is a Turing machine
> which, given n on its initial tape, terminates with the nth digit of
> that number [encoded on its tape]." (Minsky 1967:159)
> The key notions in the definition are (1) that some n is specified at
> the start, (2) when the machine's internal counter reaches this n the
> computation terminates after printing the nth decimal digit on its
> tape -- otherwise it would continue computing forever.
>
> An alternate form of (2) -- the machine successively prints all n
> of the digits on its tape, halting after printing the nth --
> emphasizes Minsky's observation: (3) That by use of a Turing machine,
> a finite definition -- in the form of the machine's TABLE -- is being
> used to define what is a potentially-infinite string of decimal
> digits. >>
>
> First a remark: we have here a machine that ***halts per
> definition***! Non-halting machines seem to just be out of the
> picture. Then, to me, these definitions do not touch the real
> problems: we seem to have our TM_1 and TM_2 someway together here, and
> still no TM_3 at all.
>
> Overall, I must confirm there is something I find deeply
> unsatisfactory about the whole of this "mainstream" mathematics. For
> instance read Smullyan on the incompleteness theorems[*], and Cantor
> is there too, at the very beginning, to say that there is more sets of
> natural numbers than predicates (more precisely: not every set of
> numbers is expressible in the language). And still, just few
> paragraphs later, we are told: we let g be a 1-1 function which assign
> to each expression E a natural number g(E) called the Goedel number of
> E... Assuming now that every number n is the Goedel number of a unique
> expression... Just to say: there is something "smelling" very bad
> here.
>
> -LV
>
> [*} Raymond M. Smullyan, "Goedel's incompleteness therems", Oxford
> University Press, 1992

I'm still uncertain what your goal here is. If you merely wish to
define a set, so be it, there's no need for algorithms or proofs. If
you wish to prove some property, such as that your algorithm shows
that every real is computable, then it's not a definition. Certainly
you could define the set of computable reals as the numbers
approximable by the list your TM produces and then show that this
equals the set of reals, but, in that case, you may want to make these
two separate steps clear.
Note that by the usual definition of a real r being computable,
there should be a TM which given e.g. n, k, or e, produces a close
enough approximation of r. The TM is only given the parameter
specifying how good the approximation should be, it is not given r.
Obviously, you would accomplish nothing by baking a machine for r into
the TM. Furthermore, the approximation should, for example, be the
last number your TM produces, not at some unknown location in the
list.

On 28 Aug, 17:01, Cenny Wenner <CWen...@gmail.com> wrote:
>
> * I'm still uncertain what your goal here is. If you merely wish to
> define a set, so be it, there's no need for algorithms or proofs. If
> you wish to prove some property, such as that your algorithm shows
> that every real is computable, then it's not a definition.

And that is not what I am trying to show either, that does not even
make very much sense, does it, as it amounts to denying tout court the
existence of non-computable numbers, an issue that is actually maybe
now under discussion.

Again, I have been talking *computables* only, and uncomputables have
simply been *out of the picture*. Something has been said about
uncomputables later in the discussion, but nothing of it has been yet
incorporated into the construction, which at the moment only deals
with finite representations (it covers gthe whole finite induction
actually): that is, essentially, the TM_3 from an example we have
discussed.

> Certainly
> you could define the set of computable reals as the numbers
> approximable by the list your TM produces and then show that this
> equals the set of reals, but, in that case, you may want to make these
> two separate steps clear.

That is not what I am trying. The set of the "reals" without further
qualification is simply out of the picture as far as the given
construction is concerned. Such statements of yours do not indeed even
make very much sense at all! BTW, have you had a look at the code yet?
There you'll find all the relevant inductive definitions.

> * Note that by the usual definition of a real r being computable,
> there should be a TM which given e.g. n, k, or e, produces a close
> enough approximation of r.

And that is what we already have. So the computable reals are there,
and that's all I am really saying: the *computable* reals *are* there,
as that operation is indeed possible and well defined in my
construction.

> The TM is only given the parameter
> specifying how good the approximation should be, it is not given r.

Ah, that is a delicate point here: *who* gives r?

> Obviously, you would accomplish nothing by baking a machine for r into
> the TM. Furthermore, the approximation should, for example, be the
> last number your TM produces, not at some unknown location in the
> list.

All those details are irrelevant to the generality of the argument.
The point here remains: "who" gives r? That's the issue now, or at
least a way to say it.

-LV

In article
<6b0d38f9-3171-4c59-bd5b-1613852a0449@k7g2000hsd.googlegroups.com>,
julio@diegidio.name wrote:

> On 28 Aug, 04:58, galathaea <galath...@gmail.com> wrote:
> > On Aug 27, 7:36 pm, ju...@diegidio.name wrote:

> > * there is a well-known theorem in this theory
> > which states
> >
> > * * * * * * * * * * * * * * * * oo
> > * * * * * * * * * * * * * * * *---
> > * * * * * * * * * * * * * * * *\
> > * if the terms a of the series / * (-1) a
> > * * * * * * * * j * * * * * * *--- * * * j
> > * * * * * * * * * * * * * * * *j=0
> >
> > * * converge monotonically to 0
> > * then the series converges
>
> I take you mean (-1)^j here.

I take it you both mean something like terms of (-1)^j * |a_j|.
Note: the absolute value may be omitted when the a_j terms are all of
the same sign, and the sequence is "eventually monotone" (for all but
finitely many terms |a_[j+1}| <= |a_j|) and converges to zero.

julio@diegidio.name writes:

> On 28 Aug, 17:01, Cenny Wenner <CWen...@gmail.com> wrote:
>>
>> Â* I'm still uncertain what your goal here is. If you merely wish to
>> define a set, so be it, there's no need for algorithms or proofs. If
>> you wish to prove some property, such as that your algorithm shows
>> that every real is computable, then it's not a definition.
>
> And that is not what I am trying to show either, that does not even
> make very much sense, does it, as it amounts to denying tout court the
> existence of non-computable numbers, an issue that is actually maybe
> now under discussion.
>
> Again, I have been talking *computables* only, and uncomputables have
> simply been *out of the picture*. Something has been said about
> uncomputables later in the discussion, but nothing of it has been yet
> incorporated into the construction, which at the moment only deals
> with finite representations (it covers gthe whole finite induction
> actually): that is, essentially, the TM_3 from an example we have
> discussed.

The presentation had no TMs at all so I have to leave this as simply a
comment about something else. The first place TM_1, TM_2 and TM_3
appeared, TM_1 and TM_2 seemed to define a computable real using a
variation on the normal definition (the variation does not affect the
result -- your computable reals are Turning's own). But TM_3 was not
well specified. Can you say what it does? It is possible it does not
exist.

>> Certainly
>> you could define the set of computable reals as the numbers
>> approximable by the list your TM produces and then show that this
>> equals the set of reals, but, in that case, you may want to make these
>> two separate steps clear.
>
> That is not what I am trying. The set of the "reals" without further
> qualification is simply out of the picture as far as the given
> construction is concerned. Such statements of yours do not indeed even
> make very much sense at all! BTW, have you had a look at the code yet?
> There you'll find all the relevant inductive definitions.

OK...

>> Â* Note that by the usual definition of a real r being computable,
>> there should be a TM which given e.g. n, k, or e, produces a close
>> enough approximation of r.
>
> And that is what we already have. So the computable reals are there,
> and that's all I am really saying: the *computable* reals *are* there,
> as that operation is indeed possible and well defined in my
> construction.

There are not there. I have not seen a construction of anything but a
set or rational numbers. The talks of machines came later and I can't
see how it fits because the key part was not well defined.

>> The TM is only given the parameter
>> specifying how good the approximation should be, it is not given r.
>
> Ah, that is a delicate point here: *who* gives r?

What is delicate about it? There is a subtle point about defined and
undefined reals, but you can leave that out for the moment I would
say. Take an example: pi. Are you in doubt that it is computable?
Will it appear in your constructed list?

--
Ben.