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-24 21:40 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <87r1ddyaeo.fsf@bsb.me.uk> (permalink) |
| References | <a7c2345d-e3ab-4296-8b1b-877212aa8c7dn@googlegroups.com> <87zgs756fi.fsf@bsb.me.uk> <db892783-52df-4412-a28b-a26cfd9f323an@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. >> > O(1) means a fixed or bounded number of steps in the algorithm where > each step is considered to be constant time. So it really means > constant time. It has an actual meaning which is not constant time. What you count matters. An algorithm that does O(1) arithmetic operations won't necessarily be constant time (operations on large numbers might be slower than those on small numbers). > A closed form is an algorithm. That's not what the phrase usually means. If you mean an algorithm, why not say an algorithm? People who know what a closed form is will be confused if you use the term to mean algorithm. > Evaluate the expression. There may be lots of different algorithms for evaluating the expression. > If you want to talk about alternate > equivalent closed forms that is another question. > > Encoding I/O is usually considered to be part of the program and we > use standard mathematical representations for the actual I/O. So pi can be represented with 100% accuracy using the standard mathematical representation "𝞹"? And if the "closed form" is about square roots, the result can be "√𝞹"? > Turing Machines are at a lower level than computers in terms of how > they compute and will have a hard time keeping up with them efficiency > wise. OK. So you are not talking about TMs. comp.theory might be the wrong group. Do you have some abstract model of computation in mind? TAOCP using a made-up machine language to do this sort of thing. > I meant that the time complexity function is a constant which is > represented by 1. You ask in the other reply if, after all this nit-picking (I would not call it that) could people answer the question. The question was: How far have people gotten in developing closed forms for recursive definitions starting with Fibonacci? by which I think you mean How far have people gotten in developing constant time algorithms for recursively defined functions like Fibonacci? Well, there are many closed form expressions for F(n) but I don't know of any algorithms that can evaluate them in constant time. So I think the answer is nowhere. If we don't allow n to be unbounded then F(n) can be evaluated in constant time, but that's theoretically true for any function since, for bounded inputs, we can just use a lookup table. -- 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