|
![](/i/fill.gif) |
Kevin Wampler wrote:
> I'm not Darren, and he'd probably be more familiar with this than I, but
> here's what I recall.
>
> The class of computable functions (also known as recursive functions)
> are something that you're familiar with.
Er... no.
> Considered in their most basic
> context, these are all functions which take a natural number as input,
> provides an integer as output, and which you could write a computer
> program to compute. If there's a program which can compute this
> function for each possible natural number (in other words, it always
> halts), then you have a total computable function.
>
> Way back in the early days of people starting to understand this sort of
> stuff -- before diagionalization proofs were used for this sort of
> thing, there was a conjecture that this class of total computable
> functions was equivalent to the class of what are called primitive
> recursive functions. You can think of a primitive recursive function,
> basically (iirc), as any function you could code up if only allowed for
> loops which didn't change their loop bounds during their execution (no
> recursion and no while loops either obviously).
>
> While it seems "obvious" since you're familiar with diagonalization type
> arguements, that this class is strictly smaller than the class of total
> computable functions, you can get a bit of an idea for why people made
> this confusion if you attempt to actually think of a function which is
> total computable but not primitive recursive. Almost all the function
> you normally deal with (addition, subtraction, division, factorial,
> exponentiation, etc) are all primitive recursive.
>
> Here's where the Ackermann function comes in. It's obviously a total
> computable function, yet you can show that it cannot be primitive
> recursive. The essence of this argument is that the growth rate of the
> Ackermann function is larger than what could be achieved by any
> primitive recursive function. I believe that the Ackermann function was
> the first concrete example of a well defined total computable function
> which was not primitive recursive -- hence why people care about it.
I see... Thank you for the illumination. Now tell me what a
diagonalization argument is, and how you pronounce it without sounding
stupid. ;-)
> If you're curious as to why it grows so quickly, I suggest you code it
> up and examine it's behavior for a bit. It's an enjoyable exercise in
> experimentally poking around in the guts of a rather odd mathematical
> function.
Note how the Wikipedia article explicitly mentions a Haskell
implementation because it's so easy. ;-) Of course, if you want to
*observe* its behaviour rather than just get the answer, you'd code it a
bit differently...
> Fun Fact! The union-find data structure has as an amortized complexity
> bound for many of many of its operations a running time proportional to
> the *inverse* of the Ackermann function! which is the slowest growing
> non-constant big-O of any algorithm I'm aware of (though I've explicitly
> never looked for others).
Fun fact: This is how I found out about "Ackermann function". Just now.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
![](/i/fill.gif) |