Finding size of Variable

M

Mark Lawrence

Le mardi 11 février 2014 20:04:02 UTC+1, Mark Lawrence a écrit :
-1


The day you find an operator working on the set of
reals (R) and it is somehow "optimized" for N
(the subset of natural numbers), let me know.

A conflict is quickly appearing. Either the operator is
not correctly defined or the choice of the set is wrong.

You can replace the "operator" with an "encoding" and
the "set" with a "repertoire of characters".

It's the main reason, why we have to live today with
all these coding schemes. Even in more sophisticated
cases like, CID-fonts or "char boxes" in a pdf (with the
hope you understand how it works).

jmf

I ask you, members of the jury, to find the accused, jmf, guilty of
writing nonsense and deliberately using google groups to double line
space. The evidence is directly above and quite clearly prooves, beyond
a resonable doubt, that no verdict other than guilty can be recorded. I
rest my case, m'lud.
 
R

Rustom Mody

Chris Angelico writes:
So, if I understand you right, you want to say that you've not found
a computer that works with the *complete* set of real numbers. Yes?
Correct. [...] My point is that computers *do not* work with real
numbers, but only ever with some subset thereof [...]
You've done it again: by saying that "computers *do not* work with real
numbers", that if I find a real number - e.g. the number 4 - your
position is that, since it's a real number, computers don't work with
that number.

There is a convention in logic called the implicit universal quantifier
convention: when a bald unqualified reference is in a statement it means
it is universally quantified. eg
"A triangle is a polygon with 3 sides"
really means
"ALL polygons with 3 sides are triangles" ie the ALL is implied

Now when for-all is inverted by de Morgan it becomes "for-some not..."

So "computers work with real numbers" really means "computers work with
all real numbers" and that is not true
That's why I think you need to be clear that your point isn't "computers
don't work with real numbers", but rather "computers work only with a
limited subset of real numbers".

Yes both these statements are true by above.

In fact computers cannot work with real numbers because the real number
set is undecidable/uncomputable. In particular, trivial operations like
equality on reals -- IN GENERAL -- is undecidable.
 
M

Marko Rauhamaa

Chris Angelico said:
Integers as far as RAM will allow, usually (which is the same caveat
as is used when describing a programming language as "Turing complete"
- strictly, that term is valid only if it has infinite memory
available), but yes, technically that's a subset of integers. However,
that subset is bounded by something other than the code, algorithms,
or even hardware - it's theoretically possible to add two numbers
larger than will fit in memory, by reading them in (even over the
network), adding segments, and writing them out again.

Text files. Since there's already no such thing as a "text file"
unless you know what its encoding is, I don't see a problem with this.

Text files suffer from the same caveat as integers: there's a limit to
how much you can store on the physical computer.

A similar caveat prevents computers from dealing with real numbers. In
the case of integers, you have a finite subset of ℵ₀. In the case of
reals, you have a finite subset of ℵâ‚.

Yes, integers are algorithmically much more tractable than reals.
However, in practice integer math is often computationally much harder
than real math. Take cryptography vs calculus as an example.


Marko
 
R

Rustom Mody

I ask you, members of the jury, to find the accused, jmf, guilty of
writing nonsense and deliberately using google groups to double line
space. The evidence is directly above and quite clearly prooves, beyond
a resonable doubt, that no verdict other than guilty can be recorded. I
rest my case, m'lud.

Is a proof more fool-proof because prove is spelt proove <wink>?
 
G

Grant Edwards

Not *any* computer? Not in *any* way? The Python built-in "float"
type "works with the set of real numbers", in a way.

The only people who think that are people who don't actualy _use_
floating point types on computers.
What specific behaviour would, for you, qualify as "works with the
set of real numbers in any way"

There's a whole laundry list of things (some of them rather nasty and
difficult) you have to worry about when using FP that simply don't
apply to "real" numbers.
 
G

Gisle Vanem

Grant Edwards said:
The only people who think that are people who don't actualy _use_
floating point types on computers.

FPU parsing the IEEE spec, or?. I didn't quite parse what *you* wrote.
To paraphrase:
#include <math.h>
"there are FP_NORMAL and FP_SUBNORMAL people in the world;
those who understand IEEE 754 and those who don't." ..

--gv
 
C

Chris Angelico

Text files suffer from the same caveat as integers: there's a limit to
how much you can store on the physical computer.

Sure, but nobody said the text file had to be _stored_ anywhere :)
Computers are quite capable of working with streams of incoming data
that are potentially infinite in size. But again, this is the same
caveat as the Turing machine. If you wrote a Python interpreter for a
Turing machine, it would be - without any changes to Python - capable
of handling any integer and any text file.

