 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
What is Ackermann's function, why does it grow so fast, and why does
anybody care anyway?
(I'm hoping you can explain this better than Wikipedia...)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> What is Ackermann's function, why does it grow so fast,
That I imagine wikipedia can answer...
> and why does anybody care anyway?
I wouldn't guarantee I'm write, but I believe it's because it's the
first function demonstrated that (basically) you needed indefinite loops
to calculate.
In other words, no number of bounded for-loops will evaluate the
function. You *have* to have while loops in your language to evaluate
the value of the ackerman function.
That's my understanding of why anyone cares, but it's an old memory, so
I might be messing things up.
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> What is Ackermann's function, why does it grow so fast, and why does
> anybody care anyway?
>
> (I'm hoping you can explain this better than Wikipedia...)
>
I'm not Darren, and he'd probably be more familiar with this than I, but
here's what I recall.
The class of computable functions (also known as recursive functions)
are something that you're familiar with. Considered in their most basic
context, these are all functions which take a natural number as input,
provides an integer as output, and which you could write a computer
program to compute. If there's a program which can compute this
function for each possible natural number (in other words, it always
halts), then you have a total computable function.
Way back in the early days of people starting to understand this sort of
stuff -- before diagionalization proofs were used for this sort of
thing, there was a conjecture that this class of total computable
functions was equivalent to the class of what are called primitive
recursive functions. You can think of a primitive recursive function,
basically (iirc), as any function you could code up if only allowed for
loops which didn't change their loop bounds during their execution (no
recursion and no while loops either obviously).
While it seems "obvious" since you're familiar with diagonalization type
arguements, that this class is strictly smaller than the class of total
computable functions, you can get a bit of an idea for why people made
this confusion if you attempt to actually think of a function which is
total computable but not primitive recursive. Almost all the function
you normally deal with (addition, subtraction, division, factorial,
exponentiation, etc) are all primitive recursive.
Here's where the Ackermann function comes in. It's obviously a total
computable function, yet you can show that it cannot be primitive
recursive. The essence of this argument is that the growth rate of the
Ackermann function is larger than what could be achieved by any
primitive recursive function. I believe that the Ackermann function was
the first concrete example of a well defined total computable function
which was not primitive recursive -- hence why people care about it.
If you're curious as to why it grows so quickly, I suggest you code it
up and examine it's behavior for a bit. It's an enjoyable exercise in
experimentally poking around in the guts of a rather odd mathematical
function.
Fun Fact! The union-find data structure has as an amortized complexity
bound for many of many of its operations a running time proportional to
the *inverse* of the Ackermann function! which is the slowest growing
non-constant big-O of any algorithm I'm aware of (though I've explicitly
never looked for others).
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
> I'm not Darren, and he'd probably be more familiar with this than I, but
> here's what I recall.
>
> The class of computable functions (also known as recursive functions)
> are something that you're familiar with.
Er... no.
> Considered in their most basic
> context, these are all functions which take a natural number as input,
> provides an integer as output, and which you could write a computer
> program to compute. If there's a program which can compute this
> function for each possible natural number (in other words, it always
> halts), then you have a total computable function.
>
> Way back in the early days of people starting to understand this sort of
> stuff -- before diagionalization proofs were used for this sort of
> thing, there was a conjecture that this class of total computable
> functions was equivalent to the class of what are called primitive
> recursive functions. You can think of a primitive recursive function,
> basically (iirc), as any function you could code up if only allowed for
> loops which didn't change their loop bounds during their execution (no
> recursion and no while loops either obviously).
>
> While it seems "obvious" since you're familiar with diagonalization type
> arguements, that this class is strictly smaller than the class of total
> computable functions, you can get a bit of an idea for why people made
> this confusion if you attempt to actually think of a function which is
> total computable but not primitive recursive. Almost all the function
> you normally deal with (addition, subtraction, division, factorial,
> exponentiation, etc) are all primitive recursive.
>
> Here's where the Ackermann function comes in. It's obviously a total
> computable function, yet you can show that it cannot be primitive
> recursive. The essence of this argument is that the growth rate of the
> Ackermann function is larger than what could be achieved by any
> primitive recursive function. I believe that the Ackermann function was
> the first concrete example of a well defined total computable function
> which was not primitive recursive -- hence why people care about it.
I see... Thank you for the illumination. Now tell me what a
diagonalization argument is, and how you pronounce it without sounding
stupid. ;-)
> If you're curious as to why it grows so quickly, I suggest you code it
> up and examine it's behavior for a bit. It's an enjoyable exercise in
> experimentally poking around in the guts of a rather odd mathematical
> function.
Note how the Wikipedia article explicitly mentions a Haskell
implementation because it's so easy. ;-) Of course, if you want to
*observe* its behaviour rather than just get the answer, you'd code it a
bit differently...
> Fun Fact! The union-find data structure has as an amortized complexity
> bound for many of many of its operations a running time proportional to
> the *inverse* of the Ackermann function! which is the slowest growing
> non-constant big-O of any algorithm I'm aware of (though I've explicitly
> never looked for others).
Fun fact: This is how I found out about "Ackermann function". Just now.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Fri, 11 Jul 2008 20:20:14 +0100, Orchid XP v8 wrote:
>> I'm not Darren, and he'd probably be more familiar with this than I,
>> but here's what I recall.
>>
>> The class of computable functions (also known as recursive functions)
>> are something that you're familiar with.
>
> Er... no.
Do you understand the concept of recursion?
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> I see... Thank you for the illumination. Now tell me what a
> diagonalization argument is,
Stuff like proofs that the number of real numbers 0 <= N < 1 is larger
than the number of positive integers.
Map each real number to a positive integer. Now for each number, take
the real number whose first digit differs from the first digit of the
first real, whose second digit differs from the second digit of the
second real, etc. You've just constructed a real which is, by
construction, not on your list that maps all real numbers to integers.
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> The class of computable functions (also known as recursive functions)
>>> are something that you're familiar with.
>> Er... no.
>
> Do you understand the concept of recursion?
Sure.
I don't know much about the formal theory of computation though. I
always assumed that "computable function" just meant "function that can
be computed by a computer". Apparently the definition is much less
general that than...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> Map each real number to a positive integer.
Um... like, how? There's more of them...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 <voi### [at] dev null> wrote:
> What is Ackermann's function, why does it grow so fast, and why does
> anybody care anyway?
From a programmer's point of view, simplified: The Ackermann's function
is an example of a function which cannot be computed iteratively, but must
be computed recursively.
This proves by example that not all algorithms can be implemented
iteratively.
(And "iteratively" in this context means "only requires O(1) memory to
compute the algorithm".)
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> From a programmer's point of view, simplified: The Ackermann's function
> is an example of a function which cannot be computed iteratively, but must
> be computed recursively.
>
> This proves by example that not all algorithms can be implemented
> iteratively.
>
> (And "iteratively" in this context means "only requires O(1) memory to
> compute the algorithm".)
Mmm, I see. Yes, the third identity requires you to either recurse twice
(requiring more stack), or to build a table of results to avoid the
extra recursion (also requiring more memory).
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New <dne### [at] sanrrcom> wrote:
> Stuff like proofs that the number of real numbers 0 <= N < 1 is larger
> than the number of positive integers.
> Map each real number to a positive integer. Now for each number, take
> the real number whose first digit differs from the first digit of the
> first real, whose second digit differs from the second digit of the
> second real, etc. You've just constructed a real which is, by
> construction, not on your list that maps all real numbers to integers.
I think that the concept you are trying to explain could become clearer
if you also prove why the amount of rational numbers between 0 and 1 is
the *same* as the amount of integers. (In other words, each rational
number can be uniquely mapped to an integer, and there are no rational
numbers that can't be.)
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
>> The class of computable functions (also known as recursive functions)
>> are something that you're familiar with.
>
> Er... no.
Well, maybe not by name, but you're certainly familiar with the concept.
For example, you can see that the Ackermann function is computable
while the Halting function is not. At the very least, since you code a
lot you're intuitively familiar with the notion of what sorts of
functions you can code (though maybe less so what sorts you *can't* code).
> I see... Thank you for the illumination. Now tell me what a
> diagonalization argument is, and how you pronounce it without sounding
> stupid. ;-)
I pronounce it diagonal (as in the diagonal of a square) ization (as in
rasterization, memorization, etc.).
I don't have a formal definition, but perhaps I can give some of the
intuition. The name derives from `Cantor's diagonal argument' for why
the set of real numbers is strictly larger than the set of rationals.
If you're not familiar with this proof you should read about it, as it's
both absolutely brilliant and extremely simple.
I've using the term more generally of course, but the basic idea is the
same. Let's say you have two set of elements, A and B, and you want to
provide a proof that there exist something in B which is not in A. One
way you can do this that ends up being useful much of the time is to
define an element, x, in B in such a way that it represents a
modification of each element in A, and by doing so we prove that x
cannot be in A since it's different that each element of A.
This may sound a bit odd, and it oversimplifies a lot too, but I think I
can explain it better with examples.
In the case of Cantor's original argument A is the set of natural
numbers and B is the set of reals. If we assume that there are the same
number of natural numbers and reals, then you could provide an
(infinite) list of all the real numbers. To form a real number that
cannot be in this list, we form a number, x, which has at each digit a
modification of a different real number in a hypothetical list. Means
that x cannot be in our list, and thus by contradiction that it's
impossible to form such a list in the first place.
The halting argument has a similar flavor. In this case we want to show
that there are functions that are not computable, so we create define a
function that, given a program, determines if it halts and then modifies
that behavior. But this program can't work on its own input and thus
cannot be computable in the first place.
There's several ways to apply this idea to show that there are total
computable functions which are not primitive recursive, but here's one.
Represent each primitive recursive program as a natural number (by
compiling it to binary if you wish). Then, define a new function from
the naturals to the naturals which, when given a number, decompiles it
into a primitive recursive function, runs the function with its own
numerical representation as input, and adds one to the result (note that
the primitive recursive function is guaranteed to always halt). The
resulting function is computable, but cannot be primitive recursive
(since then for some input it would have it give its own output plus one!).
You can use the same idea to construct a computable function that grows
faster than any primitive recursive function, or a non-computable
function which grows faster than any computable function (eg. the Busy
Beaver function). It's also the same sort of idea that Goedel used in
his proof that some theorems are unprovable. Personally, I find the
idea to be probably the most interesting discovery of 20th century
mathematics (counting 1891 when Cantor published his proof as "20th
century" of course), so needless to say I recommend you read more about
it if you're intrigued.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Fri, 11 Jul 2008 20:31:04 +0100, Orchid XP v8 wrote:
>>>> The class of computable functions (also known as recursive functions)
>>>> are something that you're familiar with.
>>> Er... no.
>>
>> Do you understand the concept of recursion?
>
> Sure.
>
> I don't know much about the formal theory of computation though. I
> always assumed that "computable function" just meant "function that can
> be computed by a computer". Apparently the definition is much less
> general that than...
Ah, I see.
I also don't have a good grasp of formal computational theory. I also
wouldn't have thought that "computable functions" was limited just to
recursive functions, though, just from the name.
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> always assumed that "computable function" just meant "function that can
> be computed by a computer".
Yes. But the question is, what functions *are* computable by a computer?
That's kind of the point.
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 <voi### [at] devnull> wrote:
> Mmm, I see. Yes, the third identity requires you to either recurse twice
> (requiring more stack), or to build a table of results to avoid the
> extra recursion (also requiring more memory).
More concrete examples: Heap sort can be implemented iteratively (the
heap sort algorithm itself only requires O(1) memory to sort an array
of values). AFAIK, quicksort cannot be implemented iteratively.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> Darren New wrote:
>
>> Map each real number to a positive integer.
>
> Um... like, how? There's more of them...
Yes. That's the point. Assume you do that. Then construct a real not on
the list. Obviously, your assumption that it was possible to do that
was wrong.
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New <dne### [at] sanrrcom> wrote:
> Orchid XP v8 wrote:
> > Darren New wrote:
> >
> >> Map each real number to a positive integer.
> >
> > Um... like, how? There's more of them...
> Yes. That's the point. Assume you do that. Then construct a real not on
> the list. Obviously, your assumption that it was possible to do that
> was wrong.
It kind of "makes sense" that there are "more" reals than integers.
What is more unintuitive is that the amount of rational numbers is the
same as the amount of integers.
(Curiously, to a mathematician it's the other way around: The latter
fact is quite intuitive, but the former is puzzling. Some even go as
far as half-jokingly saying that "there just can't be more reals than
integers, it doesn't make sense; there would be too many".)
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> Darren New wrote:
>
>> Map each real number to a positive integer.
>
> Um... like, how? There's more of them...
It's a proof by contradiction, so you start by assuming that you can
build such a map and then derive from that a contradiction, thus
invalidating the premise that you the map was possible.
It's wise to learn not to trust your intuitions too much with this sort
of thing. As warp pointed out, there are the same number of rationals
as natural numbers, whereas intuitively you might think that there's
more rationals than integers and the same number of reals as rationals.
And intuition becomes even less of a guide when you start reasoning
about more complicated sets.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> The class of computable functions (also known as recursive functions)
>>> are something that you're familiar with.
>>
>> Er... no.
>
> Well, maybe not by name, but you're certainly familiar with the concept.
> For example, you can see that the Ackermann function is computable
> while the Halting function is not. At the very least, since you code a
> lot you're intuitively familiar with the notion of what sorts of
> functions you can code (though maybe less so what sorts you *can't* code).
Proving that something exists is a *comparatively* easy task: Just hold
up one of them, and the fact that you're standing there holding it kinda
proves it exists.
Proving that something does *not* exist... well that's a whole other
kettle of fish. ;-)
[BTW... Who the HELL has fish in a kettle??]
> I don't have a formal definition, but perhaps I can give some of the
> intuition. The name derives from `Cantor's diagonal argument' for why
> the set of real numbers is strictly larger than the set of rationals. If
> you're not familiar with this proof you should read about it, as it's
> both absolutely brilliant and extremely simple.
>
> I've using the term more generally of course, but the basic idea is the
> same. Let's say you have two set of elements, A and B, and you want to
> provide a proof that there exist something in B which is not in A. One
> way you can do this that ends up being useful much of the time is to
> define an element, x, in B in such a way that it represents a
> modification of each element in A, and by doing so we prove that x
> cannot be in A since it's different that each element of A.
>
> This may sound a bit odd, and it oversimplifies a lot too, but I think I
> can explain it better with examples.
>
> In the case of Cantor's original argument A is the set of natural
> numbers and B is the set of reals. If we assume that there are the same
> number of natural numbers and reals, then you could provide an
> (infinite) list of all the real numbers. To form a real number that
> cannot be in this list, we form a number, x, which has at each digit a
> modification of a different real number in a hypothetical list. Means
> that x cannot be in our list, and thus by contradiction that it's
> impossible to form such a list in the first place.
>
> The halting argument has a similar flavor. In this case we want to show
> that there are functions that are not computable, so we create define a
> function that, given a program, determines if it halts and then modifies
> that behavior. But this program can't work on its own input and thus
> cannot be computable in the first place.
>
> There's several ways to apply this idea to show that there are total
> computable functions which are not primitive recursive, but here's one.
> Represent each primitive recursive program as a natural number (by
> compiling it to binary if you wish). Then, define a new function from
> the naturals to the naturals which, when given a number, decompiles it
> into a primitive recursive function, runs the function with its own
> numerical representation as input, and adds one to the result (note that
> the primitive recursive function is guaranteed to always halt). The
> resulting function is computable, but cannot be primitive recursive
> (since then for some input it would have it give its own output plus one!).
>
> You can use the same idea to construct a computable function that grows
> faster than any primitive recursive function, or a non-computable
> function which grows faster than any computable function (eg. the Busy
> Beaver function). It's also the same sort of idea that Goedel used in
> his proof that some theorems are unprovable. Personally, I find the
> idea to be probably the most interesting discovery of 20th century
> mathematics (counting 1891 when Cantor published his proof as "20th
> century" of course), so needless to say I recommend you read more about
> it if you're intrigued.
...OK, and this is the kind of thing that I sit down and read and end up
feeling utterly perplexed.
Logic, set theory, category theory, number theory, complexity theory,
topology... they all seem to abound with utterly counter-intuitive laws
and theorums. It's really quite mind-bending.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> always assumed that "computable function" just meant "function that
>> can be computed by a computer".
>
> Yes. But the question is, what functions *are* computable by a computer?
> That's kind of the point.
The question, surely, is what functions are *not* computable by a
computer? ;-)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
>
> I don't know much about the formal theory of computation though. I
> always assumed that "computable function" just meant "function that can
> be computed by a computer". Apparently the definition is much less
> general that than...
>
Not really! Formally you tend to consider only functions which take a
single natural number as input and provide a single number as output.
This may seem restrictive, but remember that everything on your computer
can be considered as being as represented by integers (in binary)
anyway, so it's not really a restriction at all.
As for the `function' part of `computable function' you of course mean
something which only takes an input and provides an output, and thus
doesn't allow for user interaction and the such, but you can always
model user interaction as simply providing the inputs to a an
appropriately defined proper function so even this isn't really a
restriction.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> What is more unintuitive is that the amount of rational numbers is the
> same as the amount of integers.
What is unintuitive to me is that if you draw a numberline on the wall
and toss a dart at it (figuratively speaking), your probability of
hitting a rational number is zero. That is, there are so many more reals
than rationals that the chance of picking a real that's rational at
random is literally zero. It would seem there's *some* epsilon chance,
but apparently not. :-)
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New <dne### [at] sanrrcom> wrote:
> What is unintuitive to me is that if you draw a numberline on the wall
> and toss a dart at it (figuratively speaking), your probability of
> hitting a rational number is zero. That is, there are so many more reals
> than rationals that the chance of picking a real that's rational at
> random is literally zero. It would seem there's *some* epsilon chance,
> but apparently not. :-)
Yet between any two chosen real numbers there's an infinite amount of
rational numbers, and vice-versa. There's no range of real numbers where
there wouldn't be an infinite amount of rational numbers.
Yet there are "more" real numbers than rational numbers.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Fri, 11 Jul 2008 21:00:36 +0100, Orchid XP v8 wrote:
>>> always assumed that "computable function" just meant "function that
>>> can be computed by a computer".
>>
>> Yes. But the question is, what functions *are* computable by a
>> computer? That's kind of the point.
>
> The question, surely, is what functions are *not* computable by a
> computer? ;-)
I would think any problem that was mathematically intractable. :-)
Or put another way, some computational problems where the growth function
is exponential. Some of those problems are solved on a small scale
computationally (like the traveling salesman problem), but as the scale
of the problem grows, the complexity grows as well.
At least that's what I remember from my discrete maths class in the early
90's. :-)
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Fri, 11 Jul 2008 20:59:40 +0100, Orchid XP v8 wrote:
> Proving that something exists is a *comparatively* easy task: Just hold
> up one of them, and the fact that you're standing there holding it kinda
> proves it exists.
Depends on the nature of the proof. Try taking that argument to someone
with a background in philosophy. :-)
"My universe is what happens to my eyes and my ears; anything else is
surmise and hearsay."
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> ...OK, and this is the kind of thing that I sit down and read and end up
> feeling utterly perplexed.
>
> Logic, set theory, category theory, number theory, complexity theory,
> topology... they all seem to abound with utterly counter-intuitive laws
> and theorums. It's really quite mind-bending.
Don't be intimidated, I think that the diagonalization arguments are
actually rather easy to understand for someone who doesn't have a lot of
background in this sort of thing. It's a bit mind blowing at first, but
at some point it'll click and everything will make sense, something
which I haven't found to be the case with eg. set theory.
I suggest you start by proving that there's the same number of rationals
as natural numbers. Once you've done that study Cantor's diagonal
argument until you understand why there's more reals than natural
numbers, and thus more reals than rationals. Ask for help if you're
confused and I'll provide it when I read the newsgroup (or more likely,
someone else will beat me to it).
From there I'd take a look at the definition of the busy beaver
function as an example of the same sort of technique on computable
functions, and then look at the halting theorem in the same light.
Sooner or later it should all start to seem intuitive and
straightforward, even if it's a bit mind-bending at the moment.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> The question, surely, is what functions are *not* computable by a
>> computer? ;-)
>
> I would think any problem that was mathematically intractable. :-)
Well, if you don't know "how" to solve a problem then you can't write a
program that does it. That's true enough. I'm not sure it makes it not a
"computable function" though...
> Or put another way, some computational problems where the growth function
> is exponential. Some of those problems are solved on a small scale
> computationally (like the traveling salesman problem), but as the scale
> of the problem grows, the complexity grows as well.
>
> At least that's what I remember from my discrete maths class in the early
> 90's. :-)
Nope. That's not "impossible" to compute, just really damned slow. ;-)
To a mathematician, 10^1534 years is a finite amount of time. In
practical terms it's a ridiculously long time - many times longer than
the current age of the universe, and plenty long enough for any
hypothetical computer to exhaust all the available energy in the
universe without reaching the end - but still, technically, a finite
run-time.
If we're talking about what a computer can *theoretically* calculate.
It's just a matter of leaving the machine running for long enough.
But even given infinite time and memory, a computer *still* can't solve
the Halting Problem though. Even theoretically. Don't ask me why...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> What is unintuitive to me is that if you draw a numberline on the wall
> and toss a dart at it (figuratively speaking), your probability of
> hitting a rational number is zero. That is, there are so many more reals
> than rationals that the chance of picking a real that's rational at
> random is literally zero. It would seem there's *some* epsilon chance,
> but apparently not. :-)
Probability of hitting an object with a size of zero: 0%. ;-)
Probability of hitting an uncountable infinity of objects each with a
size of zero: 100%.
GO FIGURE!
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Fri, 11 Jul 2008 13:09:40 -0700, Kevin Wampler wrote:
> I suggest you start by proving that there's the same number of rationals
> as natural numbers.
*ding* - light bulb just went on here. I was trying to figure this one
out, and it just intuitively appeared to me.
The weird thing is that I can't even explain it, but I understand it.
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
> I suggest you start by proving that there's the same number of rationals
> as natural numbers.
But there are surely *more* rational numbers than natural numbers?
Actually, let's try something easier: Common sense tells you that the
number of 2D coordinates is obviously [vastly] greater than the number
of 1D points. Yet set theory asserts that both sets are exactly the same
size. How can this be?
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> But there are surely *more* rational numbers than natural numbers?
>
> Actually, let's try something easier: Common sense tells you that the
> number of 2D coordinates is obviously [vastly] greater than the number
> of 1D points. Yet set theory asserts that both sets are exactly the same
> size. How can this be?
First, we need a clear definition of `size' which will work for infinite
sets:
Given two sets, A, and B, we'll say that B is at least as large as A (B
>= A) if there is a function which maps every element in A into a
unique element in B.
If no such function is possible, then we say that A is larger than B (A
> B).
If A >= B and B >= A. Then A and B are of the same size (A <=> B).
(Note my ASCII isn't standard here, but I think it works intuitively
enough).
Let's start even simpler, and show that the set of natural numbers, N,
is the same size as the set of integers, I. Clearly I >= N, since it's
trivial to map easy natural number into a unique integer.
To show that N >= I, consider the function
function f(i) {
if i < 0 {
return -2*i - 1
} else {
return 2*i
}
}
You can check that (assuming I didn't make a mistake) this function maps
each integer into a unique natural number. This N >= I
Since we have I >= N and N >= In so I <=> N.
Also note that there's a trick that works for proving that N >= S for
many different sets S -- just show that you can represent every element
in S exactly in a computer program. Since the program can be compiled
to binary, the compiler does the work of defining the function from
element in S to a unique element in N for you.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> But even given infinite time and memory, a computer *still* can't solve
> the Halting Problem though. Even theoretically. Don't ask me why...
Here's the idea. Assume we have a function halts(P,i), which takes a
function P and returns true of P(i) halts and false otherwise. Then
write the following function, D:
function D(i) {
if halts(i,i) {
while true
} else {
return 0
}
}
Note that since, mathematically, be consider all programs as integers
(for example their compiled binary form), the line halts(i,i) is ok
since we can interchange programs and integers to our heart's desire.
Now, when happens if we try to compute halts(D,D)?
(I'll leave this to work out for yourself, as it's a good exercise)
Once you groked this, note that although the halts function is perfectly
well defined mathematically, we've just showed that it's impossible to
ever program, and therefore it is not a computable function. You can of
course, program a halts function that works perfectly well on a subset
of all inputs, but you can't write to to determine the answer for all
possible programs.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
As a quick additional note, you may observe that if we order the
possible inputs the halts function (both considered as integers) in a
big matrix, then the the call halts(i,i) is taking elements along the
*diagonal* of this matrix, and the function D is modifying the output of
the halts function along this diagonal. Hey, diagonals! It's another
diagonalization proof! The wikipedia article has a bit more thorough
explanation of this:
http://en.wikipedia.org/wiki/Halting_problem, bottom of the `Sketch of
proof' section.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Jim Henderson wrote:
>
> *ding* - light bulb just went on here. I was trying to figure this one
> out, and it just intuitively appeared to me.
>
It's that sort of moment of epiphany that I love about learning this
sort of stuff. One moment it seems totally false and the next moment it
somehow makes sense, a bit it seems obvious!
> The weird thing is that I can't even explain it, but I understand it.
As for the proof, this site explains it reasonably well i think:
http://www.math.hmc.edu/funfacts/ffiles/30001.3-4.shtml
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 <voi### [at] devnull> wrote:
> Kevin Wampler wrote:
> > I suggest you start by proving that there's the same number of rationals
> > as natural numbers.
> But there are surely *more* rational numbers than natural numbers?
There's an infinite amount of rational numbers. There's an infinite
amount of natural numbers. Which set of numbers is larger?
The answer is that the sets have the same size. That's because a unique
mapping from each rational number to a distinct natural number can be
constructed. This means that for each rational number there exists a
distinct natural number. Hence the amount of both is the same.
Now, why this is even relevant? It's relevant because real numbers,
quite surprisingly, do *not* have such a mapping to natural numbers.
It's impossible to construct a unique mapping from each real number to
a distinct natural number. There are "too many" reals for this. For this
reason the set of real numbers is "larger" than the set of natural numbers
(and consequently the set of rational numbers).
Where this gets unintuitive is when you think about the relation between
rational numbers and real numbers: Take any two rational numbers, and
between them there will be an infinite amount of real numbers. Take any
two real numbers, and between them there will be an infinite amount of
rational numbers. No matter which pair of numbers you choose, there will
always be numbers from the other set between them. Yet the set of real
numbers is larger than the set of rational numbers.
> Actually, let's try something easier: Common sense tells you that the
> number of 2D coordinates is obviously [vastly] greater than the number
> of 1D points. Yet set theory asserts that both sets are exactly the same
> size. How can this be?
You may be confusing the density of the numbers with their total amount.
Even though more rational numbers can appear in a smaller place than
natural numbers doesn't mean their total amount is larger.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
>> Map each real number to a positive integer.
>
> Um... like, how? There's more of them...
What he meant to say was that no matter how you map integers to real
numbers, one can construct a real number that has no integer mapped to it.
Me: There's no way to make a 1-1 correspondence between reals and integers.
You: Yes there is.
Me: I defy you to provide me with such a mapping.***
You: OK. How about this one?
Me: (Using Darren's recipe) - here's a real number that isn't mapped to
an integer.
*** Not a mathematically sound argument. In mathematics, you can prove
the existence of certain sets, and you can also prove that you can never
explicitly exhibit those sets (i.e. you can *only* show they exist -
it is mathematically impossible to demonstrate them, though). So an
argument that shows one cannot exhibit/construct a certain set does not
imply that they don't exist.
Some day I have to formally learn how that is.
--
"Auntie Em: Hate Kansas. Hate You. Took Dog. -Dorothy."
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> It kind of "makes sense" that there are "more" reals than integers.
> What is more unintuitive is that the amount of rational numbers is the
> same as the amount of integers.
That, and the fact that R^n has as many points as R (for positive
integers n).
> (Curiously, to a mathematician it's the other way around: The latter
> fact is quite intuitive, but the former is puzzling. Some even go as
> far as half-jokingly saying that "there just can't be more reals than
> integers, it doesn't make sense; there would be too many".)
That's not been my experience with mathematicians - they find both to
be fairly interesting.
Of course, a lot of this "weirdness" is merely due to the definition of
equality of the size of two sets. It was a convenient one to deal with
infinite sets.
--
"Auntie Em: Hate Kansas. Hate You. Took Dog. -Dorothy."
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> What is unintuitive to me is that if you draw a numberline on the wall
> and toss a dart at it (figuratively speaking), your probability of
> hitting a rational number is zero. That is, there are so many more reals
> than rationals that the chance of picking a real that's rational at
> random is literally zero. It would seem there's *some* epsilon chance,
> but apparently not. :-)
Well, your probability of hitting a given real number is also 0. Same
amount of weirdness.
I was always somewhat uncomfortable with that aspect of probability on
continuous distributions. Because "in real life" it isn't impossible for
me to hit right at the center when thrown at random.
And then there's the whole issue of interpretation of probability and
especially statistics - I recently got more interested in the basics
(saw too many funny stats, and wanted to learn it well enough to
recognize the kooky ones).
Advanced probability theory involves measure theory - which I have yet
to study properly. My guess is what you're saying holds true because the
set of rationals is a set of measure 0 w.r.t. to the measure they use in
probability.
--
"Auntie Em: Hate Kansas. Hate You. Took Dog. -Dorothy."
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
>> Map each real number to a positive integer. Now for each number, take
>> the real number whose first digit differs from the first digit of the
>> first real, whose second digit differs from the second digit of the
>> second real, etc. You've just constructed a real which is, by
>> construction, not on your list that maps all real numbers to integers.
>
> I think that the concept you are trying to explain could become clearer
> if you also prove why the amount of rational numbers between 0 and 1 is
> the *same* as the amount of integers. (In other words, each rational
> number can be uniquely mapped to an integer, and there are no rational
> numbers that can't be.)
Yes. And to be formally correct, he has to deal with the fact that
0.3459999999.... is also 0.346 and adjust a few minor details to account
for it.
--
"Auntie Em: Hate Kansas. Hate You. Took Dog. -Dorothy."
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> What is Ackermann's function, why does it grow so fast, and why does
> anybody care anyway?
Not sure if this will answer your question, but it's a fun read:
http://www.scottaaronson.com/writings/bignumbers.html
--
"Auntie Em: Hate Kansas. Hate You. Took Dog. -Dorothy."
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Mueen Nawaz wrote:
> Darren New wrote:
>> What is unintuitive to me is that if you draw a numberline on the wall
>> and toss a dart at it (figuratively speaking), your probability of
>> hitting a rational number is zero. That is, there are so many more
>> reals than rationals that the chance of picking a real that's rational
>> at random is literally zero. It would seem there's *some* epsilon
>> chance, but apparently not. :-)
>
> Well, your probability of hitting a given real number is also 0.
> Same amount of weirdness.
Yes. But I meant my probability of hitting *any* rational number is zero.
> Advanced probability theory involves measure theory - which I have
> yet to study properly. My guess is what you're saying holds true because
> the set of rationals is a set of measure 0 w.r.t. to the measure they
> use in probability.
I think that was the technical term I saw, yes. Just seemed strange. Not
wrong, but strange. :-)
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New <dne### [at] sanrrcom> wrote:
> > Well, your probability of hitting a given real number is also 0.
> > Same amount of weirdness.
> Yes. But I meant my probability of hitting *any* rational number is zero.
I think that this confuses people because they think that if the
probability for something is 0, that means that it's *impossible* for
that something to happen.
This is indeed so in the discrete case. However, in this case the
probability is 0 because the total probability of 1 has been divided
among an *infinite* amount of numbers. Thus, mathematically, the resulting
probability of hitting a given number is 0, as 1/infinite = 0.
*After* you have thrown the dart, the probability to hit the number
the dart did hit grows to 1 (or 100%).
Or if we say the same thing in another way: Even though there is an
infinite amount of numbers, that doesn't mean you can't choose one.
(I really wonder if this has any relation whatsoever to the so-called
axiom of choice.)
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> *After* you have thrown the dart, the probability to hit the number
> the dart did hit grows to 1 (or 100%).
But is the probability that it hit any rational number (vs any
irrational number) non-zero at that point? If you do it countably many
times, will you *ever* hit *any* rational number?
> (I really wonder if this has any relation whatsoever to the so-called
> axiom of choice.)
That's pretty much exactly what the axiom of choice is. Given an
infinite set of sets, can you create a set by picking one element from
each subset?
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Warp" <war### [at] tagpovrayorg> wrote in message
news:4877ba85@news.povray.org...
> It kind of "makes sense" that there are "more" reals than integers.
> What is more unintuitive is that the amount of rational numbers is the
> same as the amount of integers.
And now the really fun part: Is there a subset of real numbers that is "more
numerous" than intergers or rationals but less so than reals?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
somebody wrote:
> And now the really fun part: Is there a subset of real numbers that is "more
> numerous" than intergers or rationals but less so than reals?
That's actually a long-standing problem, but I remember hearing that
someone had figured out the answer must be "No." I believe they were
waiting on others verifying the proof. (Which, as you can imagine, must
be pretty hairy.)
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
somebody wrote:
> And now the really fun part: Is there a subset of real numbers that is "more
> numerous" than intergers or rationals but less so than reals?
I bet even Gail didn't know that Oracle has solved *that* problem.
http://laurentschneider.com/wordpress/2007/10/what-is-bigger-than-infinity.html
(Check out the comments, too.)
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
somebody wrote:
> And now the really fun part: Is there a subset of real numbers that is "more
> numerous" than intergers or rationals but less so than reals?
Apparently, in most maths, it's neither true nor false, but an axiom to
be adopted.
http://en.wikipedia.org/wiki/Continuum_hypothesis
(That's the *actual* answer to the question, methinks.)
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
>> Well, your probability of hitting a given real number is also 0.
>> Same amount of weirdness.
>
> Yes. But I meant my probability of hitting *any* rational number is zero.
Because both are sets of measure 0 here. That's why it's the same
amount of weirdness.
--
Cut my pizza in six slices, please; I can't eat eight.
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> I think that this confuses people because they think that if the
> probability for something is 0, that means that it's *impossible* for
> that something to happen.
>
> This is indeed so in the discrete case. However, in this case the
> probability is 0 because the total probability of 1 has been divided
> among an *infinite* amount of numbers. Thus, mathematically, the resulting
> probability of hitting a given number is 0, as 1/infinite = 0.
Maybe so, but it's not as compelling as a formal proof. In math, you
can't divide by infinity.
I'm not saying it's "wrong", and your message addresses the dilemma in
another way. The question ultimately is the interpretation of
probability. I know the mathematical definition, but how do I give it
meaning in the real world?
--
Cut my pizza in six slices, please; I can't eat eight.
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> somebody wrote:
>> And now the really fun part: Is there a subset of real numbers that is
>> "more
>> numerous" than intergers or rationals but less so than reals?
>
> Apparently, in most maths, it's neither true nor false, but an axiom to
> be adopted.
>
> http://en.wikipedia.org/wiki/Continuum_hypothesis
Yes. Haven't studied it, but I remember that the answer was either
"No", or "Can't be decided." Your message makes me think it's the latter.
--
Cut my pizza in six slices, please; I can't eat eight.
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
