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


Groups > comp.theory > #39622

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-20 21:38 +0100
Organization A noiseless patient Spider
Message-ID <87zgs756fi.fsf@bsb.me.uk> (permalink)
References <a7c2345d-e3ab-4296-8b1b-877212aa8c7dn@googlegroups.com>

Show all headers | View raw


Charlie-Boo <shymathguy@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.

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