Date: Mar 10, 2013 5:02 AM
Author: mueckenh@rz.fh-augsburg.de
Subject: Re: Matheology § 222 Back to the roots

On 9 Mrz., 23:53, William Hughes <wpihug...@gmail.com> wrote:
> On Mar 9, 5:57 pm, WM <mueck...@rz.fh-augsburg.de> wrote:
>

> > What do you understand by the not changeable function (d)?
>
> If x is a potentially infinite sequence of 0's and 1's
> then we say (x) is associated to x, if (x) is an algorithm
> which given a natural number produces a finite string
> of 0's and 1's, such that for every natural number n,
> (x) produces the nth FIS of x.


Ok. So it is clear that a finite number has to be given and a finite
string is produced.
>
> We will say x is coFIS to (y) iff
>
>      i.  We have (x) associated to x and
>          (y) associated to y
>
>      ii.  For every n, (x) and (y) produce the same
>           finite string.


"Every given n" is tantamount to "there is a last given n".
This maximum is the same for line l_max and max FIS of d.
>
> Some comments.
>
> We can never have more than a limited number of the strings
> produced by (x) existing at any time, since we can never
> have more that a limited number of natural numbers.


Correct.
>
> We cannot show that x is coFIS to (y) by using (x)
> and (y) to produce "all possible strings" and
> comparing them, since "all possible natural numbers"
> does not exist.  However, we may be able to use induction
> to show "For every n, (x) and (y) produce the same finite
> string"


Induction is fine, but also restricted to the (variable) maximum.
>
> To show that x is coFIS to (y), it is not enough
> to show that  every existing FIS of x, is equal to an
> existing FIS of y.


More cannot be shown.
>
> d, the diagonal of the list L, is a potentially infinite
> sequence of 0's and 1's with associated (d):
> for any natural number n produce
> a sequence of n ones.


This sequence is identical to a line l_max of the list L, by
construction of d_max.
>
> l_k, the k_th line of L is a potentially infinite
> sequence of 0's and 1' with associated (l_k):
> for any natural number n produce a sequence
> of k 1's followed by a sequence of n-k 0's
>
> A line of L, l_k is findable iff the index
> k is findable.
>
> Do you agree with the statement
>
>              There does not exist
>              (in the sense of not findable)
>              a natural number m such that
>              the mth line of L is coFIS to
>              (d)


No. The construction of (d) implies that for every d_k there is a line
l_k = d_1, ..., d_k, hence for every d_max there is a line l_max.

For reference, the list L is given by

1
1,2
1,2,3
...

Regards, WM