Date: Mar 10, 2013 5:02 AM
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.
> 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
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
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