ChrisA
 
I

Ian Kelly

Chris Angelico writes:
On Wed, Feb 12, 2014 at 7:56 PM, Ben Finney wrote:
So, if I understand you right, you want to say that you've not found
a computer that works with the *complete* set of real numbers. Yes?
Correct. [...] My point is that computers *do not* work with real
numbers, but only ever with some subset thereof [...]
You've done it again: by saying that "computers *do not* work with real
numbers", that if I find a real number - e.g. the number 4 - your
position is that, since it's a real number, computers don't work with
that number.

There is a convention in logic called the implicit universal quantifier
convention: when a bald unqualified reference is in a statement it means
it is universally quantified. eg
"A triangle is a polygon with 3 sides"
really means
"ALL polygons with 3 sides are triangles" ie the ALL is implied

Now when for-all is inverted by de Morgan it becomes "for-some not..."

So "computers work with real numbers" really means "computers work with
all real numbers" and that is not true

I take exception whenever I see somebody trying to use predicate logic
to determine the meaning of an English sentence. English does not
follow the rules of predicate logic, and English sentences do not map
consistently to logical sentences.

To me, the meaning of "computers do not work with X" depends upon the
domain of X. "Computers do not work with real numbers" implies that
computers do not work with the set of real numbers (but implies
nothing about subsets). "Computers do not work with keyboards" on the
other hand would imply that no computer works with any keyboard (which
of course is demonstrably false).
 
G

Gregory Ewing

Ben said:
That's why I think you need to be clear that your point isn't “computers
don't work with real numbers”, but rather “computers work only with a
limited subset of real numbers”.

They actually work with a subset of *rational* numbers.
All floats representable by a computer are rational.

The rationals happen to be a subset of the reals, but
that's kind of beside the point given that a float
can't represent *any* real number that isn't also
a rational.
 
G

Gregory Ewing

Chris said:
Sure, but nobody said the text file had to be _stored_ anywhere :)
Computers are quite capable of working with streams of incoming data
that are potentially infinite in size.

However, they *can't* work with arbitrary real numbers in an
exact way, even if they are represented by infinitely long
digit streams, and you're willing to run the program for
an infinitely long time to get the result.

Consider adding two of these numbers, for example. You have
to do it starting at the big end, because the small end is
infinitely far away. And you only have a limited amount of
buffer space, so you need to start writing out result
digits before you've seen all the input digits.

But you can't do that, because it's possible that some
pair of input digits you haven't seen yet will cause a
carry-over that ripples back and affects something you've
already written out.

This is where schemes such as computable reals get into
trouble. Doing arithmetic with them gets extremely messy.
 
G

Gregory Ewing

Chris said:
Of course a
computer can work with _some_ real numbers; but only some. (An awful
lot of them, of course. A ridiculously huge number of numbers. More
numbers than you could read in a lifetime! While the number is
extremely large, it still falls pitifully short of infinity.[1])

The number of integers it can work with is also
vanishingly small compared to the total number
of integers.

However, the number of reals is vastly greater
than the number of integers, so the proportion
of reals it can work with is even *more*
vanishingly small. In some sense.
 
D

Dave Angel

Gregory Ewing said:
However, they *can't* work with arbitrary real numbers in an
exact way, even if they are represented by infinitely long
digit streams, and you're willing to run the program for
an infinitely long time to get the result.

Consider adding two of these numbers, for example. You have
to do it starting at the big end, because the small end is
infinitely far away. And you only have a limited amount of
buffer space, so you need to start writing out result
digits before you've seen all the input digits.

But you can't do that, because it's possible that some
pair of input digits you haven't seen yet will cause a
carry-over that ripples back and affects something you've
already written out.
Actually, the particular example you use can be done. When
printing the infinite sum of two infinite decimal streams, you
can simply hold back whenever you get one or more nines. Instead
keep a count of how many nines you're holding, and emit them all
only when you get something other than 9. I've done something
analogous doing run length encoding of an rs232 stream.

But you're right in general.
 
G

Grant Edwards

Chris said:
Of course a computer can work with _some_ real numbers; but only
some. (An awful lot of them, of course. A ridiculously huge number of
numbers. More numbers than you could read in a lifetime! While the
number is extremely large, it still falls pitifully short of
infinity.[1])

The number of integers it can work with is also vanishingly small
compared to the total number of integers.

However, the number of reals is vastly greater than the number of
integers, so the proportion of reals it can work with is even *more*
vanishingly small. In some sense.

