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