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