More importantly, Computers can generally work with a subset of
integers consisting of all integers between a min value and a max
value. The min and max may be known and fixed at compile time (e.g. C
"int" on a 32-bit machine), or it may depend on how much memory and
time you have. But knowing that you can represent all values in some
range makes life pretty easy.

OTOH, no matter how small the magnitude of the range of real numbers
you pick, computer FP can only represent a very tiny subset of the
rational numbers which are an even tinier subset of the real numbers
within whatever range you care to pick. If you pick your range and
representation intelligently, you can still do some pretty useful
stuff. But, if you pretend you're actually working with real numbers
you will come a cropper.
 
R

Rustom Mody

Chris Angelico writes:
On Wed, Feb 12, 2014 at 7:56 PM, Ben Finney wrote:
So, if I understand you right, you want to say that you've not found
a computer that works with the *complete* set of real numbers. Yes?
Correct. [...] My point is that computers *do not* work with real
numbers, but only ever with some subset thereof [...]
You've done it again: by saying that "computers *do not* work with real
numbers", that if I find a real number - e.g. the number 4 - your
position is that, since it's a real number, computers don't work with
that number.
There is a convention in logic called the implicit universal quantifier
convention: when a bald unqualified reference is in a statement it means
it is universally quantified. eg
"A triangle is a polygon with 3 sides"
really means
"ALL polygons with 3 sides are triangles" ie the ALL is implied
Now when for-all is inverted by de Morgan it becomes "for-some not..."
So "computers work with real numbers" really means "computers work with
all real numbers" and that is not true
I take exception whenever I see somebody trying to use predicate logic
to determine the meaning of an English sentence.

Ok See below.
English does not follow the rules of predicate logic,
Agreed

and English sentences do not map consistently to logical sentences.
Agreed

To me, the meaning of "computers do not work with X" depends upon the
domain of X.
Agreed

"Computers do not work with real numbers" implies that
computers do not work with the set of real numbers (but implies
nothing about subsets).

How come?
"Computers do not work with keyboards" on the
other hand would imply that no computer works with any keyboard (which
of course is demonstrably false).

The example is the other way. If one says:
"Computers have keyboards"
and then we have the demonstratation of say
- a cloud server
- a android phone

which are computers that have no keyboards, then that demonstrates that
"(ALL) computers have keyboards" is false"

Two things therefore come into play here:
1. "All computers have keyboards" is falsified by predicate logic
2. Modelling the English "Computers have keyboards" to the above sentence
needs: grammar, context, good-sense, good-will and a lot of other
good (and soft) stuff.

tl;dr Predicate logic can help to gain some clarity about where
the implied but unstated quantifiers lie.
 
S

Steven D'Aprano

Chris Angelico said:
So, if I understand you right, you want to say that you've not found
a computer that works with the *complete* set of real numbers. Yes?

Correct. […] My point is that computers *do not* work with real
numbers, but only ever with some subset thereof […]

You've done it again: by saying that “computers *do not* work with real
numbersâ€, that if I find a real number – e.g. the number 4 – your
position is that, since it's a real number, computers don't work with
that number.

That answer relies on the assumption that "computers do not work with X"
implies:

for each element x in X:
it is true that "computers do not work with x"

that is to say, a single counter-example of computers working with an
element of X, even if it is a fluke, is enough to disprove the rule.

To give a real-world, non-programming example:

"The former South African apartheid government did not respect the
Universal Human Rights of blacks."

Under your strict interpretation, we would have to say that even a single
example of the apartheid government respecting even a single human rights
of a single black person would be sufficient to disprove the claim.

But there's another interpretation available to us, one which is more
suited to natural language statements as made by Chris: we interpret
"computers do not work with X" as meaning:

there is at least one element x, such that it is true that
"computers do not work with x"


In the case of real numbers, there is an *uncountably infinite* number of
such elements x. In fact, we can pick any two distinct numbers, no matter
how close together, say:

1
1.000000000001

and be sure that there are an uncountably infinite number of real numbers
which computers do not work with between those two values.

For the record, "uncountable infinite" is not just me emphasising that
infinity is too big to count. It's a technical term from mathematics. In
a nutshell it means that not only are there too many elements to count,
but even in an infinite amount of time you couldn't count them all, not
even if you counted infinitely fast.

In fact, it isn't just that there are *specific* real numbers which
computers cannot represent (say, irrationals like pi or e, really tiny
numbers like 1/(googleplex**googleplex**googleplex), or really huge ones
like Graham's Number), but that the fundamental mathematical laws of the
reals are violated by computers.

For example, it is not true that for every number x, 1/1(x)) == x.

