I would like to collect what the readers think are the most common
logical errors in the world today (outside of the academic world) and
how they might be most easily recognized. If you (the reader) would
please email me (jmer…@mitre.org) what you think, I would appreciate it.
If an interest is expressed by sufficient numbers, and I get sufficient
answers to warrant it, I’ll post the accumulation.
Thank you.
Jim Meritt
—
James W. Meritt: m23…@mwunix.mitre.org – or – jmer…@mitre.org
The opinions above are mine. If anyone else wants to share them, fine.
They may say so if they wish. The facts "belong" to noone and simply are.
In article <1v8kv3$…@optima.cs.arizona.edu> gude…@CS.Arizona.EDU (David Gudeman) writes:
>In article <1v32luINN…@senator-bedfellow.MIT.EDU> Timothy Y Chow writes:
>]In article <1v0gv8$…@optima.cs.arizona.edu> gude…@CS.Arizona.EDU
>](David Gudeman) writes:
…………………….
>Now f can be used to generate an infinite sequence of digits, and this
>sequence of digits represents a unique real number r. In other words,
>f is a representation of a random real number. If R is guaranteed to
>terminate then R is an algorithm for generating random real numbers.
That a random number between 0 and 1 with the uniform distribution
has the property that its base-k digits are independent and have a
uniform distribution on {0, 1, …, k-1} has been known since "antiquity."
But since they are independent, a procedure for producing them cannot
terminate, as no matter how many have been produced, one still knows
nothing about the others.
—
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
Phone: (317)494-6054
hru…@snap.stat.purdue.edu (Internet, bitnet)
{purdue,pur-ee}!snap.stat!hrubin(UUCP)
In article <1v8kv3$…@optima.cs.arizona.edu> gude…@CS.Arizona.EDU (David Gudeman) writes:
>[...] I wasn’t talking about
>countable additivity. I was talking about the argument that it is
>impossible to define an even distribution function d(x) on rational
>numbers such that for all 0<=x<=1, d(x) is the probability that a
>random rational number in that range is equal to x. I think I agree
>with this argument, but add that this does not prove the impossibility
>of defining an "even distribution" on the range, it just requires a
>different way of describing the distribution besides the type of
>distribution function usually used.
It doesn’t require a different kind of DESCRIPTION, it requires a
different notion of "distribution", one which doesn’t require countable
additivity. If you require countable additivity (plus all the other
usual properties of a probability measure, which I think are "more
intrinsic" than countable additivity), then the argument does indeed
show that it is impossible to define an even distribution on a
countable set. You may not think you were talking about countable
additivity, but you must have been
—
Ian Sutherland
i…@eecs.nwu.edu
Sans Peur
In article <1v8kv3$…@optima.cs.arizona.edu> gude…@CS.Arizona.EDU (David Gudeman) writes:
>In article <1v32luINN…@senator-bedfellow.MIT.EDU> Timothy Y Chow writes:
[Concerning a certain proposed probability distribution on the rationals
between 0 and 1]
>]If I understand correctly, what Gudeman is advocating
>](in modern math jargon) is to retain the property that the measure of an
>]interval I[a,b] is b – a, but give up countable additivity. This should
>]be consistent, but I don’t understand Gudeman’s argument with integrals
>]and "the limit as dx goes to zero." It is not clear to me that one can
>]formulate a theory of integration on finitely additive algebras that
>]allows these kinds of arguments to go through.
>I may be confusing you with someone else, since I wasn’t talking about
>countable additivity. I was talking about the argument that it is
>impossible to define an even distribution function d(x) on rational
>numbers such that for all 0<=x<=1, d(x) is the probability that a
>random rational number in that range is equal to x.
Well, you were talking about probabilities, and these days people
usually take probability theory to be based on measure theory, a measure
being a countably additive set function defined on some sigma-algebra of
sets. There is no probability measure on the rationals between 0 and 1
such that the probability of such a number being between a and b is b-a.
The obvious way to try to wriggle around this is to drop countable
additivity. Certainly people have studied generalizations of measures
in which countable additivity is not assumed – I think they’re sometimes
called "charges" or some such thing.
As for defining "an even distribution function d(x) on rational
numbers such that for all 0<=x<=1, d(x) is the probability that a
random rational number in that range is equal to x," it is very unclear
what this means. If one takes d(x) to be the probability that a random
number is *equal* to x, the sum of d(x) over all rationals between 0 and
1 should be equal to 1, right? This is certainly possible, in many
ways, but I don’t know what it would mean for such a d(x) to be "even".
In article <C8GrDv….@mentor.cc.purdue.edu> Herman Rubin writes:
]In article <1v8kv3$…@optima.cs.arizona.edu> gude…@CS.Arizona.EDU (David Gudeman) writes:
]>In article <1v32luINN…@senator-bedfellow.MIT.EDU> Timothy Y Chow writes:
]>]In article <1v0gv8$…@optima.cs.arizona.edu> gude…@CS.Arizona.EDU
]>](David Gudeman) writes:
]
] …………………….
]
]>Now f can be used to generate an infinite sequence of digits, and this
]>sequence of digits represents a unique real number r. In other words,
]>f is a representation of a random real number. If R is guaranteed to
]>terminate then R is an algorithm for generating random real numbers.
]
]That a random number between 0 and 1 with the uniform distribution
]has the property that its base-k digits are independent and have a
]uniform distribution on {0, 1, …, k-1} has been known since "antiquity."
]But since they are independent, a procedure for producing them cannot
]terminate, as no matter how many have been produced, one still knows
]nothing about the others.
So much is obvious, so what’s your point?
—
David Gudeman
gude…@cs.arizona.edu
In article <1vg25p…@optima.cs.arizona.edu> gude…@CS.Arizona.EDU (David Gudeman) writes:
>In article <C8GrDv….@mentor.cc.purdue.edu> Herman Rubin writes:
>]That a random number between 0 and 1 with the uniform distribution
>]has the property that its base-k digits are independent and have a
>]uniform distribution on {0, 1, …, k-1} has been known since "antiquity."
>]But since they are independent, a procedure for producing them cannot
>]terminate, as no matter how many have been produced, one still knows
>]nothing about the others.
>So much is obvious, so what’s your point?
Recall that I expressed concern about your nonterminating "algorithm"
for generating random reals. You responded by saying that instead of a
procedure that returns a sequence of digits, we can have a procedure
that returns a function f that take a natural number and returns a
digit. Rubin’s point is that such a procedure won’t terminate either.
How are you going to specify your function f in finite time? You can’t
in general. This is Rubin’s point: any finite amount of information
about the function f, no matter how large, is insufficient to specify
f. Another way to see this is to note that if you are using a finite
alphabet to represent your functions, then only a countable number of
functions f can have a finite representation—but you need to
represent an uncountable number of functions.
What about a function f that does the following:
If f is called with parameter i, and f has never been called with
parameter i before, then f returns a random number 0..k-1
If f is called with parameter i, and f has been called with parameter i
before (and returned j), then f returns j.
With this function, the only information that is needed is its own past
history. Of course, at any given time this function can’t specify an
_exact_ real number, only a range of possible real numbers. If it is
called repetitively, however, it will not "contradict itself", and by
calling it enough you can get the range of possible reals to be
arbitrarily small.
Of course, this representation of reals has problems, but it does
satisfy Gudeman’s requirements.
-Matt
- Hide quoted text — Show quoted text -
gude…@CS.Arizona.EDU (David Gudeman) writes:
>In article <C8GrDv….@mentor.cc.purdue.edu> Herman Rubin writes:
>]In article <1v8kv3$…@optima.cs.arizona.edu> gude…@CS.Arizona.EDU (David Gudeman) writes:
>]>In article <1v32luINN…@senator-bedfellow.MIT.EDU> Timothy Y Chow writes:
>]>]In article <1v0gv8$…@optima.cs.arizona.edu> gude…@CS.Arizona.EDU
>]>](David Gudeman) writes:
>]
>] …………………….
>]
>]>Now f can be used to generate an infinite sequence of digits, and this
>]>sequence of digits represents a unique real number r. In other words,
>]>f is a representation of a random real number. If R is guaranteed to
>]>terminate then R is an algorithm for generating random real numbers.
>]
>]That a random number between 0 and 1 with the uniform distribution
>]has the property that its base-k digits are independent and have a
>]uniform distribution on {0, 1, …, k-1} has been known since "antiquity."
>]But since they are independent, a procedure for producing them cannot
>]terminate, as no matter how many have been produced, one still knows
>]nothing about the others.
>So much is obvious, so what’s your point?
You assume that each f generates a unique real number and each real
number is generated by some f. So generating f’s is equivalent to
generating the real numbers themselves.
Dr. Rubin’s point is that no algorithm that generates uniform real
numbers can terminate. (More precisely it may terminate with
probability zero.) It follows that no algorithm that generates
objects in one-to-one correspondence with the real numbers (your f
functions) can terminate if the implied distribution of the real
numbers is uniform. Your hypothesis — "If R is guaranteed to
terminate …" – is necessarily false, so speculating about what
would happen if it were true is irrelevant.
—
T. Scott Thompson email: thomp…@atlas.socsci.umn.edu
Department of Economics phone: (612) 625-0119
University of Minnesota fax: (612) 624-0209
In article <1vg9na$…@senator-bedfellow.MIT.EDU> Timothy Y Chow writes:
]
]Recall that I expressed concern about your nonterminating "algorithm"
]for generating random reals. You responded by saying that instead of a
]procedure that returns a sequence of digits, we can have a procedure
]that returns a function f that take a natural number and returns a
]digit. Rubin’s point is that such a procedure won’t terminate either.
But f is not the algorithm, the procedure that produces f is the
algorithm, and that function terminates. f is a representation of a
real that lets you do anything you can do with a representation like
sqrt(2) for the square root of 2. You don’t have to expand all of the
digits of f to work with it any more than you need to expand all of
the digits of sqrt(2).
Do you believe in the diagonal argument for the non-countability of
reals? How is the diagonally defined real number in that argument a
better real than f?
]How are you going to specify your function f in finite time? You can’t
]in general.
Of course you can specify it in finite time, you just can’t expand it
in finite time. But this is the case with all infinite functions.
]This is Rubin’s point: any finite amount of information
]about the function f, no matter how large, is insufficient to specify
]f.
And as before, my response is: so what’s your point? I’ll elaborate
by noting that I never said that f is specified with a finite amount
of information.
]Another way to see this is to note that if you are using a finite
]alphabet to represent your functions, then only a countable number of
]functions f can have a finite representation—but you need to
]represent an uncountable number of functions.
I never said I was representing f with an alphabet.
—
David Gudeman
gude…@cs.arizona.edu
In article <thompson.740083…@daphne.socsci.umn.edu> T. Scott Thompson writes:
]gude…@CS.Arizona.EDU (David Gudeman) writes:
]
]>In article <C8GrDv….@mentor.cc.purdue.edu> Herman Rubin writes:
]>]
]>]That a random number between 0 and 1 with the uniform distribution
]>]has the property that its base-k digits are independent and have a
]>]uniform distribution on {0, 1, …, k-1} has been known since "antiquity."
]>]But since they are independent, a procedure for producing them cannot
]>]terminate, as no matter how many have been produced, one still knows
]>]nothing about the others.
]
]>So much is obvious, so what’s your point?
]
]You assume that each f generates a unique real number and each real
]number is generated by some f. So generating f’s is equivalent to
]generating the real numbers themselves.
No, I made no such assumptions. In fact I doubt that the first
assumption is true, and I suspect that it would be highly non-trivial
to prove the second, although intuitively it seems to be true.
However, I will grant that the set of f’s must be uncountable.
]Dr. Rubin’s point is that no algorithm that generates uniform real
]numbers can terminate.
If that was his intended argument, he didn’t make any points in that
direction. All he said is that f doesn’t terminate, which as I said,
is obvious. I suspect he thinks a "non-terminating" computation
cannot represent a number, but I’m sure that if he thinks a little
longer, he will change his mind. After all, equivalence of real
numbers is only semidecidable anyway.
One more clarification, since the f’s are uncountable, they clearly
cannot all be represented by finite terms. f is a function, and not
all functions can be represented by finite terms. (In fact, if you
assume that f generates binary digits, there is an obvious isomorphism
between f and sets of integers).
Hmm. I wonder if I’m on the verge of finding a solution to the
.
continuum problem
—
David Gudeman
gude…@cs.arizona.edu