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


Groups > comp.theory > #39911

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-25 21:35 +0100
Organization A noiseless patient Spider
Message-ID <87zgs0v1en.fsf@bsb.me.uk> (permalink)
References <a7c2345d-e3ab-4296-8b1b-877212aa8c7dn@googlegroups.com> <87zgs756fi.fsf@bsb.me.uk> <c509d359-07fe-4dd8-bf5a-5a82b39fd354n@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. 
>> 
>> -- 
>> Ben.
>
>> 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)?
>
> You could compute addition in O(1).

O(1) what?  Using what encoding?  I think you are deliberately not
listening.

If you just want to chat, this seems like an odd way to do it.  If you
want find out how to express whatever it is you are trying to say you
will have to ask good questions and study the answers.

-- 
Ben.

Back to comp.theory | Previous | Next — Previous 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