py> 1/(1/93.0) == 93.0
False


Nor is it always true that a*(b+c) equals a*b + a*c, or that a+b+c is
necessarily equal to b+c+a.


So it isn't even that floats are merely a subset of reals. They're
actually not reals at all, since the fundamental properties of real
numbers do not always apply to floating point calculations.
 
C

Chris Angelico

"The former South African apartheid government did not respect the
Universal Human Rights of blacks."

Under your strict interpretation, we would have to say that even a single
example of the apartheid government respecting even a single human rights
of a single black person would be sufficient to disprove the claim.

Right. A common interpretation of that statement would be that, by and
large, one can see a parallel between "people whose rights are not
respected" and "people with black skin". The existence of a single
black person whose rights are respected, or a single non-black person
whose rights are not respected, doesn't change that; if there are X
million black people whose rights are not respected, and Y million
white people who are treated like people, and the converses are
measured in thousands, then the statement would be considered valid.

(That said, though, if there *were* a black person whose rights were
respected, then it would be highly notable. I don't know if there had
been such a case with .za, but there were - if you'll forgive me for
Godwinning - a very VERY small number of Jews who held high position
in Nazi Germany, and who were not harmed because they were of too
great value to lose. It's notable because respecting a single person
of a category of people considered "sub-human" effectively disproves
the notion that "all X are less than people". (If one Jew is worth
keeping around, how can you say that Jews are, by definition,
subhuman? If one black woman can hold a highly respected position in a
university, doesn't that prove that black people and women are just as
intelligent as white males?) But, notable or not, it doesn't change
the fact that Nazi Germany *as a whole* considered Jews *as a group*
to be insignificant, and that the apartheid .za govt treated
black-skinned people *as a group* to be insignificant.)

So where does that leave computers and reals? Well, it comes down to
descriptors. Suppose there were a place where all people are treated
perfectly fairly, UNLESS a white-skinned person is male and aged
between 13 and 20, in which case he is considered guilty until proven
innocent. Does this place treat males and females equally? Not really.
But it's also not really accurate to say that "men are mistreated by
the law", any more than it's accurate to say that "IEEE floating point
handles real numbers". I certainly would not say that an integer type
"works with real numbers", simply because it's almost completely
useless to say that - since it's such a tight subset of them.

ChrisA
 
O

Oscar Benjamin

Chris Angelico said:
So, if I understand you right, you want to say that you've not found
a computer that works with the *complete* set of real numbers. Yes?

Correct. [...] My point is that computers *do not* work with real
numbers, but only ever with some subset thereof [...]

You've done it again: by saying that "computers *do not* work with real
numbers", that if I find a real number - e.g. the number 4 - your
position is that, since it's a real number, computers don't work with
that number.

That's why I think you need to be clear that your point isn't "computers
don't work with real numbers", but rather "computers work only with a
limited subset of real numbers".

I think Chris' statement above is pretty clear. Also I didn't find the
original statement confusing and it is a reasonable point to make.

While computers can (with some limitations) do a pretty good job of
integers and rational numbers they cannot truly represent real
computation. Other people have mentioned that there are computer
algebra systems that can handle surds and other algebraic numbers or
some transcendental numbers but none of these comes close to the set
of reals.

This isn't even a question of resource constraints: a digital computer
with infinite memory and computing power would still be limited to
working with countable sets, and the real numbers are just not
countable. The fundamentally discrete nature of digital computers
prevents them from being able to truly handle real numbers and real
computation.

A hypothetical idealised analogue computer would be able to truly do
real arithmetic (but I think in practice the errors would be worse
than single precision floating point).


Oscar
 
M

Marko Rauhamaa

Oscar Benjamin said:
This isn't even a question of resource constraints: a digital computer
with infinite memory and computing power would still be limited to
working with countable sets, and the real numbers are just not
countable. The fundamentally discrete nature of digital computers
prevents them from being able to truly handle real numbers and real
computation.

Well, if your idealized, infinite, digital computer had ℵ₠bytes of RAM
and ran at ℵ₠hertz and Python supported transfinite iteration, you
could easily do reals:

def real_sqrt(y):
for x in continuum(0, max(1, y)):
# Note: x is not traversed in the < order but some other
# well-ordering, which has been proved to exist.
if x * x == y:
return x
assert False

The function could well return in finite time with a precise result for
any given nonnegative real argument.


Marko
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
474,078
Messages
2,570,572
Members
47,204
Latest member
MalorieSte

Latest Threads

Top