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


Groups > comp.theory > #39621

Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics

From Jeff Barnett <jbb@notatt.com>
Newsgroups comp.theory
Subject Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics
Date 2021-09-20 14:01 -0600
Organization A noiseless patient Spider
Message-ID <siapb5$kp9$1@dont-email.me> (permalink)
References <a7c2345d-e3ab-4296-8b1b-877212aa8c7dn@googlegroups.com> <siaf08$1ft$1@dont-email.me> <e08a8e4e-5708-41c0-80b6-3def72b74fadn@googlegroups.com>

Show all headers | View raw


On 9/20/2021 12:43 PM, Charlie-Boo wrote:
> On Monday, September 20, 2021 at 1:05:14 PM UTC-4, Jeff Barnett wrote:
>> On 9/20/2021 10:38 AM, Charlie-Boo wrote:
>>> A closed form i.e. O(1) is the Holy Grail of Algorithmics.
>>>
>>> Every problem is a recursive definition since running a program is evaluating a recursive definition.
>>>
>>> [Let INIT = Initial State. NEXTSTATE(state) = Iterate. HALTS(state)="Does state halt?" Then PROG(Input) is HALTS(Input)?Input:PROG(NEXTSTATE(Input)).]
>>>
>>> The Nth Fibonacci Number is a recursive definition but there is a closed form (e.g. wiki.)
>>>
>>> (The trick, however, is that iteration is replaced by exponentiation of a real number.)
>>>
>>> How far have people gotten in developing closed forms for recursive definitions starting with Fibonacci?
>>>
>>> Solving this 2-place function over N would be helpful (I will explain.)
>>>
>>> 2 5 34 1,597
>>> 8 55 2,584
>>> 144 6,765
>>> 46,368
>>>
>>> C-B
>>>
>> First things first. Evaluating a closed form is not necessarily O(1).
>> For example, 2^{2^{2^ ...... {2^n}}} is as much a closed form as is n^2.
>> If we are measuring computational cost, there is a non constant amount
>> of work to do depending on the size of n, the representation of n, and
>> the representation of the value. Further, the order of magnitude of the
>> work depends on algorithm and computing device.
>>
>> I think what you meant to say is evaluating f(n) is O(1) if f(x) is a
>> constant for all x. Of course if your computation method must read x
>> even though it is not relevant, than the order of the work is O(|x|),
>> where |x| is the length of the string representing the value of x.
>> -- 
>> Jeff Barnett
> Closed forms don't have a "..." operator.
> How is that defined, by the way?

It was meant to indicate "any number of", a constant. It's called an 
ellipsis in English. In the present case you can have the exponential 1 
deep, two deep, up to any constant number you wish deep - the depth does 
not depend on n.

As a side note: there is no agreed upon definition of "closed form" 
among mathematicians, computer scientists, or philosophers. The intent 
varies from a constant to a recursive total function definition that can 
be evaluated in a finite number of steps with each step a finite 
calculation. This latter requirement may be abused when dealing with 
real numbers. For example, is PI + E a closed form? Actually is PI a 
closed form?

You talked about Fibonacci numbers above. You do know that that closed 
form involves raising two irrational numbers to the nth power? It 
happens that the sum of those powers multiplied by their coefficients 
when added produce an integer but that is zero gain in efficiency. 
Instead of doing about n integer additions, you must do about 2n 
multiplies of non rationals, so what is the gain??????
-- 
Jeff Barnett

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