>>> 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