Dr. Aloisius Louie, one of my father's former PhD students from
Dalhousie University in Halifax, Nova Scotia, back in the late 1970's, early
1980's, has gotten back to me with his analysis of the mathematical question
Boris had several days ago. Here are his comments:
Here below is my answer to Boris's question. You may
just
cut-and-paste the following and post it onto Tim's
list.
> Boris wrote: But then,
and here I come to my
point, Rosen says "We thus end up with a
> countable family of distinct
programs, each of which is a distinct word
> of finite length on a
finite alphabet : this is clearly impossible".
> This is where I don't
understand. Consider for instance the sequence
> of all binary programs
(binary sequences) ordered in lexicographic order
>
(0<1<00<01<10<10<000<001<010<010<011<100<....)
: this is a countable
> family of distinct programs, each of which is a
distinct word of finite
> length on a finite alphabet. So it seems
possible to have such a family.
> Am I mistaking? If not, we loose the
property that the category C(N) of
> all models of a mechanism has a
largest model, and we loose the property
> that if N is a mechanism
then analytic and synthetic coincide in C(N)
> (conclusion 4, p.205,
section 8B).
>
> What do you think?
>
Boris
>
[This is Section 8C of Life Itself that Boris is
asking about.]
The important thing to remember is that a Turing machine
must halt after
a FINITE number of steps. So Rosen's argument was
that this model M,
which is strictly larger than any of the Mi, was forced
to have a
program that was an INFINITE set (all the Mi programs).
This was the
part that was "clearly impossible": M cannot be a Turing
machine AND
have an infinite set as its program at the same time.
In
other words, what Rosen said in the book was NOT that it was
impossible to
have "a countable family of distinct programs, each of
which is a distinct
word of finite length on a finite alphabet". The
sequence of all
ordered binary programs {0, 1, 00, 01, 10, 11, 000, 001,
010, 011, 100,...}
in Boris's example was such a family. What Rosen
meant was that it
was impossible for an infinite set to be (the
representation of) a Turing
machine.
Dr. Aloisius Louie
I was rather pleased that his analysis is very similar to my own
because Aloisius' math chops are formidable! I hope this helps folks on the
list, and especially Boris?
Cheers,
Judith