Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.theory > #39841

Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics

From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups comp.theory
Subject Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics
Date 2021-09-24 21:40 +0100
Organization A noiseless patient Spider
Message-ID <87r1ddyaeo.fsf@bsb.me.uk> (permalink)
References <a7c2345d-e3ab-4296-8b1b-877212aa8c7dn@googlegroups.com> <87zgs756fi.fsf@bsb.me.uk> <db892783-52df-4412-a28b-a26cfd9f323an@googlegroups.com>

Show all headers | View raw


Charlie-Boo <shymathguy@gmail.com> writes:

> On Monday, September 20, 2021 at 4:38:17 PM UTC-4, Ben Bacarisse wrote:
>> Charlie-Boo <shyma...@gmail.com> writes: 
>> 
>> > A closed form i.e. O(1) is the Holy Grail of Algorithmics.
>> Closed forms are rarely O(1). First, O(1) depends on some measure. In 
>> comp.theory it's reasonable to expect you mean O(1) steps of a Turing 
>> machine. Secondly, O(1) is about an algorithm, so the "cost" of 
>> evaluating a closed form depends on how good an algorithm you have. 
>> I.e. I can't show you a wrong simply by showing an O(n) algorithm for 
>> some closed form, because there might be a better one I have not thought 
>> of. Third, the order of an algorithm can depend on the encoding of the 
>> "inputs" and the "outputs" so I'd have to cover every conceivable 
>> encoding as well. 
>> 
>> I don't have the time or the inclination to do that, so here's a 
>> challenge... Given the simple function f(n) = n+1, do you think there 
>> is an encoding for n (and for the result) such that some TM M can 
>> compute f(n) in O(1)?
>> 
>> The long and the short of it is that I don't think you meant to say what 
>> you said. That O(1) means something to you which is not the usual 
>> technical meaning. 
>> 
> O(1) means a fixed or bounded number of steps in the algorithm where
> each step is considered to be constant time.  So it really means
> constant time.

It has an actual meaning which is not constant time.  What you count
matters.  An algorithm that does O(1) arithmetic operations won't
necessarily be constant time (operations on large numbers might be
slower than those on small numbers).

> A closed form is an algorithm.

That's not what the phrase usually means.  If you mean an algorithm, why
not say an algorithm?  People who know what a closed form is will be
confused if you use the term to mean algorithm.

> Evaluate the expression.

There may be lots of different algorithms for evaluating the expression.

> If you want to talk about alternate
> equivalent closed forms that is another question.
>
> Encoding I/O is usually considered to be part of the program and we
> use standard mathematical representations for the actual I/O.

So pi can be represented with 100% accuracy using the standard
mathematical representation "𝞹"?  And if the "closed form" is about
square roots, the result can be "√𝞹"?

> Turing Machines are at a lower level than computers in terms of how
> they compute and will have a hard time keeping up with them efficiency
> wise.

OK.  So you are not talking about TMs.  comp.theory might be the wrong
group.  Do you have some abstract model of computation in mind?  TAOCP
using a made-up machine language to do this sort of thing.

> I meant that the time complexity function is a constant which is
> represented by 1.

You ask in the other reply if, after all this nit-picking (I would not
call it that) could people answer the question.  The question was:

  How far have people gotten in developing closed forms for recursive
  definitions starting with Fibonacci?

by which I think you mean

  How far have people gotten in developing constant time algorithms for
  recursively defined functions like Fibonacci?

Well, there are many closed form expressions for F(n) but I don't know
of any algorithms that can evaluate them in constant time.  So I think
the answer is nowhere.

If we don't allow n to be unbounded then F(n) can be evaluated in
constant time, but that's theoretically true for any function since, for
bounded inputs, we can just use a lookup table.

-- 
Ben.

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Charlie-Boo <shymathguy@gmail.com> - 2021-09-20 09:38 -0700
  Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Jeff Barnett <jbb@notatt.com> - 2021-09-20 11:05 -0600
    Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Charlie-Boo <shymathguy@gmail.com> - 2021-09-20 11:43 -0700
      Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Jeff Barnett <jbb@notatt.com> - 2021-09-20 14:01 -0600
        Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Charlie-Boo <shymathguy@gmail.com> - 2021-09-24 16:41 -0700
          Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Jeff Barnett <jbb@notatt.com> - 2021-09-24 20:46 -0600
  Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-20 21:38 +0100
    Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Charlie-Boo <shymathguy@gmail.com> - 2021-09-24 11:10 -0700
    Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Charlie-Boo <shymathguy@gmail.com> - 2021-09-24 11:23 -0700
      Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-24 21:40 +0100
    Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Charlie-Boo <shymathguy@gmail.com> - 2021-09-24 16:45 -0700
      Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-25 21:31 +0100
        Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-09-26 10:26 -0700
          Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-26 19:02 +0100
    Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Charlie-Boo <shymathguy@gmail.com> - 2021-09-24 17:04 -0700
      Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-25 21:35 +0100

csiph-web