Uncomputable numbers are all in your head
|-|erc
and a natural index for every possible program.
real_n <=> UTM(n:N)
e.g. UTM(5) is the 5th number
UTM(100) is the 100th number.
To calculate the digits of the numbers give an input parameter DIGIT
to the number-program, and convert the output into MOD 10.
UTM(n)(digit) mod 10
e.g. say the 1000th number happens to be pi/10, then
UTM(1000) (1) mod 10 = 3
UTM(1000) (2) mod 10 = 1
UTM(1000) (3) mod 10 = 4
The mod 10 is not required but it ensures digits output are from 0 - 9, and makes the
set of programs much richer in real numbers.
How does Cantors proof hold up against such a definition of numbers?
UTM(n)(digit) mod 10 n=1,2,3....
sugggests a listing of all the reals so we can use that for the proof.
To construct the antidiagonal, we take the UTM index that equals the digits index.
UTM(digit)(digit) mod 10 is the diagonal.
UTM(digit)(digit)+1 mod 10 is an antidiagonal.
But for the antidiagonal to be a valid real number, it must be composed
of a UTM# and a natural number. Let it occur at index a.
UTM(a)(digit) mod 10 = antidiagonal
UTM(a)(digit) mod 10 = UTM(digit)(digit)+1 mod 10
when digit = a
UTM(digit)(digit) mod 10 = UTM(digit)(digit)+1 mod 10
0 = 1
contradiction
Therefore, the antidiagonal is not definable, GIVEN THE DEFINITION OF
REAL NUMBER THAT WE ARE USING.
Therefore we have a consise system of numbers where there are only
countable infinity many.
#similary for computing antidiag with a different UTM.
Herc
--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Rupert
|-|erc wrote:
> Define a real number as the output of a program, we can use a Universal Turing Machine
> and a natural index for every possible program.
>
> real_n <=> UTM(n:N)
>
> e.g. UTM(5) is the 5th number
> UTM(100) is the 100th number.
>
> To calculate the digits of the numbers give an input parameter DIGIT
> to the number-program, and convert the output into MOD 10.
>
> UTM(n)(digit) mod 10
>
> e.g. say the 1000th number happens to be pi/10, then
> UTM(1000) (1) mod 10 = 3
> UTM(1000) (2) mod 10 = 1
> UTM(1000) (3) mod 10 = 4
>
> The mod 10 is not required but it ensures digits output are from 0 - 9, and makes the
> set of programs much richer in real numbers.
>
> How does Cantors proof hold up against such a definition of numbers?
>
Perfectly well. If you require that reals be computable you should
require that bijections be computable as well. Then Cantor's proof
shows that there is no effective enumeration of the set of computable
numbers.
|-|erc
> |-|erc wrote:
> > Define a real number as the output of a program, we can use a Universal Turing Machine
> > and a natural index for every possible program.
> >
> > real_n <=> UTM(n:N)
> >
> > e.g. UTM(5) is the 5th number
> > UTM(100) is the 100th number.
> >
> > To calculate the digits of the numbers give an input parameter DIGIT
> > to the number-program, and convert the output into MOD 10.
> >
> > UTM(n)(digit) mod 10
> >
> > e.g. say the 1000th number happens to be pi/10, then
> > UTM(1000) (1) mod 10 = 3
> > UTM(1000) (2) mod 10 = 1
> > UTM(1000) (3) mod 10 = 4
> >
> > The mod 10 is not required but it ensures digits output are from 0 - 9, and makes the
> > set of programs much richer in real numbers.
> >
> > How does Cantors proof hold up against such a definition of numbers?
> >
>
> Perfectly well. If you require that reals be computable you should
> require that bijections be computable as well. Then Cantor's proof
> shows that there is no effective enumeration of the set of computable
> numbers.
How so?
Herc
Rupert
Let f(m,n) be a total recursive function in two variables whose range
is contained in the set of decimal digits. If we think of the function
n->f(m,n) as a computable sequence of digits, then f may be viewed as
an effective enumeration of a set of such sequences. (We may get a
repetition of the same sequence, but we don't need to worry about
that). There is an effective procedure for constructing a computable
sequence which differs from the sequence n->f(m,n) for all m. Just
construct the anti-diagonal number. This is guaranteed to be computable
since f is total recursive.
Here is another version of the argument using a different notion of an
effective enumeration of a set of computable reals.
Take some enumeration of the intervals with rational endpoints. Let's
define a computable real to be a total recursive function g, such that
g(n) is the number of an interval with rational endpoints with length
less than 1/n, and such that whenever m<n, the interval corresponding
to g(n) is contained in the interval corresponding to g(m). And an
effective enumeration of a set of computable numbers is a total
recursive function f such that f(n) is the number of a Turing machine
which computes the total recursive function corresponding to a
computable real, and such that f(m) and f(n) correspond to distinct
computable reals when m is not equal to n. Given an effective
enumeration of a set of computable reals, there is an effective
procedure for constructing a computable real not in the set enumerated.
Let h(n) be the number of an interval with length less than 1/n which
is contained in the intervals corresponding to h(m) for m<n, and which
is disjoint from one of the intervals corresponding to g(k) for some k,
where g is the comuptable number corresponding to f(n). h is total
recursive, and it corresponds to a computable real not in the set
enumerated.
David Bernier
> Define a real number as the output of a program, we can use a Universal Turing Machine
> and a natural index for every possible program.
>
> real_n <=> UTM(n:N)
>
> e.g. UTM(5) is the 5th number
> UTM(100) is the 100th number.
>
> To calculate the digits of the numbers give an input parameter DIGIT
> to the number-program, and convert the output into MOD 10.
>
> UTM(n)(digit) mod 10
>
> e.g. say the 1000th number happens to be pi/10, then
> UTM(1000) (1) mod 10 = 3
> UTM(1000) (2) mod 10 = 1
> UTM(1000) (3) mod 10 = 4
I think 1000 is the input to the UTM
[representing a program]. From the initial state,
then the UTM will continue computing step by step until it
halts (if ever). Is the DIGIT parameter the step number, or is
it something else?
David Bernier
fishfry
"|-|erc" <h@r.c> wrote:
> Define a real number as the output of a program,
If I define a real number as a tunafish sandwich, then a real number
contains mayo. But the conventional definition of a real number is not a
tunafish sandwich, and it's not the output of a program.
guenther vonKnakspot
fishfry wrote:
> In article <45938fb8$0$97257$892e...@authen.yellow.readfreenews.net>,
> "|-|erc" <h@r.c> wrote:
>
> > Define a real number as the output of a program,
>
> If I define a real number as a tunafish sandwich, then a real number
> contains mayo.
> But the conventional definition of a real number is not a
> tunafish sandwich, and it's not the output of a program.
porky_...@my-deja.com
> > But the conventional definition of a real number is not a
> > tunafish sandwich, and it's not the output of a program.
> I wonder wether _|erc has the ability to understand that.
He doesn't and he'll never have one.
His world is deterministic digital (or descrete, if you wish)
computers. Probably he won't even understand the notion of 'analog
computer'.
Unfortunately, he's not the only one. Many computer science students
are put on a strict diet of descrete math, and even if things like
'differentiation and integration' is include in cirriculum, it is
presented from the perspective of something that must be implement as a
code (executable on digital computer, of course). Then those folks grow
up, become professors of computer science and teach the same thing.
Ignorance breeds ignorance.
Newberry
Do you mean that n is on the vertical exis and m is on the horizontal
axis?
then f may be viewed as
> an effective enumeration of a set of such sequences. (We may get a
> repetition of the same sequence, but we don't need to worry about
> that). There is an effective procedure for constructing a computable
> sequence which differs from the sequence n->f(m,n) for all m. Just
> construct the anti-diagonal number. This is guaranteed to be computable
> since f is total recursive.
What if you enumerate the f(m,n) in a lexicographic order? Then the
antidiagonal must be one of them.
Robert Maas, see http://tinyurl.com/uh3t
> Define a real number as the output of a program, ...
So by your definition "Hello There!" is a "real number"? Instead of
re-defining ordinary mathematical jargon words to mean something
totally different from their ordinary meaning, why don't you make
up your own jargon words and define *them* instead? That would
result in a lot less confusion. Why not define a "proout" as the
output of a program? That would be easy for us to remember.
|-|erc
How about a generic term, indexed_reals?
An indexed real comprises a UTM and a natural index
which goes on the input tape to the UTM.
Now do we all get to the part where the antidiagonal is not an
indexed real?
Herc
|-|erc
Its the input on a 2nd tape. A UTM uses 2 tapes I think!
UTM(program_number) <=> TM_program_number
Now the TM requires an input. The input is which digit to calculate,
a natural number.
e.g. the 3rd digit of pi/10 is UTM(1000)(3) = 4
Herc
|-|erc
It may be computable, but its not indexable, so it doesn't qualify as an indexed real.
Cantors proof is invalid if you require that all reals are indexed by a UTM, the
antidiag isn't.
Herc
Rupert
Well, it doesn't really matter but let's do it that way, yes. So
n->f(m,n) is a row.
>
> then f may be viewed as
> > an effective enumeration of a set of such sequences. (We may get a
> > repetition of the same sequence, but we don't need to worry about
> > that). There is an effective procedure for constructing a computable
> > sequence which differs from the sequence n->f(m,n) for all m. Just
> > construct the anti-diagonal number. This is guaranteed to be computable
> > since f is total recursive.
>
> What if you enumerate the f(m,n) in a lexicographic order?
That's not an enumeration. It's not the same ordertype as the natural
numbers.
|-|erc
> fishfry wrote:
> > "|-|erc" <h@r.c> wrote:
> >
> > > Define a real number as the output of a program,
> >
> > If I define a real number as a tunafish sandwich, then a real number
> > contains mayo.
> And molten cheese, if it is a proper tuna melt.
> > But the conventional definition of a real number is not a
> > tunafish sandwich, and it's not the output of a program.
> I wonder wether _|erc has the ability to understand that.
A real number has to be enscribed somehow, computers are just a way
of automating that. I can define real any way I like as long as everything
else I write is consistent with that definition.
Herc
Rupert
It is if it's the antidiag for an effective enumeration. In that case,
there will be some Turing machine that computes it.
If you take the enumeration whereby n corresponds to the computable
real computed by Turing machine number n, that's not an effective
enumeration, because it's not decidable whether a given number actually
corresponds to a real. In that case the argument doesn't apply.
> Herc
The Ghost In The Machine
<h@r.c>
wrote
on Thu, 28 Dec 2006 19:37:57 +1000
<45938fb8$0$97257$892e...@authen.yellow.readfreenews.net>:
> Define a real number as the output of a program, we can use a Universal Turing Machine
> and a natural index for every possible program.
>
> real_n <=> UTM(n:N)
>
> e.g. UTM(5) is the 5th number
> UTM(100) is the 100th number.
[1] Not all machines halt.
[2] An indefinite number of machines can generate the same number.
>
> To calculate the digits of the numbers give an input parameter DIGIT
> to the number-program, and convert the output into MOD 10.
>
> UTM(n)(digit) mod 10
>
> e.g. say the 1000th number happens to be pi/10, then
> UTM(1000) (1) mod 10 = 3
> UTM(1000) (2) mod 10 = 1
> UTM(1000) (3) mod 10 = 4
>
> The mod 10 is not required but it ensures digits output are from 0 - 9, and makes the
> set of programs much richer in real numbers.
You could just use the alphabet SPACE,0,1,...,9.
>
> How does Cantors proof hold up against such a definition of numbers?
>
> UTM(n)(digit) mod 10 n=1,2,3....
> sugggests a listing of all the reals so we can use that for the proof.
>
> To construct the antidiagonal, we take the UTM index that equals the digits index.
> UTM(digit)(digit) mod 10 is the diagonal.
> UTM(digit)(digit)+1 mod 10 is an antidiagonal.
>
> But for the antidiagonal to be a valid real number, it must be composed
> of a UTM# and a natural number. Let it occur at index a.
> UTM(a)(digit) mod 10 = antidiagonal
> UTM(a)(digit) mod 10 = UTM(digit)(digit)+1 mod 10
> when digit = a
> UTM(digit)(digit) mod 10 = UTM(digit)(digit)+1 mod 10
> 0 = 1
> contradiction
>
> Therefore, the antidiagonal is not definable, GIVEN THE DEFINITION OF
> REAL NUMBER THAT WE ARE USING.
>
> Therefore we have a consise system of numbers where there are only
> countable infinity many.
Very true. Congratulations. Now had there actually been a *point* in
doing so I for one would have been more impressed.
As it is, all IEEE754 numbers (with the possible exception
of Inf and Nan) are in fact rational, of the form M * 2^n,
where M and n are integers.
>
> #similary for computing antidiag with a different UTM.
>
> Herc
--
#191, ewi...@earthlink.net
Useless C++ Programming Idea #8830129:
std::set<...> v; for(..:iterator i = v.begin(); i != v.end(); i++)
if(*i == thing) {...}
--
Posted via a free Usenet account from http://www.teranews.com
David Bernier
It's possible to define enhanced Turing machines, ETMs,
by using, say, 10 tapes glued at the edges. The 1st tape
from the top could be input1, the second from top input2,
the 3rd input3, the 4th through 9th would be used as
a scratch pad, and the 10th tape from the top would be
for the output. The ETM's program would be in the
state transition diagram or table.
Also, as The Ghost in the Machine said, a larger alphabet
such as the numerals 0 to 9 plus Space can also be useful.
These enhancements can perhaps make it easier to see what
can be done with Turing-type devices.
I guess uncomputable things are nonsense to you.
Suppose somebody writes down a Turing machine table on paper,
and calls it "Test_machine". Do you believe that
either Test_machine halts, or else Test_machine
goes on forever? (That makes one question per
value of Test_machine).
The law of the excluded middle (in some cases)
is rejected on philosophical or other grounds
by some mathematicians.
E.g.: Paul Cohen:
``The notion of a set is too vague for the
continuum hypothesis to have a positive
or negative answer."
cf.:
< http://www-history.mcs.st-andrews.ac.uk/Quotations/Cohen.html >
The quotation above is corroborated by the abstract
of a talk Cohen gave at a symposium on the occasion
of the centenary of Godel's birth.
see the last paragraph of the abstract at:
< http://www.logic.at/goedel2006/abstract.php?cohen >
David Bernier
|-|erc
> I guess uncomputable things are nonsense to you.
uncomputable functions are OK, uncomputable numbers is a misnomer.
>
> Suppose somebody writes down a Turing machine table on paper,
> and calls it "Test_machine". Do you believe that
> either Test_machine halts, or else Test_machine
> goes on forever? (That makes one question per
> value of Test_machine).
No. Either test machine [halts] or it [hasn't halted yet] are the only
2 observable values. [Goes forever] is a third value that may be
calculated in some instances. To say it either halts or it doesn't
requires some kind of oracle.
Herc
|-|erc
If a TM computes the antidiagonal, call it TM_a, then there must exist some number a,
UTM(a) = TM_a. Are you saying TM_a exists because there is no a where UTM(a)
computes the antidiagonal.
Herc
Rupert
The antidiagonal for what?
The antidiagonal for an effective enumeration is computable. That shows
that an effective enumeration cannot include every computable real.
As I said, if you let the n-th real in the list be the one computed by
the Turing machine with number n, that's not an effective enumeration,
because not every Turing machine computes a real, and it's not a
computable matter to decide which do and which don't.
Newberry
Why not?
Rupert
There are various issues that can be got around by changing the
definition of "Turing machine". But the one issue that can't be got
around is that not every Turing machine halts.
Newberry
It does not need to. "3.14" is a real number just as
"3.140000000000........"
Rupert
The problem is that there's no effective way of deciding whether the
Turing machine is going to go on forever without producing another
digit or whether it will eventually produce another digit. So the point
stands, it is not an effective enumeration.
Newberry
OK, let's say it is not an "effective enumeration." But the Turing
machine will either halt or not. If it does not halt we get "3.14", if
it does halt we get "3.140000...." (Some of them will produce the
actual pi.) In any case all the Turing machines will produce nothing
but real numbers. Whether it halts or not, whatever it will produce
will be a real number.
The antidiagonal will not be computable because at some point it will
get stuck and stop producing digits. That is, there is no Turing
machine that will produce the anti-diagonal. I think this is what Herc
was trying to demonstrate.
Rupert
That's right, there is an enumeration, not an effective one, and the
anti-diagonal for it is not computable. If that is Herc's claim then I
agree with him. My point that there is no effective enumeration of the
computable reals still stands. If you believe in non-effective
enumerations of the computable reals then you should also believe in
non-computable reals.
Newberry
Non-effective enumeration means that some reals will be represented by
finite strings. A non-computable real means that no algorithm for its
computation exists.
Case in point is the scenario above. There is no algorithm that will
compute the anti-diagonal. (An attempt to compute it will result in an
infinite loop and thus in a finite string that will not be different
from all the strings in the list.) By definition no algorithm exists to
compute infinite, incompressible strings that carry infinite amount of
information.
In any case it does not matter. You can require that the function be
total. Then you will find out that the reals are not r.e. OK. But the
computable reals are still countable. You make a list indexed by
integers and the anti-diagonal is not copmutable. Again, I believe this
,or something to that effect, was Herc's point.
David Bernier
[...]
> In any case it does not matter. You can require that the function be
> total. Then you will find out that the reals are not r.e. OK. But the
> computable reals are still countable. You make a list indexed by
> integers and the anti-diagonal is not copmutable. Again, I believe this
> ,or something to that effect, was Herc's point.
[...]
Right, the computable reals are countable. For most mathematicians,
meaning those not familiar with constructive mathematics, logic or
possibly other specialized areas, doing basic real analysis
(rigorous calculus, and more) while trying to avoid having theorems
saying that non-computable reals exist, is really very hard (I think).
Also, pure existence proofs are quite common in the usual way
real or complex analysis are done. For example,
any real-valued continuous function on the interval [0,1] is
bounded and has a maximum [also minimum] value
that are attained at one or more points in the interval.
But the proof of that (say by using topological properties of
the real numbers) doesn't give any idea about how to
go about computing the maximum value or where it
is reached in a specific instance of some specified
continuous function.
There are also existence proofs for solutions to
differential equations, and so on.
In the 1800's, Fourier used trigonometrical series to
solve partial differential equations.
Cauchy did a huge amount of work in real and complex analysis,
and Cauchy sequences are named after him.
Dedekind defined the real numbers as what are called
Dedekind-cuts of the rationals.
I read somewhere that Cantor studied trigonometrical series
before his seminal work in set theory. I think I read that
Cantor was led to study ordinals [or well ordered sets?]
from his studies of trigonometrical series.
I'd be interested to know if that's indeed the case, and
what the connection was.
David Bernier
Newberry
David Bernier wrote:
> Newberry wrote:
> [...]
>
> > In any case it does not matter. You can require that the function be
> > total. Then you will find out that the reals are not r.e. OK. But the
> > computable reals are still countable. You make a list indexed by
> > integers and the anti-diagonal is not copmutable. Again, I believe this
> > ,or something to that effect, was Herc's point.
> [...]
>
> Right, the computable reals are countable. For most mathematicians,
> meaning those not familiar with constructive mathematics, logic or
> possibly other specialized areas, doing basic real analysis
> (rigorous calculus, and more) while trying to avoid having theorems
> saying that non-computable reals exist, is really very hard (I think).
How about just dropping Zermelo's comprehension axiom?
>
> Also, pure existence proofs are quite common in the usual way
> real or complex analysis are done. For example,
> any real-valued continuous function on the interval [0,1] is
> bounded and has a maximum [also minimum] value
> that are attained at one or more points in the interval.
>
> But the proof of that (say by using topological properties of
> the real numbers) doesn't give any idea about how to
> go about computing the maximum value or where it
> is reached in a specific instance of some specified
> continuous function.
>
> There are also existence proofs for solutions to
> differential equations, and so on.
I guess there are two kinds of existence. a) existence in Cantor's
sense by showing a non-existence of a mapping, b) existence of a
computable entity. If there is a proof of existence we need to know if
it is type a) or b). b) means that a solution can be found but has not
been found yet. a) means that there is no solution i.e. it "exists" but
we can never find it. ZFC creates confusion.
>
> In the 1800's, Fourier used trigonometrical series to
> solve partial differential equations.
>
> Cauchy did a huge amount of work in real and complex analysis,
> and Cauchy sequences are named after him.
>
> Dedekind defined the real numbers as what are called
> Dedekind-cuts of the rationals.
>
> I read somewhere that Cantor studied trigonometrical series
> before his seminal work in set theory. I think I read that
> Cantor was led to study ordinals [or well ordered sets?]
> from his studies of trigonometrical series.
> I'd be interested to know if that's indeed the case, and
> what the connection was.
Some people claim that he was motivated by religion or rather by his
own religious views. His motivation is kind of an interesting side
note, but not really that relevant. The real issue is if Cantor-Zermelo
theory is justifiable, not how they arrived at it.
>
> David Bernier
Rupert
Well, my point is that if you only believe in computable reals you
should also only believe in computable bijections, in which case you
should still accept Cantor's theorem.
Newberry
Yes, I do believe only in computable reals. That includes all the
rational numbers, plus pi, e, the solutions of all algebraic equations
and much more. That is enough for me.
How does the belief in computable bijection imply the belief in
Cantor's theorem? Which part of the theorem? That the anti-diagonal is
not on the list or that the anti-diagonal exists?
Rupert
Cantor's argument proves that there is no effective enumeration of the
computable reals.
The Ghost In The Machine
<rupertm...@yahoo.com>
wrote
on 31 Dec 2006 18:41:42 -0800
<1167619302....@h40g2000cwb.googlegroups.com>:
[snip to address this point]
> Cantor's argument proves that there is no effective enumeration of the
> computable reals.
Pedant point: argument(S). Apparently there are two proofs, one using
a sequencing arrangement and the much more famous one using digits.
(Kinda neat, that. It means those who actually argue for
the reals' denumerability can get hit by both proofs. :-) )
>
>> >
>> > > >
>> > > > > > > > > > and it's not a
>> > > > > > > > > > computable matter to decide which do and which don't.
>
--
#191, ewi...@earthlink.net
Warning: This encrypted signature is a dangerous
munition. Please notify the US government
immediately upon reception.
0000 0000 0000 0000 0001 0000 0000 0000 ...
Newberry
I accept it. But I accept that the anti-diagonal exists only if it is
computable. If you list all the computable reals then the anti-diagonal
is not computable, and effective enumeration is not required to
establish this.
David Bernier
[...]
> I accept it. But I accept that the anti-diagonal exists only if it is
> computable. If you list all the computable reals then the anti-diagonal
> is not computable, and effective enumeration is not required to
> establish this.
[...]
I think I've understood the point that Rupert is trying to explain.
So, to get to the point, I'll just ask a couple of questions
addressed to you:
(1) Does there exist a sequence r_1, r_2, r_3, ....
of the computable reals such that every computable real
appears once and only once in the sequence?
(2) If yes, why so and
if not, why not?
Regards,
David Bernier
Rupert
Please pay attention. There is no effective enumeration of the
computable reals. Given an effective enumeration of some of the
computable reals, the anti-diagonal exists, is computable, and is not
in the set enumerated. If you list all the computable reals, that is
not an effective enumeration. (And, as you correctly point out, the
anti-diagonal is not computable). You are welcome to believe only in
computable reals if you want. But if so then you should also believe
only in effective enumerations, so you shouldn't talk about the
possibility of listing all the computable reals. That's not a
possibility in your world.
Newberry
Why so?
so you shouldn't talk about the
> possibility of listing all the computable reals. That's not a
> possibility in your world.
Maybe not. But I do not need it as I am not attempting the diagonal
argument.
There is a list of modified Turing machines, which output every symbol
they write on the tape. You can order tem lexicographically and by the
input. (I think Herc was attempting a similar construct a little
differently.) They will compute all the reals. Many of them will get
stuck in infinite loops but so what? There are no more reals than those
computed by the machines in the list. The anti-diagonal is not
computable. There is an universal machine somewhere in the list that
will try to emulate all the other machines in the list and add 1 mod b.
It will be on line i. When it comes to computing the i-th digit of the
diagonal it will call itself and go into an infinite regression.
Newberry
Why so?
so you shouldn't talk about the
> possibility of listing all the computable reals. That's not a
> possibility in your world.
Maybe not. But I do not need it as I am not attempting the diagonal
argument.
There is a list of modified Turing machines, which output every symbol
they write on the tape. You can order tem lexicographically and by the
input. (I think Herc was attempting a similar construct a little
differently.) They will compute all the reals. Many of them will get
stuck in infinite loops but so what? There are no more reals than those
computed by the machines in the list. The anti-diagonal is not
computable. There is an universal machine somewhere in the list that
will try to emulate all the other machines in the list and add 1 mod b.
It will be on line i. When it comes to computing the i-th digit of the
diagonal it will call itself and go into an infinite regression.
>
> > >
> > > > >
> > > > > > >
Rupert
Well, I can't think of a justification for refusing to accept
non-computable reals that wouldn't also entail not accepting
non-effective enumerations. They're pretty much the same kind of thing.
Maybe you've thought of such a justification. Please tell me all about
it.
> so you shouldn't talk about the
> > possibility of listing all the computable reals. That's not a
> > possibility in your world.
>
> Maybe not. But I do not need it as I am not attempting the diagonal
> argument.
>
> There is a list of modified Turing machines, which output every symbol
> they write on the tape. You can order tem lexicographically and by the
> input. (I think Herc was attempting a similar construct a little
> differently.) They will compute all the reals. Many of them will get
> stuck in infinite loops but so what? There are no more reals than those
> computed by the machines in the list. The anti-diagonal is not
> computable. There is an universal machine somewhere in the list that
> will try to emulate all the other machines in the list and add 1 mod b.
> It will be on line i. When it comes to computing the i-th digit of the
> diagonal it will call itself and go into an infinite regression.
>
If you only believe in computable reals, I don't think you should say
"There are only countably many reals" unless you can find an effective
enumeration of the computable reals. As Cantor's argument proves, there
is no such enumeration.
Newberry
I simply don't see why the machines absolutely have to terminate.
>
> > so you shouldn't talk about the
> > > possibility of listing all the computable reals. That's not a
> > > possibility in your world.
> >
> > Maybe not. But I do not need it as I am not attempting the diagonal
> > argument.
> >
> > There is a list of modified Turing machines, which output every symbol
> > they write on the tape. You can order tem lexicographically and by the
> > input. (I think Herc was attempting a similar construct a little
> > differently.) They will compute all the reals. Many of them will get
> > stuck in infinite loops but so what? There are no more reals than those
> > computed by the machines in the list. The anti-diagonal is not
> > computable. There is an universal machine somewhere in the list that
> > will try to emulate all the other machines in the list and add 1 mod b.
> > It will be on line i. When it comes to computing the i-th digit of the
> > diagonal it will call itself and go into an infinite regression.
> >
>
> If you only believe in computable reals, I don't think you should say
> "There are only countably many reals" unless you can find an effective
> enumeration of the computable reals. As Cantor's argument proves, there
> is no such enumeration.
I think you have it all backwards. As I have shown above the diagonal
argument does not go through if you restrict yourself to computable
reals. The totality of the function is required for the argument to go
through. It serves no other purpose.
Newberry
I got the idea from people smarter than myself:
Ok, but a "list of all computable real numbers" is not computable.
That
is, the list is countable, but it is not recursively enumerable.
--
Dave Seaman
"How to copmute pi"
http://groups.google.com/group/sci.logic/browse_frm/thread/988adb6e245aa3d4/f31f4b1796682494?hl=en#f31f4b1796682494
Rupert
If you require your reals to be computable, you should also require
your enumerations to be effective. And in that case the argument works
fine.
Rupert
I know. And if you refuse to accept the existence of non-computable
reals then I don't think you have the right to say that anything which
is not recursively enumerable is countable.
|-|erc
The only semi-practical way to enumerate reals is with a Universal Turing Machine.
real_n <=> UTM(n:N)
e.g. UTM(5) is the 5th number (the digits output by the 5th constructed Turing Machine).
UTM(100) is the 100th number
Since some programs won't halt this isn't effective, but from a constructionists P.O.V.
it iterates every real and is good enough. For diagonalisation to take place one must
look at partial constructions of the number grid, we can use an 11th digit for 'not halted yet'.
If we restrict the Universe of Discourse to a single default Universal Turing Machine, then
the antidiagonal is not computable and hence Cantor's argument proves nothing against
the claim that the reals are countable.
Herc
Newberry
I do not see the connection. All the the Turing machines are countable
and so are their inputs N. Effective enumeration is the range of one of
them.
> And in that case the argument works
> fine.
Are you suggesting that there is some contradiction in recognizing only
countable reals? Hardly. You only need to drop the axiom of extent or
the the power set axiom and the diagonal argument will not go through.
And since you believe that ZFC is consistent then a weaker system is
even more consistent.
And not knowing which Turing machine will halt how can you specify a
total function?
|-|erc
> There is a list of modified Turing machines, which output every symbol
> they write on the tape. You can order tem lexicographically and by the
> input. (I think Herc was attempting a similar construct a little
> differently.) They will compute all the reals. Many of them will get
> stuck in infinite loops but so what? There are no more reals than those
> computed by the machines in the list. The anti-diagonal is not
> computable. There is an universal machine somewhere in the list that
> will try to emulate all the other machines in the list and add 1 mod b.
> It will be on line i. When it comes to computing the i-th digit of the
> diagonal it will call itself and go into an infinite regression.
>
This is the same way I am using but instead of ordering Turing Machines
I use a Universal Turing Machine and call UTM(1) the 1st Turing Machine,
UTM(2) the 2nd Turing Machine and so on.
The problem I come to that you seem to have avoided, is describing the computations
of the antidiagonal under a different UTM, eg. UTMb. UTMb(i) could compute
the antidiagonal and not appear anywhere on the original UTM list. So the
problem is there is more than 1 way to list Turing Machines, and Cantorians
will compute the antidiagonal any way they can!
Herc
Rupert
Not every Turing machine computes a real in the sense this is usually
defined, and there is no effective way to determine when this is the
case and when it isn't. You can modify the definition so that every
Turing machine computes a real, but then you will have the phenomenon
that there will be no effective procedure for determining the n-th
digit of the m-th real. Thus this is not an effective enumeration, and
if you don't believe in non-computable reals you shouldn't really
regard it as an "enumeration of the computable reals".
> e.g. UTM(5) is the 5th number (the digits output by the 5th constructed Turing Machine).
> UTM(100) is the 100th number
>
> Since some programs won't halt this isn't effective, but from a constructionists P.O.V.
> it iterates every real and is good enough.
I think if non-computable reals aren't allowed, non-effective
enumerations shouldn't be allowed either.
> For diagonalisation to take place one must
> look at partial constructions of the number grid, we can use an 11th digit for 'not halted yet'.
>
> If we restrict the Universe of Discourse to a single default Universal Turing Machine, then
> the antidiagonal is not computable and hence Cantor's argument proves nothing against
> the claim that the reals are countable.
>
Cantor's argument is perfectly good. It proves that the reals are
uncountable, and it proves that the computable reals are not
effectively countable. It's true that the computable reals are
(non-effectively) countable, but this cannot be plausibly held to be a
reasonable interpretation of the statement "the reals are countable".
> Herc
|-|erc
> > > If you require your reals to be computable, you should also require
> > > your enumerations to be effective. And in that case the argument works
> > > fine.
> > >
> >
> > The only semi-practical way to enumerate reals is with a Universal Turing Machine.
> >
> > real_n <=> UTM(n:N)
> >
>
> Not every Turing machine computes a real in the sense this is usually
> defined, and there is no effective way to determine when this is the
> case and when it isn't. You can modify the definition so that every
> Turing machine computes a real, but then you will have the phenomenon
> that there will be no effective procedure for determining the n-th
> digit of the m-th real. Thus this is not an effective enumeration, and
> if you don't believe in non-computable reals you shouldn't really
> regard it as an "enumeration of the computable reals".
>
> > e.g. UTM(5) is the 5th number (the digits output by the 5th constructed Turing Machine).
> > UTM(100) is the 100th number
> >
> > Since some programs won't halt this isn't effective, but from a constructionists P.O.V.
> > it iterates every real and is good enough.
>
> I think if non-computable reals aren't allowed, non-effective
> enumerations shouldn't be allowed either.
What is the connection between computability and effectiveness here?
They seem independent yet you keep stressing this dependency. Why
aren't non-effective enumerations allowed, allowed into what, and what
has this got to do with restricting the class to computable reals.
>
> > For diagonalisation to take place one must
> > look at partial constructions of the number grid, we can use an 11th digit for 'not halted yet'.
> >
> > If we restrict the Universe of Discourse to a single default Universal Turing Machine, then
> > the antidiagonal is not computable and hence Cantor's argument proves nothing against
> > the claim that the reals are countable.
> >
>
> Cantor's argument is perfectly good. It proves that the reals are
> uncountable, and it proves that the computable reals are not
> effectively countable. It's true that the computable reals are
> (non-effectively) countable, but this cannot be plausibly held to be a
> reasonable interpretation of the statement "the reals are countable".
I don't think you've listened on the numerous times Newberry and I have said
the antidiagonal is not computable, (with certain restrictions).
Herc
Rupert
|-|erc wrote:
> "Rupert" <rupertm...@yahoo.com> wrote
> > > > If you require your reals to be computable, you should also require
> > > > your enumerations to be effective. And in that case the argument works
> > > > fine.
> > > >
> > >
> > > The only semi-practical way to enumerate reals is with a Universal Turing Machine.
> > >
> > > real_n <=> UTM(n:N)
> > >
> >
> > Not every Turing machine computes a real in the sense this is usually
> > defined, and there is no effective way to determine when this is the
> > case and when it isn't. You can modify the definition so that every
> > Turing machine computes a real, but then you will have the phenomenon
> > that there will be no effective procedure for determining the n-th
> > digit of the m-th real. Thus this is not an effective enumeration, and
> > if you don't believe in non-computable reals you shouldn't really
> > regard it as an "enumeration of the computable reals".
> >
> > > e.g. UTM(5) is the 5th number (the digits output by the 5th constructed Turing Machine).
> > > UTM(100) is the 100th number
> > >
> > > Since some programs won't halt this isn't effective, but from a constructionists P.O.V.
> > > it iterates every real and is good enough.
> >
> > I think if non-computable reals aren't allowed, non-effective
> > enumerations shouldn't be allowed either.
>
> What is the connection between computability and effectiveness here?
I believe I gave a definition of "effective enumeration" earlier. That
should make the connection clear.
> They seem independent
Not at all.
> yet you keep stressing this dependency. Why
> aren't non-effective enumerations allowed,
They are, but I can't think of any good reason for not allowing
non-computable reals that wouldn't also be a reason for not allowing
non-effective enumerations. They are pretty much the same kind of
thing.
> allowed into what, and what
> has this got to do with restricting the class to computable reals.
>
I'm sorry you can't see the connection. An enumeration of the reals can
itself be coded as a real. This real will be computable if and only if
the enumeration is an effective enumeration of the computable reals. If
you don't allow non-computable reals, I don't see the justification for
allowing non-effective enumerations. They are the same kind of thing.
> >
> > > For diagonalisation to take place one must
> > > look at partial constructions of the number grid, we can use an 11th digit for 'not halted yet'.
> > >
> > > If we restrict the Universe of Discourse to a single default Universal Turing Machine, then
> > > the antidiagonal is not computable and hence Cantor's argument proves nothing against
> > > the claim that the reals are countable.
> > >
> >
> > Cantor's argument is perfectly good. It proves that the reals are
> > uncountable, and it proves that the computable reals are not
> > effectively countable. It's true that the computable reals are
> > (non-effectively) countable, but this cannot be plausibly held to be a
> > reasonable interpretation of the statement "the reals are countable".
>
> I don't think you've listened on the numerous times Newberry and I have said
> the antidiagonal is not computable, (with certain restrictions).
>
Well, your comprehension skills aren't very good then. I know the
antidiagonal for the enumeration of the reals you're talking about
isn't computable. That's because it's not an effective enumeration.
This has no relevance to the points I made.
> Herc
Rupert
And a non-effective enumeration isn't. And I can't think of any good
reason for rejecting non-computable reals which wouldn't also be a
reason for rejecting non-effective enumerations. They are pretty much
the same kind of thing. An enumeration of the reals can be coded by a
real, and the real will be computable if and only if the enumeration is
an effective enumeration of a subset of the computable reals. If you
don't believe in non-computable reals, you shouldn't believe in any
enumerations that aren't effective enumerations of a subset of the
computable reals.
> > And in that case the argument works
> > fine.
>
> Are you suggesting that there is some contradiction in recognizing only
> countable reals?
No, "countable reals" doesn't mean anything. If you substitute
"computable reals", I suggested no such thing.
> Hardly. You only need to drop the axiom of extent
There is no axiom of extent.
> or
> the the power set axiom and the diagonal argument will not go through.
Yes, it will, it will show that there is no countable set containing
all the reals.
> And since you believe that ZFC is consistent then a weaker system is
> even more consistent.
>
There are subtheories of ZFC in which the diagonal argument doesn't go
through. That is no objection to the diagonal argument. Your job is to
find a consistent theory in which the reals are countable (which
necessarily won't be a subtheory of ZFC), and convince me that I should
accept this theory. I expect you could do the former, but I doubt you
can do the latter.
> And not knowing which Turing machine will halt how can you specify a
> total function?
>
Don't understand this point.
|-|erc
So you are just being silly then. Dissallowing noncomputable reals is at the
heart of constructionism, where mathematical objects must attain a certain
level of reality before we wildly accept phantoms like hyperinfinities.
>
> > allowed into what, and what
> > has this got to do with restricting the class to computable reals.
> >
>
> I'm sorry you can't see the connection. An enumeration of the reals can
> itself be coded as a real. This real will be computable if and only if
> the enumeration is an effective enumeration of the computable reals. If
> you don't allow non-computable reals, I don't see the justification for
> allowing non-effective enumerations. They are the same kind of thing.
In what ways are they they same kind of thing. You are being silly. We don't
allow non computable reals INTO THE SET R. This is clearly defined.
Not allowing non-effective enumerations is just in your head, it means nothing.
>
> > >
> > > > For diagonalisation to take place one must
> > > > look at partial constructions of the number grid, we can use an 11th digit for 'not halted yet'.
> > > >
> > > > If we restrict the Universe of Discourse to a single default Universal Turing Machine, then
> > > > the antidiagonal is not computable and hence Cantor's argument proves nothing against
> > > > the claim that the reals are countable.
> > > >
> > >
> > > Cantor's argument is perfectly good. It proves that the reals are
> > > uncountable, and it proves that the computable reals are not
> > > effectively countable. It's true that the computable reals are
> > > (non-effectively) countable, but this cannot be plausibly held to be a
> > > reasonable interpretation of the statement "the reals are countable".
> >
> > I don't think you've listened on the numerous times Newberry and I have said
> > the antidiagonal is not computable, (with certain restrictions).
> >
>
> Well, your comprehension skills aren't very good then. I know the
> antidiagonal for the enumeration of the reals you're talking about
> isn't computable. That's because it's not an effective enumeration.
> This has no relevance to the points I made.
Then how can you keep using the diagonal argument? I have already outlined
a technique for diagonalising a partial population of the number grid, it
doesn't matter if some digits are not finished computing yet or never will.
Herc
|-|erc
> > I don't think you've listened on the numerous times Newberry and I have said
> > the antidiagonal is not computable, (with certain restrictions).
> >
>
> Well, your comprehension skills aren't very good then. I know the
> antidiagonal for the enumeration of the reals you're talking about
> isn't computable. That's because it's not an effective enumeration.
> This has no relevance to the points I made.
>
No it's not because it's not an effective enumeration, it's because (if you
listened you would know) you can't construct a computer program to
compute the antidiagonal as the computer program appears on some
line of the enumeration of reals, and creates a conflict.
Herc
Rupert
No, I'm not being silly. You haven't addressed my point in the
slightest, you evince no understanding of it whatsoever. If you're
going to talk about the real number comptued by the n-th Turing
machine, you have to specify what to do when the Turing machine doesn't
halt. If you come up with some scheme whereby every Turing machine
represents a real number, then the function mapping n to the real
number computed by the n-th Turing machine will be a non-effective
enumeration: the real which codes for it will be a non-computable real.
If you don't believe in non-computable reals, you shouldn't believe in
the existence of the enumeration.
>
> >
> > > allowed into what, and what
> > > has this got to do with restricting the class to computable reals.
> > >
> >
> > I'm sorry you can't see the connection. An enumeration of the reals can
> > itself be coded as a real. This real will be computable if and only if
> > the enumeration is an effective enumeration of the computable reals. If
> > you don't allow non-computable reals, I don't see the justification for
> > allowing non-effective enumerations. They are the same kind of thing.
>
> In what ways are they they same kind of thing.
I explained that. An enumeration can be coded for by a real. You should
only accept the existence of the enumeration if you accept the
existence of the real which codes for it.
> You are being silly. We don't
> allow non computable reals INTO THE SET R. This is clearly defined.
> Not allowing non-effective enumerations is just in your head, it means nothing.
>
I'm afraid you don't know what you're talking about.
>
> >
> > > >
> > > > > For diagonalisation to take place one must
> > > > > look at partial constructions of the number grid, we can use an 11th digit for 'not halted yet'.
> > > > >
> > > > > If we restrict the Universe of Discourse to a single default Universal Turing Machine, then
> > > > > the antidiagonal is not computable and hence Cantor's argument proves nothing against
> > > > > the claim that the reals are countable.
> > > > >
> > > >
> > > > Cantor's argument is perfectly good. It proves that the reals are
> > > > uncountable, and it proves that the computable reals are not
> > > > effectively countable. It's true that the computable reals are
> > > > (non-effectively) countable, but this cannot be plausibly held to be a
> > > > reasonable interpretation of the statement "the reals are countable".
> > >
> > > I don't think you've listened on the numerous times Newberry and I have said
> > > the antidiagonal is not computable, (with certain restrictions).
> > >
> >
> > Well, your comprehension skills aren't very good then. I know the
> > antidiagonal for the enumeration of the reals you're talking about
> > isn't computable. That's because it's not an effective enumeration.
> > This has no relevance to the points I made.
>
> Then how can you keep using the diagonal argument? I have already outlined
> a technique for diagonalising a partial population of the number grid, it
> doesn't matter if some digits are not finished computing yet or never will.
>
Let me cut and paste what I wrote above.
> > > > Cantor's argument is perfectly good. It proves that the reals are
> > > > uncountable, and it proves that the computable reals are not
> > > > effectively countable. It's true that the computable reals are
> > > > (non-effectively) countable, but this cannot be plausibly held to be a
> > > > reasonable interpretation of the statement "the reals are countable".
> > >
I really don't know how to make it any clearer.
> Herc
Rupert
The reason why that is the case is because it's not an effective
enumeration. It's really not a good idea to try to be patronizing when
the person you're talking to understands the subject a lot better than
you do.
> Herc
Newberry
My guess is that your method will come to the same. The UTM will call
itself with the same parameter and go into an infinite recursion.
This is the heart of the matter the diagonal is not computable because
the machines will never halt. Rupert somehow turned the argument on its
head.
>
> Herc
Rupert
All that matters is that we are clear about what claims are being made.
The real numbers are uncountable. The computable numbers are not
effectively countable. They are non-effectively countable. What I am
questioning is whether "the computable numbers are non-effectively
countable" is a reasonable interpretation for "the real numbers are
countable". I don't see how to justify such an interpretation, for
reasons I've repeated several times now which you people seem to be
having trouble understanding.
> >
> > Herc
|-|erc
> No, I'm not being silly. You haven't addressed my point in the
> slightest, you evince no understanding of it whatsoever. If you're
> going to talk about the real number comptued by the n-th Turing
> machine, you have to specify what to do when the Turing machine doesn't
> halt. If you come up with some scheme whereby every Turing machine
> represents a real number, then the function mapping n to the real
> number computed by the n-th Turing machine will be a non-effective
> enumeration: the real which codes for it will be a non-computable real.
> If you don't believe in non-computable reals, you shouldn't believe in
> the existence of the enumeration.
OK, what is 'the real which codes for it'?
The list of reals is hypothetical, the best we can achieve is some list after
t processing cycles, so there will be null values for digits. There is a difference
between returning a null value and noncomputability.
Herc
Rupert
|-|erc wrote:
> "Rupert" <rupertm...@yahoo.com> wrote >
> > No, I'm not being silly. You haven't addressed my point in the
> > slightest, you evince no understanding of it whatsoever. If you're
> > going to talk about the real number comptued by the n-th Turing
> > machine, you have to specify what to do when the Turing machine doesn't
> > halt. If you come up with some scheme whereby every Turing machine
> > represents a real number, then the function mapping n to the real
> > number computed by the n-th Turing machine will be a non-effective
> > enumeration: the real which codes for it will be a non-computable real.
> > If you don't believe in non-computable reals, you shouldn't believe in
> > the existence of the enumeration.
>
> OK, what is 'the real which codes for it'?
>
The coding system is trivial. If you really can't come up with one
yourself you need to learn more mathematical logic.
> The list of reals is hypothetical, the best we can achieve is some list after
> t processing cycles, so there will be null values for digits. There is a difference
> between returning a null value and noncomputability.
>
So what justifies you in saying there is a list of all reals,
especially since some Turing machines will never halt?
> Herc
|-|erc
>
> |-|erc wrote:
> > "Rupert" <rupertm...@yahoo.com> wrote >
> > > No, I'm not being silly. You haven't addressed my point in the
> > > slightest, you evince no understanding of it whatsoever. If you're
> > > going to talk about the real number comptued by the n-th Turing
> > > machine, you have to specify what to do when the Turing machine doesn't
> > > halt. If you come up with some scheme whereby every Turing machine
> > > represents a real number, then the function mapping n to the real
> > > number computed by the n-th Turing machine will be a non-effective
> > > enumeration: the real which codes for it will be a non-computable real.
> > > If you don't believe in non-computable reals, you shouldn't believe in
> > > the existence of the enumeration.
> >
> > OK, what is 'the real which codes for it'?
> >
>
> The coding system is trivial. If you really can't come up with one
> yourself you need to learn more mathematical logic.
does anyone else know what Rupert is talking about?
>
> > The list of reals is hypothetical, the best we can achieve is some list after
> > t processing cycles, so there will be null values for digits. There is a difference
> > between returning a null value and noncomputability.
> >
>
> So what justifies you in saying there is a list of all reals,
> especially since some Turing machines will never halt?
the old Cantorian excuse, BUT IT WONT HALT!
Herc
|-|erc
Yes, this is my argument in the OP
UTM(digit)(digit) mod 10 = UTM(digit)(digit)+1 mod 10
0 = 1
>
> This is the heart of the matter the diagonal is not computable because
> the machines will never halt. Rupert somehow turned the argument on its
> head.
Rupert has yet to acknowledge this argument, he seems oblivious to this fault
of diagonalistion since some machines won't halt anyway.
Herc
Newberry
Is this an absolute thruth or a property of one particular axiomatic
system?
Rupert
What do you think counts as a "list of all reals"? How would you define
it?
Newberry
I think what you are trying to tell ma that you want the diagonal
argument to stand. For that you need a total function. Therefore I
should also accept the requirement that the function be total. But it
is a contrived case considering that for a given general recursive
function you cannot even tell if it is total or not.
Secondly procedures that are not total are still considered effective.
Case in point is my example of a list of modified Turing machines. It
does not matter one iota if any given machine will terminate or not
because in either case it will compute a real number. And there no more
computable real numbers than there are modified Turing machines.
>
> > > And in that case the argument works
> > > fine.
> >
> > Are you suggesting that there is some contradiction in recognizing only
> > countable reals?
>
> No, "countable reals" doesn't mean anything. If you substitute
> "computable reals", I suggested no such thing.
>
> > Hardly. You only need to drop the axiom of extent
>
> There is no axiom of extent.
I meant axiom of comprehension.
>
> > or
> > the the power set axiom and the diagonal argument will not go through.
>
> Yes, it will, it will show that there is no countable set containing
> all the reals.
No, it will not. If there is no power sat then you cannot show that it
is greater than N.
>
> > And since you believe that ZFC is consistent then a weaker system is
> > even more consistent.
> >
>
> There are subtheories of ZFC in which the diagonal argument doesn't go
> through. That is no objection to the diagonal argument. Your job is to
> find a consistent theory in which the reals are countable (which
> necessarily won't be a subtheory of ZFC), and convince me that I should
> accept this theory. I expect you could do the former, but I doubt you
> can do the latter.
I already told how to construct a consistent theory where the diagonal
argument will not go through. Drop the axiom of comprehension or drop
the power set axiom.
That of course is not entirely satisfactory theory. So I propose adding
the axiom: A class x is set only if x is definable. This will result in
proving that
B = {x e N| x ~e phi(x)}, phi:N --> P(N)
is not a set. After all B is just Russell's set in blue.
Rupert
Absolute truth in my view. But this isn't the issue I've been arguing
about, I've been willing to concede alternative views about this point
for the sake of argument.
Newberry
Then don't inject statements like "The real numbers are uncountable."
That precludes alternative views.
Aatu Koskensilta
> does anyone else know what Rupert is talking about?
Yes.
--
Aatu Koskensilta (aatu.kos...@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
Rupert
I'll say what I like and I don't really care whether you agree with it
or not unless you can come up with a coherent reason for thinking
otherwise. You want to re-interpret the statement "The real numbers are
countable" as the correct statement "The computable real numbers are
non-effectively countable". In my view that is distorting the meanings
of words beyond recognition. Just say "The computable real numbers are
non-effectively countable", then I'll agree with you.
There is nothing wrong with Cantor's proof and it works in many
different axiomatic frameworks. If you want to specify an axiomatic
framework which you like in which the argument doesn't go through, go
ahead.
Rupert
I don't think you should call it an enumeration of the reals if the
function is not total. Because I don't think a Turing machine really
computes a real if it won't ever tell you what the value of a
particular digit is. If we happen to know that the Turing machine
doesn't halt on this particular digit, then we can come up with a
different Turing machine which does halt on every digit and say "this
is the real that the first Turing machine computes". But there's no
effective procedure for coming up with such a Turing machine. You're
saying, take the list where the n-th real is the real computed by the
n-th Turing machine, where in the case where the Turing machine doesn't
halt for some particular digit you're appealling to the fact that we
can find another Turing machine which goes on producing zeroes forever
after the point where the first Turing machine doesn't halt. But this
is cheating, you're evading the fact that there's no effective
procedure for finding such a Turing machine. What you've got doesn't
deserve to be called an effective enumeration of all the reals, because
there's no effective procedure for finding the m-th digit of the n-th
real.
The diagonal argument does show that there can be no effective
enumeration of the set of all computable reals. What you've got, I
claim, should be called a non-effective enumeration. And since I can't
see any good reason to reject non-computable reals that doesn't also
lead to rejecting non-effective enumerations, I don't accept that
you've given me a reasonable stance which justifies the statement "The
reals are countable".
> Secondly procedures that are not total are still considered effective.
> Case in point is my example of a list of modified Turing machines. It
> does not matter one iota if any given machine will terminate or not
> because in either case it will compute a real number. And there no more
> computable real numbers than there are modified Turing machines.
>
You are not justified in saying the real numbes are countable from your
standpoint unless you can give an effective enumeration of the
computable reals, which gives an effective procedure for finding the
m-th digit of the n-th real. If the enumeration you've given is good
enough to be called an enumeration, why shouldn't I take the
anti-diagonal for it and say that's good enough to be called a real
number?
Whatever. It doesn't really matter. As long as you translate your claim
into my language I'll agree with you. Just say "The computable reals
are non-effectively countable." That's fine. I think that to paraphrase
this as "The real numbers are countable" is silly, that's what I object
to.
|-|erc
> |-|erc wrote:
> > does anyone else know what Rupert is talking about?
>
> Yes.
Looks like I was right, these uncomputable numbers are all in your head.
Herc
Rupert
I am not arguing against this point of view (though I don't think
you've offered any compelling reasons for accepting it). I am arguing
that if non-comuptable numbers are all in your head, then non-effective
enumerations should be in your head as well. I may explain the
connection in more detail later, but really, if you don't know this
stuff you're in over your head.
Newberry
Correct. That is what's wrong with the diagonal argument. The matrix
will in fact be full of holes. Some of them will be on the diagonal, so
the anti-diagonal is not computable.
>
> The diagonal argument does show that there can be no effective
> enumeration of the set of all computable reals. What you've got, I
> claim, should be called a non-effective enumeration.
It is still an enumeration.
> And since I can't
> see any good reason to reject non-computable reals that doesn't also
> lead to rejecting non-effective enumerations, I don't accept that
> you've given me a reasonable stance which justifies the statement "The
> reals are countable".
I will give you a couple of reasons:
1) What happens in infinity is beyond the realm not only of observable
but even imaginable phenomena. Hence any statements about infinity
(such as one infinity is greater than another) are meaningless.
2) Actual infinity (that is finished infinity) is a contradiction in
terms
3) Infinite, incompressible strings carrying infinite amount of
information cannot exist for reasons 1) and 2).
4) in a finite binary tree the ratio of edges to paths is (2*2^n -
2)/2^n. In an infinite tree the ratio is lim{n-->oo} (2*2^n - 2)/2^n =
2. It contradicts Cantor's result that the cardinality of the paths is
greater than the number of the edges.
5) The diagonal argument shows that for any matrix of size n there is a
string of size n that is not in the matrix. Yet for any n such a string
can be generated and added to the list. You could as well have counters
A and B with values v(B) and v(A) such that vhen v(A) = n then v(B) =
n+1. You could keep incrementing these counters till infinity and find
that for any n v(B) > v(A). Yet it would be absurd to argue that in
infinity B > A. But the Cantorists do precisely that arguing that they
can always find one more antidiagonal that is not on the list yet. When
you observe a dog chasing its tail you do not conclude that one
infinity is greater than another.
>
> > Secondly procedures that are not total are still considered effective.
> > Case in point is my example of a list of modified Turing machines. It
> > does not matter one iota if any given machine will terminate or not
> > because in either case it will compute a real number. And there no more
> > computable real numbers than there are modified Turing machines.
> >
>
> You are not justified in saying the real numbes are countable from your
> standpoint unless you can give an effective enumeration of the
> computable reals, which gives an effective procedure for finding the
> m-th digit of the n-th real.
You added this arbitrary condition to preserve the diagonal argument.
If the enumeration you've given is good
> enough to be called an enumeration, why shouldn't I take the
> anti-diagonal for it and say that's good enough to be called a real
> number?
Because the diagonal will have holes.
>
> Whatever. It doesn't really matter. As long as you translate your claim
> into my language I'll agree with you. Just say "The computable reals
> are non-effectively countable."
OK, they are not effectiveky countable.
That's fine. I think that to paraphrase
> this as "The real numbers are countable" is silly, that's what I object
> to.
"Countable" means the same cardinality as N.
Rupert
There's nothing wrong with the diagonal argument as long as you're
clear about what it purports to show. There is a non-effective
enumeration of the computable reals, yes, this in no way contradicts
the diagonal argument, and does not deserve to be paraphrased as "The
reals are countable". You're assuming the matrix with its holes in it
actually exists. There's no effective way of telling whether a given
entry in the matrix will have a hole in it or not, so to assume that
the matrix somehow "exists" as a determinate object is on a par with
assuming the existence of a non-computable real.
> >
> > The diagonal argument does show that there can be no effective
> > enumeration of the set of all computable reals. What you've got, I
> > claim, should be called a non-effective enumeration.
>
> It is still an enumeration.
>
> > And since I can't
> > see any good reason to reject non-computable reals that doesn't also
> > lead to rejecting non-effective enumerations, I don't accept that
> > you've given me a reasonable stance which justifies the statement "The
> > reals are countable".
>
> I will give you a couple of reasons:
> 1) What happens in infinity is beyond the realm not only of observable
> but even imaginable phenomena. Hence any statements about infinity
> (such as one infinity is greater than another) are meaningless.
Is the statement "The computable reals are not effectively countable"
meaningless?
> 2) Actual infinity (that is finished infinity) is a contradiction in
> terms
> 3) Infinite, incompressible strings carrying infinite amount of
> information cannot exist for reasons 1) and 2).
So why do you believe your enumeration, which you conceded was
non-effective, exists?
> 4) in a finite binary tree the ratio of edges to paths is (2*2^n -
> 2)/2^n. In an infinite tree the ratio is lim{n-->oo} (2*2^n - 2)/2^n =
> 2.
Wrong, in an infinite tree it's not defined.
> It contradicts Cantor's result that the cardinality of the paths is
> greater than the number of the edges.
> 5) The diagonal argument shows that for any matrix of size n there is a
> string of size n that is not in the matrix. Yet for any n such a string
> can be generated and added to the list. You could as well have counters
> A and B with values v(B) and v(A) such that vhen v(A) = n then v(B) =
> n+1. You could keep incrementing these counters till infinity and find
> that for any n v(B) > v(A). Yet it would be absurd to argue that in
> infinity B > A. But the Cantorists do precisely that arguing that they
> can always find one more antidiagonal that is not on the list yet.
We say that one infinite set is of larger size than another when the
latter can be injected into the former but not bijected onto the
former. Cantor proves this is the case for the set of real numbers and
the set of natural numbers.
> When
> you observe a dog chasing its tail you do not conclude that one
> infinity is greater than another.
>
> >
> > > Secondly procedures that are not total are still considered effective.
> > > Case in point is my example of a list of modified Turing machines. It
> > > does not matter one iota if any given machine will terminate or not
> > > because in either case it will compute a real number. And there no more
> > > computable real numbers than there are modified Turing machines.
> > >
> >
> > You are not justified in saying the real numbes are countable from your
> > standpoint unless you can give an effective enumeration of the
> > computable reals, which gives an effective procedure for finding the
> > m-th digit of the n-th real.
>
> You added this arbitrary condition to preserve the diagonal argument.
>
It's no more arbitrary than the requirement that reals be computable.
> If the enumeration you've given is good
> > enough to be called an enumeration, why shouldn't I take the
> > anti-diagonal for it and say that's good enough to be called a real
> > number?
>
> Because the diagonal will have holes.
>
When I objected to you that the enumeration will have holes, you said,
"Fine, get rid of the holes" without worrying about the fact that
there's no effective procedure for doing so. You still thought this was
a good enough reason to call it an enumeration. Why shouldn't I do the
same thing here and say that the anti-diagonal with the holes removed
deserves to be called a real, even though it's not computable?
> >
> > Whatever. It doesn't really matter. As long as you translate your claim
> > into my language I'll agree with you. Just say "The computable reals
> > are non-effectively countable."
>
> OK, they are not effectiveky countable.
>
Good. Also, there is nothing wrong with the diagonal argument, and you
cannot justify saying "The reals are countable" without twisting the
meanings of words in totally arbitrary ways.
> That's fine. I think that to paraphrase
> > this as "The real numbers are countable" is silly, that's what I object
> > to.
>
> "Countable" means the same cardinality as N.
>
And "same cardinality" means there exists a bijection. Why am I
supposed to accept the existence of the bijection but not the
anti-diagonal? It's not good enough to say the anti-diagonal will have
holes. You can only justify your claim that the bijection exists by
getting rid of the holes (in a necessarily non-effective way). So I
should be allowed to do the same with the anti-diagonal and say "Here
is a non-computable real number."
David Marcus
> 4) in a finite binary tree the ratio of edges to paths is (2*2^n -
> 2)/2^n. In an infinite tree the ratio is lim{n-->oo} (2*2^n - 2)/2^n =
> 2.
What is the meaning of the word "ratio" in the second sentence?
--
David Marcus
Newberry
Maybe not, but P(N) > N is.
>
> > 2) Actual infinity (that is finished infinity) is a contradiction in
> > terms
> > 3) Infinite, incompressible strings carrying infinite amount of
> > information cannot exist for reasons 1) and 2).
>
> So why do you believe your enumeration, which you conceded was
> non-effective, exists?
I never said I believed in any enumeration.
>
> > 4) in a finite binary tree the ratio of edges to paths is (2*2^n -
> > 2)/2^n. In an infinite tree the ratio is lim{n-->oo} (2*2^n - 2)/2^n =
> > 2.
>
> Wrong, in an infinite tree it's not defined.
Is it true that lim{n-->oo}(2*2^n - 2)/2^n = 2?
is it true that we indexed all the layers by integers? Is it true that
N is infinite?
>
> > It contradicts Cantor's result that the cardinality of the paths is
> > greater than the number of the edges.
> > 5) The diagonal argument shows that for any matrix of size n there is a
> > string of size n that is not in the matrix. Yet for any n such a string
> > can be generated and added to the list. You could as well have counters
> > A and B with values v(B) and v(A) such that vhen v(A) = n then v(B) =
> > n+1. You could keep incrementing these counters till infinity and find
> > that for any n v(B) > v(A). Yet it would be absurd to argue that in
> > infinity B > A. But the Cantorists do precisely that arguing that they
> > can always find one more antidiagonal that is not on the list yet.
>
> We say that one infinite set is of larger size than another when the
> latter can be injected into the former but not bijected onto the
> former. Cantor proves this is the case for the set of real numbers and
> the set of natural numbers.
You missed the point. I am saying that any time you find the
anti-diagonal I can put back on the list. What leads you to believe
that once we reach infinity there will be one outstanding anti-diagonal
left before I have a chance to put it in the list.
>
> > When
> > you observe a dog chasing its tail you do not conclude that one
> > infinity is greater than another.
> >
> > >
> > > > Secondly procedures that are not total are still considered effective.
> > > > Case in point is my example of a list of modified Turing machines. It
> > > > does not matter one iota if any given machine will terminate or not
> > > > because in either case it will compute a real number. And there no more
> > > > computable real numbers than there are modified Turing machines.
> > > >
> > >
> > > You are not justified in saying the real numbes are countable from your
> > > standpoint unless you can give an effective enumeration of the
> > > computable reals, which gives an effective procedure for finding the
> > > m-th digit of the n-th real.
> >
> > You added this arbitrary condition to preserve the diagonal argument.
> >
>
> It's no more arbitrary than the requirement that reals be computable.
>
> > If the enumeration you've given is good
> > > enough to be called an enumeration, why shouldn't I take the
> > > anti-diagonal for it and say that's good enough to be called a real
> > > number?
> >
> > Because the diagonal will have holes.
> >
>
> When I objected to you that the enumeration will have holes, you said,
> "Fine, get rid of the holes"
I do not recall saying this.
> without worrying about the fact that
> there's no effective procedure for doing so. You still thought this was
> a good enough reason to call it an enumeration. Why shouldn't I do the
> same thing here and say that the anti-diagonal with the holes removed
> deserves to be called a real, even though it's not computable?
>
> > >
> > > Whatever. It doesn't really matter. As long as you translate your claim
> > > into my language I'll agree with you. Just say "The computable reals
> > > are non-effectively countable."
> >
> > OK, they are not effectiveky countable.
> >
>
> Good. Also, there is nothing wrong with the diagonal argument, and you
> cannot justify saying "The reals are countable" without twisting the
> meanings of words in totally arbitrary ways.
>
> > That's fine. I think that to paraphrase
> > > this as "The real numbers are countable" is silly, that's what I object
> > > to.
> >
> > "Countable" means the same cardinality as N.
> >
>
> And "same cardinality" means there exists a bijection. Why am I
> supposed to accept the existence of the bijection but not the
> anti-diagonal?
I thought the anti-diagonal was supposed to prove that there was no
bijection.
It's not good enough to say the anti-diagonal will have
> holes. You can only justify your claim that the bijection exists by
> getting rid of the holes (in a necessarily non-effective way).
Obviously there is bijection between Turing machines and N, holes or
not.
> So I
> should be allowed to do the same with the anti-diagonal and say "Here
> is a non-computable real number."
What justifies saying that it exists?
Newberry
I cannot recapitulate all the elementary mathematics. There is no space
for it. But for n approaching infinity the limit converges and it
converges to 2.
>
> --
> David Marcus
David Marcus
> David Marcus wrote:
> > Newberry wrote:
> > > 4) in a finite binary tree the ratio of edges to paths is (2*2^n -
> > > 2)/2^n. In an infinite tree the ratio is lim{n-->oo} (2*2^n - 2)/2^n =
> > > 2.
> >
> > What is the meaning of the word "ratio" in the second sentence?
>
> I cannot recapitulate all the elementary mathematics. There is no space
> for it.
No idea what that means.
> But for n approaching infinity the limit converges and it
> converges to 2.
Yes, of course. However, you wrote "the ratio is...". My question is,
what does this limit have to do with the "ratio of edges to paths" in
the infinite tree? As far as I can see, the answer is nothing. So, your
example doesn't seem to have a point.
--
David Marcus
David Marcus
> Rupert wrote:
> > Newberry wrote:
> > > 4) in a finite binary tree the ratio of edges to paths is (2*2^n -
> > > 2)/2^n. In an infinite tree the ratio is lim{n-->oo} (2*2^n - 2)/2^n =
> > > 2.
> >
> > Wrong, in an infinite tree it's not defined.
>
> Is it true that lim{n-->oo}(2*2^n - 2)/2^n = 2?
Yes.
> is it true that we indexed all the layers by integers?
Yes.
> Is it true that N is infinite?
Yes.
Now, I'll ask you a question: How do you define "ratio of edges to paths
in the infinite tree"?
> > > It contradicts Cantor's result that the cardinality of the paths is
> > > greater than the number of the edges.
How so?
> > > 5) The diagonal argument shows that for any matrix of size n there is a
> > > string of size n that is not in the matrix. Yet for any n such a string
> > > can be generated and added to the list. You could as well have counters
> > > A and B with values v(B) and v(A) such that vhen v(A) = n then v(B) =
> > > n+1. You could keep incrementing these counters till infinity and find
> > > that for any n v(B) > v(A). Yet it would be absurd to argue that in
> > > infinity B > A. But the Cantorists do precisely that arguing that they
> > > can always find one more antidiagonal that is not on the list yet.
"Yet"? "Yet" has nothing to do with it. The list is given. Rhetorical
question: Why do people keep trying to put time into mathematics?
What does "in infinity" mean? If you mean a limit, then please say so.
If you mean something else, then say what you mean.
> > We say that one infinite set is of larger size than another when the
> > latter can be injected into the former but not bijected onto the
> > former. Cantor proves this is the case for the set of real numbers and
> > the set of natural numbers.
>
> You missed the point. I am saying that any time you find the
> anti-diagonal I can put back on the list. What leads you to believe
> that once we reach infinity there will be one outstanding anti-diagonal
> left before I have a chance to put it in the list.
What makes you think that "time", "once we reach infinity", "before I
have a chance" have any mathematical meaning?
Do you disagree that there is no surjection from the natural numbers to
the real numbers?
--
David Marcus
Newberry
David Marcus wrote:
> Newberry wrote:
> > David Marcus wrote:
> > > Newberry wrote:
> > > > 4) in a finite binary tree the ratio of edges to paths is (2*2^n -
> > > > 2)/2^n. In an infinite tree the ratio is lim{n-->oo} (2*2^n - 2)/2^n =
> > > > 2.
> > >
> > > What is the meaning of the word "ratio" in the second sentence?
> >
> > I cannot recapitulate all the elementary mathematics. There is no space
> > for it.
>
> No idea what that means.
>
> > But for n approaching infinity the limit converges and it
> > converges to 2.
>
> Yes, of course. However, you wrote "the ratio is...". My question is,
> what does this limit have to do with the "ratio of edges to paths" in
> the infinite tree?
We assign one integer to one layer of the tree. There are infinitely
many integers therefore we get an infinite tree.
Newberry
David Marcus wrote:
> Newberry wrote:
> > Rupert wrote:
> > > Newberry wrote:
>
> > > > 4) in a finite binary tree the ratio of edges to paths is (2*2^n -
> > > > 2)/2^n. In an infinite tree the ratio is lim{n-->oo} (2*2^n - 2)/2^n =
> > > > 2.
> > >
> > > Wrong, in an infinite tree it's not defined.
> >
> > Is it true that lim{n-->oo}(2*2^n - 2)/2^n = 2?
>
> Yes.
>
> > is it true that we indexed all the layers by integers?
>
> Yes.
>
> > Is it true that N is infinite?
>
> Yes.
>
> Now, I'll ask you a question: How do you define "ratio of edges to paths
> in the infinite tree"?
By calculating the limit edges to paths for n-->oo.
>
> > > > It contradicts Cantor's result that the cardinality of the paths is
> > > > greater than the number of the edges.
>
> How so?
lim{n-->oo} (2*2^n - 2)/2^n = 2 contradicts |#paths| > |#edges|
>
> > > > 5) The diagonal argument shows that for any matrix of size n there is a
> > > > string of size n that is not in the matrix. Yet for any n such a string
> > > > can be generated and added to the list. You could as well have counters
> > > > A and B with values v(B) and v(A) such that vhen v(A) = n then v(B) =
> > > > n+1. You could keep incrementing these counters till infinity and find
> > > > that for any n v(B) > v(A). Yet it would be absurd to argue that in
> > > > infinity B > A. But the Cantorists do precisely that arguing that they
> > > > can always find one more antidiagonal that is not on the list yet.
>
> "Yet"? "Yet" has nothing to do with it. The list is given. Rhetorical
> question: Why do people keep trying to put time into mathematics?
>
> What does "in infinity" mean? If you mean a limit, then please say so.
> If you mean something else, then say what you mean.
Of course it does not mean anything. That was my point.
>
> > > We say that one infinite set is of larger size than another when the
> > > latter can be injected into the former but not bijected onto the
> > > former. Cantor proves this is the case for the set of real numbers and
> > > the set of natural numbers.
> >
> > You missed the point. I am saying that any time you find the
> > anti-diagonal I can put back on the list. What leads you to believe
> > that once we reach infinity there will be one outstanding anti-diagonal
> > left before I have a chance to put it in the list.
>
> What makes you think that "time", "once we reach infinity", "before I
> have a chance" have any mathematical meaning?
That was my point. Actual infinity is nonsense.
David Marcus
>
> David Marcus wrote:
> > Newberry wrote:
> > > David Marcus wrote:
> > > > Newberry wrote:
> > > > > 4) in a finite binary tree the ratio of edges to paths is (2*2^n -
> > > > > 2)/2^n. In an infinite tree the ratio is lim{n-->oo} (2*2^n - 2)/2^n =
> > > > > 2.
> > > >
> > > > What is the meaning of the word "ratio" in the second sentence?
> > >
> > > I cannot recapitulate all the elementary mathematics. There is no space
> > > for it.
> >
> > No idea what that means.
> >
> > > But for n approaching infinity the limit converges and it
> > > converges to 2.
> >
> > Yes, of course. However, you wrote "the ratio is...". My question is,
> > what does this limit have to do with the "ratio of edges to paths" in
> > the infinite tree?
>
> We assign one integer to one layer of the tree. There are infinitely
> many integers therefore we get an infinite tree.
I don't think you answered my question. What does the limit you gave, or
the fact that the tree is infinite, have to do with the "ratio of edges
to paths" in the infinite tree?
If you don't like that question, then try this one: what does the limit
you gave have to do with the cardinality of edges and paths in the
infinite tree?
> > As far as I can see, the answer is nothing. So, your
Virgil
"Newberry" <newb...@ureach.com> wrote:
> David Marcus wrote:
> > Newberry wrote:
> > > David Marcus wrote:
> > > > Newberry wrote:
> > > > > 4) in a finite binary tree the ratio of edges to paths is (2*2^n -
> > > > > 2)/2^n. In an infinite tree the ratio is lim{n-->oo} (2*2^n - 2)/2^n =
> > > > > 2.
> > > >
> > > > What is the meaning of the word "ratio" in the second sentence?
> > >
> > > I cannot recapitulate all the elementary mathematics. There is no space
> > > for it.
> >
> > No idea what that means.
> >
> > > But for n approaching infinity the limit converges and it
> > > converges to 2.
> >
> > Yes, of course. However, you wrote "the ratio is...". My question is,
> > what does this limit have to do with the "ratio of edges to paths" in
> > the infinite tree?
>
> We assign one integer to one layer of the tree. There are infinitely
> many integers therefore we get an infinite tree.
But there is nothing in any finite tree or collection of finite trees
that to show what happens in an infinite tree.
It is clearly false to assume that everything that is true for finite
trees remains true for infinite trees, as that would mean that infinite
trees are finite.
David Marcus
> David Marcus wrote:
> > Newberry wrote:
> > > Rupert wrote:
> > > > Newberry wrote:
> >
> > Now, I'll ask you a question: How do you define "ratio of edges to paths
> > in the infinite tree"?
>
> By calculating the limit edges to paths for n-->oo.
You are welcome to do that, but then it isn't clear why this ratio has
anything to do with the cardinalities of paths and edges in the infinite
tree. Or, are you using WM's axiom that everything is continuous?
> > > > > It contradicts Cantor's result that the cardinality of the paths is
> > > > > greater than the number of the edges.
> >
> > How so?
>
> lim{n-->oo} (2*2^n - 2)/2^n = 2 contradicts |#paths| > |#edges|
What is the contradiction?
Do you really think there is a contradiction or are you trolling?
> > > > > 5) The diagonal argument shows that for any matrix of size n there is a
> > > > > string of size n that is not in the matrix. Yet for any n such a string
> > > > > can be generated and added to the list. You could as well have counters
> > > > > A and B with values v(B) and v(A) such that vhen v(A) = n then v(B) =
> > > > > n+1. You could keep incrementing these counters till infinity and find
> > > > > that for any n v(B) > v(A). Yet it would be absurd to argue that in
> > > > > infinity B > A. But the Cantorists do precisely that arguing that they
> > > > > can always find one more antidiagonal that is not on the list yet.
> >
> > "Yet"? "Yet" has nothing to do with it. The list is given. Rhetorical
> > question: Why do people keep trying to put time into mathematics?
> >
> > What does "in infinity" mean? If you mean a limit, then please say so.
> > If you mean something else, then say what you mean.
>
> Of course it does not mean anything. That was my point.
Your point was that you wrote something that doesn't mean anything?
> > > > We say that one infinite set is of larger size than another when the
> > > > latter can be injected into the former but not bijected onto the
> > > > former. Cantor proves this is the case for the set of real numbers and
> > > > the set of natural numbers.
> > >
> > > You missed the point. I am saying that any time you find the
> > > anti-diagonal I can put back on the list. What leads you to believe
> > > that once we reach infinity there will be one outstanding anti-diagonal
> > > left before I have a chance to put it in the list.
> >
> > What makes you think that "time", "once we reach infinity", "before I
> > have a chance" have any mathematical meaning?
>
> That was my point. Actual infinity is nonsense.
What is "actual infinity", why should we care whether it is nonsense,
and what does your "actual infinity" have to do with standard
mathematics?
Virgil
"Newberry" <newb...@ureach.com> wrote:
> David Marcus wrote:
> > Now, I'll ask you a question: How do you define "ratio of edges to paths
> > in the infinite tree"?
>
> By calculating the limit edges to paths for n-->oo.
That presumes that everything that holds for finite trees must hold for
infinite trees as well, which would require that infinite trees be
finite.
>
> >
> > > > > It contradicts Cantor's result that the cardinality of the paths is
> > > > > greater than the number of the edges.
> >
> > How so?
>
> lim{n-->oo} (2*2^n - 2)/2^n = 2 contradicts |#paths| > |#edges|
Not necessarily. It only does if one also supposes that
lim{n-->oo} (2*2^n - 2)/2^n = lim{n-->oo} (2*2^n - 2) / lim{n-->oo} 2^n
has some sort of meaning, but it doesn't.
David Marcus
It is interesting that people who think the infinite tree has more edges
than paths don't find this argument persuasive. It is hard not to think
that they reason backwards from their conclusions.
--
David Marcus
Virgil
David Marcus <David...@alumdotmit.edu> wrote:
I'm not even sure that I would call it "reasoning", at least in the
sense that mathemticians use the word.
Rupert
Why? It says there's an injection from N into P(N) and no bijection
from N onto P(N). Seems to me I understand it perfectly well.
> >
> > > 2) Actual infinity (that is finished infinity) is a contradiction in
> > > terms
> > > 3) Infinite, incompressible strings carrying infinite amount of
> > > information cannot exist for reasons 1) and 2).
> >
> > So why do you believe your enumeration, which you conceded was
> > non-effective, exists?
>
> I never said I believed in any enumeration.
>
Good. So presumably you won't claim that the reals are countable.
> >
> > > 4) in a finite binary tree the ratio of edges to paths is (2*2^n -
> > > 2)/2^n. In an infinite tree the ratio is lim{n-->oo} (2*2^n - 2)/2^n =
> > > 2.
> >
> > Wrong, in an infinite tree it's not defined.
>
> Is it true that lim{n-->oo}(2*2^n - 2)/2^n = 2?
Yes.
> is it true that we indexed all the layers by integers?
Don't understand this one. You seem to be missing my point.
> Is it true that
> N is infinite?
>
Yes.
> >
> > > It contradicts Cantor's result that the cardinality of the paths is
> > > greater than the number of the edges.
> > > 5) The diagonal argument shows that for any matrix of size n there is a
> > > string of size n that is not in the matrix. Yet for any n such a string
> > > can be generated and added to the list. You could as well have counters
> > > A and B with values v(B) and v(A) such that vhen v(A) = n then v(B) =
> > > n+1. You could keep incrementing these counters till infinity and find
> > > that for any n v(B) > v(A). Yet it would be absurd to argue that in
> > > infinity B > A. But the Cantorists do precisely that arguing that they
> > > can always find one more antidiagonal that is not on the list yet.
> >
> > We say that one infinite set is of larger size than another when the
> > latter can be injected into the former but not bijected onto the
> > former. Cantor proves this is the case for the set of real numbers and
> > the set of natural numbers.
>
> You missed the point. I am saying that any time you find the
> anti-diagonal I can put back on the list. What leads you to believe
> that once we reach infinity there will be one outstanding anti-diagonal
> left before I have a chance to put it in the list.
>
Given any countable set of real numbers, there is a real number not in
the set. That shows that the set of real numbers is not countable.
> >
> > > When
> > > you observe a dog chasing its tail you do not conclude that one
> > > infinity is greater than another.
> > >
> > > >
> > > > > Secondly procedures that are not total are still considered effective.
> > > > > Case in point is my example of a list of modified Turing machines. It
> > > > > does not matter one iota if any given machine will terminate or not
> > > > > because in either case it will compute a real number. And there no more
> > > > > computable real numbers than there are modified Turing machines.
> > > > >
> > > >
> > > > You are not justified in saying the real numbes are countable from your
> > > > standpoint unless you can give an effective enumeration of the
> > > > computable reals, which gives an effective procedure for finding the
> > > > m-th digit of the n-th real.
> > >
> > > You added this arbitrary condition to preserve the diagonal argument.
> > >
> >
> > It's no more arbitrary than the requirement that reals be computable.
> >
> > > If the enumeration you've given is good
> > > > enough to be called an enumeration, why shouldn't I take the
> > > > anti-diagonal for it and say that's good enough to be called a real
> > > > number?
> > >
> > > Because the diagonal will have holes.
> > >
> >
> > When I objected to you that the enumeration will have holes, you said,
> > "Fine, get rid of the holes"
>
> I do not recall saying this.
>
http://groups.google.com/group/sci.math/msg/1b67d0b41d39655c?dmode=source
> > without worrying about the fact that
> > there's no effective procedure for doing so. You still thought this was
> > a good enough reason to call it an enumeration. Why shouldn't I do the
> > same thing here and say that the anti-diagonal with the holes removed
> > deserves to be called a real, even though it's not computable?
> >
> > > >
> > > > Whatever. It doesn't really matter. As long as you translate your claim
> > > > into my language I'll agree with you. Just say "The computable reals
> > > > are non-effectively countable."
> > >
> > > OK, they are not effectiveky countable.
> > >
> >
> > Good. Also, there is nothing wrong with the diagonal argument, and you
> > cannot justify saying "The reals are countable" without twisting the
> > meanings of words in totally arbitrary ways.
> >
> > > That's fine. I think that to paraphrase
> > > > this as "The real numbers are countable" is silly, that's what I object
> > > > to.
> > >
> > > "Countable" means the same cardinality as N.
> > >
> >
> > And "same cardinality" means there exists a bijection. Why am I
> > supposed to accept the existence of the bijection but not the
> > anti-diagonal?
>
> I thought the anti-diagonal was supposed to prove that there was no
> bijection.
>
It does. You are telling me the enumeration exists but not the
anti-diagonal, therefore the enumeration is a bijection. I see no good
reason for accepting the existence of the enumeration but not the
anti-diagonal.
> It's not good enough to say the anti-diagonal will have
> > holes. You can only justify your claim that the bijection exists by
> > getting rid of the holes (in a necessarily non-effective way).
>
> Obviously there is bijection between Turing machines and N, holes or
> not.
>
Well, yes, I think it's obvious, but I also think it's obvious that the
anti-diagonal exists. I don't think you can have one without the other.
> > So I
> > should be allowed to do the same with the anti-diagonal and say "Here
> > is a non-computable real number."
>
> What justifies saying that it exists?
>
What justifies saying that the enumeration exists? If it does, the
anti-diagonal should exist too.
Newberry
David Marcus wrote:
> Newberry wrote:
> >
> > David Marcus wrote:
> > > Newberry wrote:
> > > > David Marcus wrote:
> > > > > Newberry wrote:
> > > > > > 4) in a finite binary tree the ratio of edges to paths is (2*2^n -
> > > > > > 2)/2^n. In an infinite tree the ratio is lim{n-->oo} (2*2^n - 2)/2^n =
> > > > > > 2.
> > > > >
> > > > > What is the meaning of the word "ratio" in the second sentence?
> > > >
> > > > I cannot recapitulate all the elementary mathematics. There is no space
> > > > for it.
> > >
> > > No idea what that means.
> > >
> > > > But for n approaching infinity the limit converges and it
> > > > converges to 2.
> > >
> > > Yes, of course. However, you wrote "the ratio is...". My question is,
> > > what does this limit have to do with the "ratio of edges to paths" in
> > > the infinite tree?
> >
> > We assign one integer to one layer of the tree. There are infinitely
> > many integers therefore we get an infinite tree.
>
> I don't think you answered my question. What does the limit you gave, or
> the fact that the tree is infinite, have to do with the "ratio of edges
> to paths" in the infinite tree?
The ratio of eges to paths of the infinite tree is the limit
lim{n-->oo} (2*2^n - 2)/2^n.
David Marcus
Indeed. I didn't mean to use the word in that sense.
--
David Marcus
Newberry
Virgil wrote:
> In article <1168120398.4...@i15g2000cwa.googlegroups.com>,
> "Newberry" <newb...@ureach.com> wrote:
>
> > David Marcus wrote:
> > > Newberry wrote:
> > > > David Marcus wrote:
> > > > > Newberry wrote:
> > > > > > 4) in a finite binary tree the ratio of edges to paths is (2*2^n -
> > > > > > 2)/2^n. In an infinite tree the ratio is lim{n-->oo} (2*2^n - 2)/2^n =
> > > > > > 2.
> > > > >
> > > > > What is the meaning of the word "ratio" in the second sentence?
> > > >
> > > > I cannot recapitulate all the elementary mathematics. There is no space
> > > > for it.
> > >
> > > No idea what that means.
> > >
> > > > But for n approaching infinity the limit converges and it
> > > > converges to 2.
> > >
> > > Yes, of course. However, you wrote "the ratio is...". My question is,
> > > what does this limit have to do with the "ratio of edges to paths" in
> > > the infinite tree?
> >
> > We assign one integer to one layer of the tree. There are infinitely
> > many integers therefore we get an infinite tree.
>
> But there is nothing in any finite tree or collection of finite trees
> that to show what happens in an infinite tree.
That is what limits are for. This question was settled 200 years ago.
Newberry
Can you picture one infinity greater than another?
>
> > >
> > > > 2) Actual infinity (that is finished infinity) is a contradiction in
> > > > terms
> > > > 3) Infinite, incompressible strings carrying infinite amount of
> > > > information cannot exist for reasons 1) and 2).
> > >
> > > So why do you believe your enumeration, which you conceded was
> > > non-effective, exists?
> >
> > I never said I believed in any enumeration.
> >
>
> Good. So presumably you won't claim that the reals are countable.
I do not believe that that there are more reals than natural numbers.
>
> > >
> > > > 4) in a finite binary tree the ratio of edges to paths is (2*2^n -
> > > > 2)/2^n. In an infinite tree the ratio is lim{n-->oo} (2*2^n - 2)/2^n =
> > > > 2.
> > >
> > > Wrong, in an infinite tree it's not defined.
> >
> > Is it true that lim{n-->oo}(2*2^n - 2)/2^n = 2?
>
> Yes.
>
> > is it true that we indexed all the layers by integers?
>
> Don't understand this one. You seem to be missing my point.
Here is the point. lim{n-->oo}(2*2^n - 2)/2^n = 2 applies to the
INFINITE tree because there are infinitely many integers.
>
> > Is it true that
> > N is infinite?
> >
>
> Yes.
>
> > >
> > > > It contradicts Cantor's result that the cardinality of the paths is
> > > > greater than the number of the edges.
> > > > 5) The diagonal argument shows that for any matrix of size n there is a
> > > > string of size n that is not in the matrix. Yet for any n such a string
> > > > can be generated and added to the list. You could as well have counters
> > > > A and B with values v(B) and v(A) such that vhen v(A) = n then v(B) =
> > > > n+1. You could keep incrementing these counters till infinity and find
> > > > that for any n v(B) > v(A). Yet it would be absurd to argue that in
> > > > infinity B > A. But the Cantorists do precisely that arguing that they
> > > > can always find one more antidiagonal that is not on the list yet.
> > >
> > > We say that one infinite set is of larger size than another when the
> > > latter can be injected into the former but not bijected onto the
> > > former. Cantor proves this is the case for the set of real numbers and
> > > the set of natural numbers.
> >
> > You missed the point. I am saying that any time you find the
> > anti-diagonal I can put back on the list. What leads you to believe
> > that once we reach infinity there will be one outstanding anti-diagonal
> > left before I have a chance to put it in the list.
> >
>
> Given any countable set of real numbers, there is a real number not in
> the set. That shows that the set of real numbers is not countable.
Any real that is not on the list can be added to the list.
>
> > >
> > > > When
> > > > you observe a dog chasing its tail you do not conclude that one
> > > > infinity is greater than another.
> > > >
> > > > >
> > > > > > Secondly procedures that are not total are still considered effective.
> > > > > > Case in point is my example of a list of modified Turing machines. It
> > > > > > does not matter one iota if any given machine will terminate or not
> > > > > > because in either case it will compute a real number. And there no more
> > > > > > computable real numbers than there are modified Turing machines.
> > > > > >
> > > > >
> > > > > You are not justified in saying the real numbes are countable from your
> > > > > standpoint unless you can give an effective enumeration of the
> > > > > computable reals, which gives an effective procedure for finding the
> > > > > m-th digit of the n-th real.
> > > >
> > > > You added this arbitrary condition to preserve the diagonal argument.
> > > >
> > >
> > > It's no more arbitrary than the requirement that reals be computable.
> > >
> > > > If the enumeration you've given is good
> > > > > enough to be called an enumeration, why shouldn't I take the
> > > > > anti-diagonal for it and say that's good enough to be called a real
> > > > > number?
> > > >
> > > > Because the diagonal will have holes.
> > > >
> > >
> > > When I objected to you that the enumeration will have holes, you said,
> > > "Fine, get rid of the holes"
> >
> > I do not recall saying this.
> >
>
> http://groups.google.com/group/sci.math/msg/1b67d0b41d39655c?dmode=source
I could not find the quote there.
If some of the (countable many) Turing machines go into infinite loop
or infinite recursion then the diagonal will not be computable.
>
> > > So I
> > > should be allowed to do the same with the anti-diagonal and say "Here
> > > is a non-computable real number."
> >
> > What justifies saying that it exists?
> >
>
> What justifies saying that the enumeration exists? If it does, the
> anti-diagonal should exist too.
If the enumeration does not exist then there is no diagonal.
Virgil
"Newberry" <newb...@ureach.com> wrote:
Why?
It is definitely not required that the limit of a quotient ibe equal to
the quotient of the limits when any of the limits fails to exist.
In this case, two of the limits do not exist at all, so your claim of
equality fails.
Virgil
"Newberry" <newb...@ureach.com> wrote:
Says someone who cleary does not know what limit theorems say, or what
they mean.
The existence of a limit for finite but increasing values of n in N does
not carry over to any corresponding property for non-naturals.
imagin...@despammed.com
Gosh. What a lot of writing.
<snip>
> You missed the point. I am saying that any time you find the
> anti-diagonal I can put back on the list. What leads you to believe
> that once we reach infinity there will be one outstanding anti-diagonal
> left before I have a chance to put it in the list.
Aha! Well, when we reach infinity, we've reached the end of something
with no end, so everything is true, so you win. Well done!
Brian Chandler
http://imaginatorium.org
Virgil
"Newberry" <newb...@ureach.com> wrote:
> Rupert wrote:
> > Why? It says there's an injection from N into P(N) and no bijection
> > from N onto P(N). Seems to me I understand it perfectly well.
>
> Can you picture one infinity greater than another?
All one has to "picture" is an injection from N to P(N), and a reason
why there is no injection in the reverse direction.
Both of which I can do.
> > Good. So presumably you won't claim that the reals are countable.
>
> I do not believe that that there are more reals than natural numbers.
Then you must also believe yourself able to inject the reals to the
naturals, or surject the naturals to the reals.
So please present us with one or the other as evidence of the
justifiability of your belief.
> Here is the point. lim{n-->oo}(2*2^n - 2)/2^n = 2 applies to the
> INFINITE tree because there are infinitely many integers.
It would only apply if there were any natural numbers which measured the
length of a path in an infinite binary tree.
While there re infinitely many naturals, none of them are infinitely
large.
> > Given any countable set of real numbers, there is a real number not in
> > the set. That shows that the set of real numbers is not countable.
>
> Any real that is not on the list can be added to the list.
And the original rule applied to that list ( or any other list) produces
a number not in the list to which it is applied.
So that as soon as a list exists, so does a number not in it.
One can, in fact, modify the rule so that for any given list of reals
there is one number not in the list for every real number.
I.e., for every list of reals there are at least as many real
non-members of that list as there are members.
David Marcus
> David Marcus wrote:
> > I don't think you answered my question. What does the limit you gave, or
> > the fact that the tree is infinite, have to do with the "ratio of edges
> > to paths" in the infinite tree?
>
> The ratio of eges to paths of the infinite tree is the limit
> lim{n-->oo} (2*2^n - 2)/2^n.
Is this a theorem or a definition?
--
David Marcus
David Marcus
> Virgil wrote:
> > But there is nothing in any finite tree or collection of finite trees
> > that to show what happens in an infinite tree.
>
> That is what limits are for.
What "that" are you referring to? I.e., what are limits for?
> This question was settled 200 years ago.
What question was settled 200 years ago?
--
David Marcus
David Marcus
> Rupert wrote:
> > Newberry wrote:
> Can you picture one infinity greater than another?
Sure. Can't you?
> > Good. So presumably you won't claim that the reals are countable.
>
> I do not believe that that there are more reals than natural numbers.
What do you mean by "believe"? Do you mean that you can prove something?
> > > is it true that we indexed all the layers by integers?
> >
> > Don't understand this one. You seem to be missing my point.
>
> Here is the point. lim{n-->oo}(2*2^n - 2)/2^n = 2 applies to the
> INFINITE tree because there are infinitely many integers.
What does "applies to" mean in this context?
> > Given any countable set of real numbers, there is a real number not in
> > the set. That shows that the set of real numbers is not countable.
>
> Any real that is not on the list can be added to the list.
What does that accomplish?
--
David Marcus
Rupert
Can you picture four-dimensional space? I don't know what this question
means. It's irrelevant. I understand the meaning of the statement
perfectly well.
> >
> > > >
> > > > > 2) Actual infinity (that is finished infinity) is a contradiction in
> > > > > terms
> > > > > 3) Infinite, incompressible strings carrying infinite amount of
> > > > > information cannot exist for reasons 1) and 2).
> > > >
> > > > So why do you believe your enumeration, which you conceded was
> > > > non-effective, exists?
> > >
> > > I never said I believed in any enumeration.
> > >
> >
> > Good. So presumably you won't claim that the reals are countable.
>
> I do not believe that that there are more reals than natural numbers.
>
So you either reject the claim that the naturals can be injected into
the reals, or you claim that the naturals can be bijected onto the
reals. Somehow I doubt the former. So how does this square with your
saying "I never said I believed in any enumeration"?
> >
> > > >
> > > > > 4) in a finite binary tree the ratio of edges to paths is (2*2^n -
> > > > > 2)/2^n. In an infinite tree the ratio is lim{n-->oo} (2*2^n - 2)/2^n =
> > > > > 2.
> > > >
> > > > Wrong, in an infinite tree it's not defined.
> > >
> > > Is it true that lim{n-->oo}(2*2^n - 2)/2^n = 2?
> >
> > Yes.
> >
> > > is it true that we indexed all the layers by integers?
> >
> > Don't understand this one. You seem to be missing my point.
>
> Here is the point. lim{n-->oo}(2*2^n - 2)/2^n = 2 applies to the
> INFINITE tree because there are infinitely many integers.
>
Look, this is just drivel. You've given no reason for thinking this
limit has anything to do with anything.
> >
> > > Is it true that
> > > N is infinite?
> > >
> >
> > Yes.
> >
> > > >
> > > > > It contradicts Cantor's result that the cardinality of the paths is
> > > > > greater than the number of the edges.
> > > > > 5) The diagonal argument shows that for any matrix of size n there is a
> > > > > string of size n that is not in the matrix. Yet for any n such a string
> > > > > can be generated and added to the list. You could as well have counters
> > > > > A and B with values v(B) and v(A) such that vhen v(A) = n then v(B) =
> > > > > n+1. You could keep incrementing these counters till infinity and find
> > > > > that for any n v(B) > v(A). Yet it would be absurd to argue that in
> > > > > infinity B > A. But the Cantorists do precisely that arguing that they
> > > > > can always find one more antidiagonal that is not on the list yet.
> > > >
> > > > We say that one infinite set is of larger size than another when the
> > > > latter can be injected into the former but not bijected onto the
> > > > former. Cantor proves this is the case for the set of real numbers and
> > > > the set of natural numbers.
> > >
> > > You missed the point. I am saying that any time you find the
> > > anti-diagonal I can put back on the list. What leads you to believe
> > > that once we reach infinity there will be one outstanding anti-diagonal
> > > left before I have a chance to put it in the list.
> > >
> >
> > Given any countable set of real numbers, there is a real number not in
> > the set. That shows that the set of real numbers is not countable.
>
> Any real that is not on the list can be added to the list.
>
So what?
> >
> > > >
> > > > > When
> > > > > you observe a dog chasing its tail you do not conclude that one
> > > > > infinity is greater than another.
> > > > >
> > > > > >
> > > > > > > Secondly procedures that are not total are still considered effective.
> > > > > > > Case in point is my example of a list of modified Turing machines. It
> > > > > > > does not matter one iota if any given machine will terminate or not
> > > > > > > because in either case it will compute a real number. And there no more
> > > > > > > computable real numbers than there are modified Turing machines.
> > > > > > >
> > > > > >
> > > > > > You are not justified in saying the real numbes are countable from your
> > > > > > standpoint unless you can give an effective enumeration of the
> > > > > > computable reals, which gives an effective procedure for finding the
> > > > > > m-th digit of the n-th real.
> > > > >
> > > > > You added this arbitrary condition to preserve the diagonal argument.
> > > > >
> > > >
> > > > It's no more arbitrary than the requirement that reals be computable.
> > > >
> > > > > If the enumeration you've given is good
> > > > > > enough to be called an enumeration, why shouldn't I take the
> > > > > > anti-diagonal for it and say that's good enough to be called a real
> > > > > > number?
> > > > >
> > > > > Because the diagonal will have holes.
> > > > >
> > > >
> > > > When I objected to you that the enumeration will have holes, you said,
> > > > "Fine, get rid of the holes"
> > >
> > > I do not recall saying this.
> > >
> >
> > http://groups.google.com/group/sci.math/msg/1b67d0b41d39655c?dmode=source
> I could not find the quote there.
>
You wrote:
`It does not need to. "3.14" is a real number just as
"3.140000000000........"'
You're saying the fact that there are holes doesn't matter. You
advocate replacing 3.14 followed by an infinite string of holes with
3.1400000000......
That's right, the enumeration will not be effective, and the diagonal
will not be computable. I don't understand why you believe in the
enumeration but not the diagonal.
> >
> > > > So I
> > > > should be allowed to do the same with the anti-diagonal and say "Here
> > > > is a non-computable real number."
> > >
> > > What justifies saying that it exists?
> > >
> >
> > What justifies saying that the enumeration exists? If it does, the
> > anti-diagonal should exist too.
>
> If the enumeration does not exist then there is no diagonal.
>
True. The nonexistence of the enumeration is the point of Cantor's
argument.
Newberry
Definition.
>
> --
> David Marcus