Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| 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> |
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
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