 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New <dne### [at] san rrcom> 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
|
|
| |
| |
|
|
|
|
| |
|
|
