|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |