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


Groups > comp.theory > #39910

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:31 +0100
Organization A noiseless patient Spider
Message-ID <875yuowg5y.fsf@bsb.me.uk> (permalink)
References <a7c2345d-e3ab-4296-8b1b-877212aa8c7dn@googlegroups.com> <87zgs756fi.fsf@bsb.me.uk> <db4f0bd4-b103-4c97-95ba-8ae1330c954fn@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. 
>> 
>> 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)?
>
> Certainly.

Show it.

> Must the relationship between the tape and the outside
> world be the same before and after the TM runs?

I don't know what that means.

> If not then it is instantaneous.

Time has no bearing on any TM computations.  O(1) means that the length
of the TM configuration sequence is bounded above by a constant.

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