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